CS 240: Lecture 11 - Doubly-Linked List

Dear students:

As we saw last lecture, singly-linked lists perform structural changes much faster than array lists. Inserting or removing an item changes only the local neighborhood. In an array list, these changes ripple outward. But that doesn't mean linked lists are always the better choice; each has its strengths. Today, we compare some of these operations with our StopWatch utility. But first, let's improve our singly-linked list class a bit to make a workhorse list of which we can be proud.

Doubly-linked List

Singly-linked lists have several imperfections:

• Empty lists require conditional logic that is easy to get wrong.
• Making structural changes requires extra bookkeeping information. If you are trying to remove an item, you must first find the item. But the link changes need to happen on the predecessor node, which you've just passed by.
• The list can only be iterated through efficiently from head to tail. Sometimes you want to iterate in reverse. You're fighting the current if you process the elements in reverse order, and you will likely end up with an \(\Theta(n^2)\) algorithm.

We can fix all these issues with just two changes:

• Use a Node class that has links to both the previous and next nodes.
• Mark the head and tail with empty sentinel nodes. That way the head and tail will never be null, and every real node will have non-null next and previous nodes. No conditionals will be needed.

After making these changes, we'll reimplement get, contains, append, prepend, and remove. And maybe add an iterator.

TODO

You've got a few things to do before we meet again:

See you next time!

P.S. It's time for a haiku!