Various operation performed on the doubly linked list. Doubly Linked Lists

Explain various operation performed on the doubly linked list. Doubly Linked Lists

That sounds even harder than a linked list! Well, if you've mastered how to do singly linked lists, then it shouldn't be much of a leap to doubly linked lists A doubly linked list is one where there are links from each node in both directions: 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 that 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, 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.

Creating Doubly Linked Lists

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

char name[20];

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;

We have also included some code to declare the first node and set its pointers to NULL. It gives the following situation:

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).

Adding a Node to a Doubly Linked List

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 name is passed to the appropriate function as a parameter. We'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.