COSC 350: Data Structures
Feb. 23, 2009

Linked Lists Con't

The key to mastering link-list operations understanding the process well enough to draw the sequence of box-pointer diagrams to model the process. Key in mind that the order of the operations is often crucial. Watch out for lost links!

Head and Tail Conventions

(See table 3.1, Page 102 in your text)
Circular Lists
Null tail
Using dummy nodes for head and tail

Drawing Box-Pointer Diagrams

When drawing box-pointer diagrams, you will have one set of drawing for each case.
Start with initial condition drawing without any changes.
Then give one drawing for each step.
Lable each step with corresponding code.
This may seem tedious at first, but it will insure that you clearly identify each step and minimize the chance you will overlook any important steps.

Special Lists

Circular lists
Ordered vs. unordered lists
Doubly-linked lists

Homework

Wednesday: Draw out the box-pointer diagrams for "insert t after x" and "remove t after x" for
1. "Head pointer, null tail" and
2. "Dummy head and tail nodes"

Friday: Reimplement the linked-list class presented in class:

1. using dummy head and tail nodes
2. as a double-linked list

(Friday's assignment counts as two assignments.)

This page was created by Joe Sloan.
It was last modified on or after: 23 February 2009
Send mail to: sloanjd@wofford.edu