CSC207.01 2014F, Class 35: Doubly-Linked Lists

Continue lab partners! (I didn't find the cards.)

Don't forget to vote today (provided you are permitted to do so)

Overview

Preliminaries

Extended office hours this week and next week.
- Complicated by exam times and too many meetings.
Today's survey: Should I switch to online signup for my office hours? (You may vote "I prefer online signup" or "I prefer paper signup"; you may also choose not to vote.) No clarity.
Handout: Article on Skip Lists.
We'll spend a bit of time talking about HW 8 today.
Do you want to work alone or with partners on the next HW?
I've restructured the schedule to give us more time to talk about linked lists and other data structures.
I've been scheduled in an important meeting during class time on Friday. (Thank you Grinnell College.) You should show up and do the lab on Queues. I may get a substitute, or I may trust Mira to run the lab on her own. (You all trust Mira. Yay!)
Do you want to do the next assignment as individuals or in small teams? Email me if you want to work individually.

Homework 8: Sorting Out Sorting due Wednesday.
Readings for Wednesday:
- Linear Structures
- Stacks
- Yes, these used to be the readings for today.

Peace studies talk Monday at 4:15 p.m. in JRC 101 "With All the Worldâ€™s Violence, Where is Peace?"

What are the required/optional parts?

Gremlins.

You have to do a lot of code reading to even get started on homework 8.

Today's random comment: One of the things that your predecessors noted was helpful about this course is that they had to read a lot of code.
I think there are two important aspects to this comment.
- You will have to read code to contribute to an existing project, so practice doing so is good. (And perhaps it's that my code is confusing enough that "If you can read Sam's code, you can read anyone's".)
- My code illustrates some good practices, and you learn about practices better by reading code than just by hearing about them in general.
I also expected that you'd done a decent amount of this code reading in the corresponding labs.

Why isn't my sort method working?

Most common experiences: Using wrong limits (either starting or ending).
- A partition in which the counter is initialized to 0, rather than to lb.
- An insert in which you stop one away from the end.
If you do your loop invariants carefully, and step through your code by hand, you can help avoid these issues.
How do you decide what to use when you step through by hand? Lots of randomized tests (of the particular method).

Those merge methods are weird

I tend to over-generalize my code.
In some cases, it's just force of habit.
In others, I think general solutions make certain things easier. (For example, the most general merge can work with recursive or iterative quicksort, with or without allocating new arrays.)

Can you go over the recursion in merge sort?

What's the theory between the shifting rather than swapping.

    6 0 7 3 6 5 4 2 0

Conceptual

    sorted | unsorted

Work 6|0 7 3 6 5 4 2 0 0 6|7 3 6 5 4 2 0 0 6 7|3 6 5 4 2 0 0 3 6 7|6 5 4 2 0 0 3 6 6 7|5 4 2 0 0 3 5 6 6 7|4 2 0 0 3 4 5 6 6 7|2 0

There's also a nice animated gif on Wikipedia.

Why swap, given that shift is more efficient?

There are often multiple approaches to these problems, including some that I didn't think about.

CMV suggested using positions, rather than checking the next link, when re-iterating a list.
DR suggested that we keep an array of pointers to the node's we've passed by.

Discuss the following questions with your partner(s).

Does our previous method break the implementation of add?
If so, how can we fix it?
How can we remove an element efficiently? (We may have to add or change the meaning of various fields in the class or iterator.)
- Add a 'previous' field to nodes
- Two dummy nodes, keep the cursor two back
How do we prevent the client from calling remove twice in sequence?
- Store a flag to indicate whether or not you just removed an element.
- remove checks the flag
- remove sets the flag
- everything else clears the flag

Discuss with partner

What changes do we make to the Node class?
In dealing with singly-linked lists, we kept the cursor at the node before the next node. Where should we keep it now?
Given those decisions, how do we implement
- add?
- remove?
- next? *`previous?
In dealing with the previous method, we had to store additional information. Do we need to store the same information?

Are there benefits to having the last element link to the first, and vice versa? Will a dummy node make a difference?