CS217 Precept 4: Linked Lists
Before we implement a linked list, we need to stand back and decide
how external code is supposed to interface with it. In C,
that means writing the header (.h) file.
In precept, we'd do this on the board then take a closer look at
an actual header file. If you're reading
this afterward, write a header file down on paper first, then
follow the link to my version.
The wonderful thing about linked lists is how many different methods
have been invented to implement them. Data structure design involves
a lot more than a C struct definition.
- Do lists have a header node?
- Are they circular?
- If not circular, is there a tail node or a NULL?
- Do we store the contents in sorted order?
In precept, we're going to draw lots of pretty pictures on the board
kinda like this:
and, you're going to have to explain how the list insertion code
is supposed to work in each case. Don't call us, we'll call on you.
Double-linked lists are remarkably hard to get right. Let's say you
want to insert an element in order, and you even know exactly where
it's supposed to go:
Seems pretty complicated, huh? The general rule is to initialize fully
the newly allocated node first, then edit the list to point
at your new node. This prevents you from forgetting a pointer.
But, there are special cases for you to worry about, even in
``simple'' single-linked lists. What happens
if the list is currently empty? Do you need a special case for the
first node you insert?
Dan Wallach, CS Department, Princeton University
Last modified: Thu Feb 29 15:03:02 EST 1996