Doubly Linked Lists

That sounds even harder than a linked list!

A doubly linked list is one where there are links from each node in both directions:

					current position
	Data		Data		Data		Data
								NULL
NULL

You will notice that each node in the list has two pointers, one to the next node and one to the previous one - again, the ends of the list are defined by NULL pointers. Also there is no pointer to the start of the list. Instead, there is simply a pointer to some position in the list which can be moved left or right.

The reason we needed a start pointer in the ordinary linked list is because, having moved on from one node to another, we can't easily move back ("The moving pointer doth write, and having writ, moves on!") so without the start pointer, we would lose track of all the nodes in the list that we have already passed. With the doubly linked list, we can move the current pointer backwards and forwards at will.

The nodes for a doubly linked list would be defined as follows:

struct node
 { string name;
   node *nxt;    // Pointer to next node
   node *prv;    // Pointer to previous node
 };

node *current;

current = new node;
current->name = "Fred";
current->nxt = NULL;
current->prv = NULL;

The nodes in this example only contain one piece of data - a person's name. A practical list would contain more variable declarations after string name. I have also included some code to declare the first node and set its pointers to NULL. It gives the following situation:

	current
	Fred
		NULL
NULL

We still need to consider the directions 'forward' and 'backward', so in this case, we will need to define functions to add a node to the start of the list (left-most position) and the end of the list (right-most position):

void add_node_at_start (string new_name)
 { // Declare a temporary pointer and move it to the start
   node *temp = current;
   while (temp->prv != NULL)
    temp = temp->prv;
   // Declare a new node and link it in
   node *temp2;
   temp2 = new node;
   temp2->name = new_name;  // Store the new name in the node
   temp2->prv = NULL;       // This is the new start of the list
   temp2->nxt = temp;       // Links to current list
   temp->prv = temp2;
 }

void add_node_at_end ()
 { // Declare a temporary pointer and move it to the end
   node *temp = current;
   while (temp->nxt != NULL)
    temp = temp->nxt;
   // Declare a new node and link it in
   node *temp2;
   temp2 = new node;
   temp2->name = new_name;  // Store the new name in the node
   temp2->nxt = NULL;       // This is the new start of the list
   temp2->prv = temp;       // Links to current list
   temp->nxt = temp2;
 }

Here, the new person's name is passed to the appropriate function as a parameter. I'll go through the function for adding a node to the right-most end of the list. The method is similar for adding a node at the other end. Firstly, a temporary pointer is set up and is made to march along the list until it points to last node in the list:

After that, a new node is declared, and the name is copied into it. The nxt pointer of this new node is set to NULL to indicate that this node will be the new end of the list.

The prv pointer of the new node is linked into the last node of the existing list.

The nxt pointer of the current end of the list is set to the new node.

Linked Lists	Top of the Page	Main Menu