Doubly Linked List
So far you have studied singly linked lists and their variation circular linked lists. One of the most striking disadvantages of these lists is that the inability to traverse the list in the backward direction. In most of the real world applications it is necessary to traverse the list both in forward direction and backward direction. The most appropriate data structure for such an application is a doubly linked list.
A doubly linked list is one in which all nodes are linked together by multiple number of links which help in accessing both the successor node and predecessor node form the given node position. It provides bi-directional traversing.
Each node in a doubly linked list has two link fields. These are used to point to the successor node and predecessor nodes.
The LEFT link points to the predecessor node and the REGHT link points to the successor node. The structure definition for the above node on C is as follows.
Struct node;
{ int num;
Sturuct node * prev;
Struct node * next;
};
Typedef struct node NODE;
Let us look at the insertion and deletion operations to be performed on a doubly linked list
Inserting A Node at the Beginning
An algorithm to insert a new node at the beginning of a doubly linked list is given below.
1. Allocate memory for the new node.
2. Assign value to the data field of the new node.
3. Assign LEFT and RIGHT links to NULL
4. Make the REGHT link of the new node to point to the head node of the list and make LEFT link of the head node to point to the new node.
5. Finally reset the head pointer. That is making it to point to the new node which has inserted at the beginning.
Viod insert_at_beginning (int item)
{
Node *ptr;
Ptr = (node*) malloc (sizeof (node));
Ptr info = item
If (head = = (node *) NULL)
}
Ptr prev = ptr next = (node *) NULL;
Head = tail = ptr;
}
Else
{
Ptr prev = (node*) NULL;
ptr next = head;
head prev = ptr;
head = ptr;
}
}
Inserting A Node at the End
An algorithm to insert a node at the end of a doubly linked list is given below
1. Allocate memory for the new node.
2. Assign value to the data field of the new node.
3. Set the LEFT and RIGHT links to the new node.
4. If the list is not empty then traverse the list till the last and make the RIGHT link of the last node to point to the new node and LEFT link of the new node to point to the last node.
Void insert_at_tail (int item)
{
Node * ptr;
Ptr = (node*) malloc (sizeof (node));
Ptr info = item;
If (tail = = (node*) NULL)
{ ptr prev = ptr next = (node*) NULL;
Head = tail = ptr;
}
Else
{
Ptr next = (node*) NULL;
Ptr prev = tail;
Tail next = ptr;
Tail = ptr ;
}
}
Data Structure & Algorithms Assignment Help, Live Experts
Struggling with data structure problems? Data structure subject is quite tough to learn? Need quick assistance in data structure questions? ExpertsMind.com is right place for you where your search ends, We at ExpertsMind offer online data structure assignment help, data structure homework help and data structure and algorithms question's answers by best online support by qualified tutors.
ExpertsMind.com - Doubly Linked List Assignment Help, Doubly Linked List Homework Help, Doubly Linked List Assignment Tutors, Doubly Linked List Solutions, Doubly Linked List Answers, Linked Lists Assignment Tutors