After reading this article you should be able to answer the following questions.
- What are doubly linked lists?
- How doubly linked lists are implemented?
- What are the applications for doubly linked lists?
- How doubly linked lists are different than singly-linked lists?
Introduction
The following are problems with singly linked lists:
- A singly linked list allows traversal of the list in only one direction.
- Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
- If the link in any node gets corrupted, the remaining nodes of the list become unusable.
These problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. When such a link is added to every node of a list, the corresponding linked list is called a doubly linked list. Therefore, a doubly linked list is a linked list in which every node contains two links, called left link and right link, respectively.
The left link of the node points to the previous node, whereas the right points to the next node. Like a singly linked list, a doubly linked list can also be a chain or it may be circular with or without a header node. If it is a chain, the left link of the first node and the right link of the last node will be NULL, as shown in Figure 1.
Figure 1 : Doubly Linked List as a chain
If it is a circular list without a header node, the right link of the last node points to the first node. The left link of the first node points to the last node, as shown in Figure 2
Figure 2 : Doubly Linked List maintained as circular list
If it is a circular list with a header node, the left link of the first node and the right link of the last node point to the header node. The right link of the header node points to the first node and the left link of the header node points to the last node of the list, as shown in Figure 3.
Figure 3 : A doubly linked list maintained as a circular list with a header node.
Therefore, the following representation is required to be used for the nodes of a doubly linked list.
struct dnode {
int data;
struct dnode *left,*right;
};
Inserting into a doubly linked list is done as :
struct dnode *insert(struct dnode *p, struct dnode **q, int n)
{
struct dnode *temp;
/* if the existing list is empty then insert a new node as the
starting node */
if(p==NULL)
{
p=(struct dnode *)malloc(sizeof(struct dnode)); /* creates new
node data value
passed as parameter */
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p->data = n;
p-> left = p->right =NULL;
*q =p;
}
else
{
temp = (struct dnode *)malloc(sizeof(struct dnode)); /* creates
new node using
data value passed as
parameter and puts its
address in the temp
*/
if(temp == NULL)
{
printf("Error\n");
exit(0);
}
temp->data = n;
temp->left = (*q);
temp->right = NULL;
(*q)->right = temp;
(*q) = temp;
}
return (p);
}
