Linked Lists continued

A simple Linked List class might resemble:

class LinkedList
  {
  public:
    LinkedList();
    ~LinkedList();
    int insert_node(int);     /* inserts node with passed in key */
    int delete_node(int);     /* deletes node with passed in key */
    Node * find_node(int);    /* returns the address of the node with passed in key */

  private:
    Node *headPtr;            /* pointer to first node in the list */
  };

The constructor for the class simply initializes the headPtr to NULL.

The destructor for the class must free up the memory for every node in the list. The psuedocode might resemble:

ptr = headPtr
while (ptr != NULL)
  ptr2 = ptr->link
  free up the node pointed to by ptr
  ptr = ptr2
endwhile

Doubly Linked List

Up to this point, we have been dealing with a singly linked list, a linked list where each node has exactly one pointer.

Sometimes, we need the ability to move both forwards and backwards when processing a list. In order to accomplish this, we will use a doubly linked list.

Each node in this type of list will contain two pointers:

1. forward pointer - points to the next node in the list
2. backward pointer - points to the previous node in the list

The node class can now be changed to:

class DNode
  {
  public:
    DNode(int = 0, DNode * = NULL, DNode * = NULL);
    ...

  private:
    DNode *forPtr;            /* pointer to next node in the list */
    DNode *backPtr;           /* pointer to previous node in the list */
  };

What's the advantage(s) to a doubly linked list?