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:

We can fix all these issues with just two changes:

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


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

Keep working on PA2. Delays bring grief.

See you next time!


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

When I get removed The whole world better feel it Or I'm coming back