Doubly Linked Lists

A doubly linked list is similar to a simple linked list in that each node contains a pointer to the next node (or to NULL). In addition, however, each node contains a pointer to the previous node:

[doubly linked list]

Just as the last node points forward to NULL, the first node points backward to NULL.

As with simple linked lists, we could have omitted LAST-P. If we didn't have it, we could still find the end of the list by traversing it from the beginning.

With a doubly linked list, however, we could just as well dispense with FIRST-P. If we still had LAST-P, we could find the beginning of the list by traversing it backwards from the end. We could even keep a pointer to a node somewhere in the middle, and traverse the list in either direction as needed.

Typically an application will designate one end of the list as the first node, and the other end as the last node. The structure itself, however, is inherently symmetrical.

The Example, Modified

In our example for simple linked lists, we managed a list of names and telephone numbers. For a doubly linked list we can use the same structure, but with an additional pointer TN-PREV-P to point to the previous node: 
 01  TN-NODE.
     05  TN-NEXT-P        USAGE IS POINTER.
     05  TN-PREV-P        USAGE IS POINTER.
     05  TN-WTN           PIC X(10).
     05  TN-NAME          PIC X(15).

Operations

Given this infrastructure, we can perform all the same operations as with simple linked lists: prepend, append, insert, and all the rest. The same principles apply, though these pages will not illustrate them in detail.

The backwards pointers makes some operations somewhat more complicated, because we must maintain two sets of pointers instead of one.

Other operations are simpler. For example, if we need to remove a node from the list, we can immediately find the nodes on either side and stitch them together. We don't have to traverse the list from the beginning just to find the previous node.

Anything you can do with a simple linked list, you can also do with a doubly linked list, and vice versa. Choose between them according to the operations you need to perform and how often you perform them.

[home]COBOL Home [crane]Data Structures