Re: Help: my list adt is broken

[schwarza@gdls.com]

Chris;

There are exactly two (2) ways of implementating a doubly-linked
list (unless I become reasonable - nah, never happen):

[1] Each end of the doubly linked list terminates in a null and
    the list head points to the first element of the list:

    ptr ->   null <- cell -> ... <- cell -> null

[2] There is a unique list header which points to both the list
    header and tail (and is itself a list cell) with a pointer
    to the header cell being the external 'name' of the list:

    ptr ->   unique list header cell
                                top   -> <- cell -> ... <- cell -> .
                                bot                     ->         |
                                 ^                                 |
                                 |                                 |
                                 .---------------------------------.

I prefer two to one (2 to 1) but that is not material.

Now, to do any list switching the order of operations is very, very
important. If you don't do things in the proper order, carefully,
things get fouled up fast. So let's see:

Suppose we do the following:

   1. Save the left pointer of the first cell.
   2. Put into the left pointer of the first cell, the left pointer
      of the 'new cell'.
   3. Put into the left pointer of the second cell, the (saved) left
      pointer of the first cell.
   4. Put into the right pointer of the cell pointed to by the second
      cell a pointer to the current cell. And here is where the two
      implementations differ. For [1], it is possible for the left
      pointer of the second cell to be null. For [2] there is no such
      worry (it works in all cases).
   5. Repeat for the right pointers.
   6. If you have implemented [1], then some fixup is required:
      a. If the second cell is the list top, then the 'ptr' must
         be changed to the first cell (the new list top).
      b. If the first cell is the list top then the contrawise
         operation has to be done.

And now for the kicker. This is not a place to get your homework
assignments done. Having said that, let me amplify a comment concerning
debugging (instrumenting your code with output statements). Code for
failure!! Assume nothing (NOTHING) will work correctly and provide
print statements accordingly. It's easier than asking questions. And,
allow the print statements to be turned on or off, as in:

   if this_is_some_kind_of_debug_thing then PRINT;

Disappointingly you will find that the volume of code required to code
for failure is larger than that for your actual classroom assignments.
Encouragingly you will shine amongst your peers because you will be able
to identify your errors quickly and solve them even more quickly.

art

PS: If any of you are real, real old programmers then [2] is SLIP
(Symmetric
    LIst Processor) from way, way back (circa 1960).  I believe that Eliza
    was programmed in SLIP and in FORTRAN at MIT.

PSST: I am a real, real old programmer and still have copies of the
original
    SLIP implementation circa 1964 at the University of Wisconsin; in
FORTRAN.