Class 41: Extending Linked Lists: Doubly- and Circularly-Linked Lists

Held: Monday, 14 April 2003

Summary: We consider some data structure design decisions that will ease the implementation of certain operations.

Related Pages:

• EBoard.
• list.h.
• list.c.

Assignments:

• Read Gries 12.

Overview:

• Implementing delete.
• Doubly-linked lists.
• Detour: ADTs vs. Data Structures.
• Circularly-Linked lists.

Implementing delete

• We have a variety of kinds of deletion.
  • deleteCurrent deletes the node under the cursor.
  • delete deletes all copies of the same value.
• Suppose we want to implement a deleteCurrent operation.
• Design decision: Should it delete the contents, too?
  • Probably not.
• Implementation problem: How do we fix the pointers?
• See discussion for more details.

Doubly-Linked Lists

• One solution to this problem is to give each node a previous pointer as well as a next pointer.
• Finding the previous node is now quite easy.
• We now have to be careful to update both links in all the operations (insert, delete, etc.)
• We also have more overhead.
• Are there other disadvantages?

Detour: ADTs vs. Data Structures

• We're beginning to hit a problem in the design of C.
• The header file traditionally gives:
  • The struct
  • The declarations of the key procedures that go with the struct.
• But our experience suggests that you need to separate the interface from the implementation.
  • If your experience doesn't suggest that, talk to me.
• How can we write a real ADT, one that just gives a list of operations?
  • We could decide that real C programmers don't write ADT's.
  • We could design list.h so that it assumes that the list struct is defined elsewhere.
  • We could build a header file generator.
  • ...

Circularly-Linked lists

• As you may have noted in our discussion of doubly-linked lists, one problem we have is lots and lots of special cases.
• Here's a cool solution to that problem:
  • Add one special node that's always there (you never delete this node).
  • Make the next element of the last node this special node.
  • Make the prior element of the first node this special node.
• This strategy eliminates special cases.
• We can also make a circularly linked list without the special node.