INTRODUCTION:              

This lesson presents a variation of singly-linked lists, a doubly-linked list.  There are occasions when it might be more efficient to have nodes with pointers going both ways - to the right and to the left.  Working with such lists involves twice as many internal pointers, as the diagrams will illustrate.

The key topic for this lesson is:

A.  Doubly-Linked Lists                        B.   Deleting from a Doubly-Linked List

VOCABULARY:                   DOUBLY-LINKED LISTS

DISCUSSION:                      

A.  Doubly-Linked Lists

1.   The node of a doubly-linked list will contain the information field(s) and two pointer fields.  One pointer will point to a previous node while the other pointer will point to the next node in the list.

2.   The following type definitions will be used in this student outline.

struct listNode

{

        int  value;

        listNode  *left;

        listNode  *right;

        listNode (int, listNode *, listNode *);

};

listNode::listNode (int tempValue, listNode *tLeft, listNode *tRight)

        : value(tempValue), left(tLeft), right(tRight)

{

        // all values initialized using initializer list

}

struct listType

{

        listNode  *first;

        listNode  *last;

};

//  note: this version does not use a typedef statement

3.   Here is a picture of a doubly linked list, declared as A of type listType.

4.   A NULL value must be placed at each end of the list to signify the end of the data structure.  In the diagram, a NULL is indicated with the diagonal line.

5.   A doubly-linked list should have two external pointers to access the data structure.  In the case above, A.first and A.last are the two entry points.

6.   A doubly-linked list can be traversed in either direction.

7.   Inserting values into an ordered doubly-linked list is a similar process to the algorithm used with a singly-linked list.  However, the number of pointer manipulations will double.

8.   The addition of a new node to a position between two existing nodes will require four pointer hookups.

B.   Deleting from a Doubly-Linked List

1.   There are some special cases to be aware of when deleting nodes from a doubly-linked list .  The diagram in section A.3. will be used for the illustration.

2.   Deleting the only node in a one-node list means that one or both of the external pointers are set to NULL.

3.   Deleting the first node would require A.first to be changed.

4.   Deleting the last node would require A.last to be changed.

5.   Deleting a node between two others will require two pointer  manipulations.

6.   The memory being deleted should be recovered by using the delete command.

SUMMARY/REVIEW:         This data structure, a doubly-linked list, is an extension of the basic linear-linked list.  The lab work will provide good practice in working with pointers and linked lists.

ASSIGNMENT:                    Lab Exercise L.A.35.1, Double

Test the deletion algorithms using (file3.txt).  After debugging code using this short data file, proceed to the general run output using (file10.txt).