| Article Index |
|---|
| Doubly Linked List |
| Source Code |
| Documentation |
| Test cases and compatibility |
| All Pages |
DOUBLY LINKED LIST
A linked list is a linear data structure used to organize the data in the memory. As the name indicates, linked list is a list of items called the 'NODE' linked using pointers. A 'NODE' is a structure of List containing two or more fields called the 'data' field and 'address' field.
DOUBLY LINKED LIST:
The following figure shows a doubly linked list . The link is two way. Here every NODE contains two pointers LPTR(left pointer) and the RPTR (right pointer).
- LPTR points to the previous node.
- RPTR points to the next node.
The advantage of a doubly linked list is that traversal becomes easy.
Eg.
Doubly-linked vs. singly-linked:
- Double-linked lists require more space per node, and their elementary operations are more expensive; but they are often easier to manipulate because they allow sequential access to the list in both the directions.
- In particular, one can insert or delete a node given only that node's address. To do the same in a singly-linked list, one must have the previous node's address as well.
LINKED LIST OPERATIONS:
-
Inserting a node in the beginning when the list is empty:
new->lptr=NULL;
new->rptr=NULL;
new->element=x;//here, x=23
-
Inserting a node in the beginning when the list is not empty:
new->lptr=NULL;
new->rptr=l;
l->lptr=new;
Here, L is the left most node in the list and R is the right most node in the list. In this eg. L and R nodes are the same(since the list has only one element before insertion).
-
Inserting a node in the end:
new->rptr=NULL;
new->lptr=r;
r->rptr=new;
-
Inserting a node in the middle:
new->lptr=temp->lptr;
new->rptr=temp;
(temp->lptr)->rptr=new;
temp->lptr=new;
To insert a node in the middle, the list is traversed till the position where the node to be inserted is reached using a temp node. Here, the above code inserts the new node before the temp node.
-
Deleting a node in the beginning(when the list has only one element):
To delete a node in the beginning from the list having only one element or rather to delete the first(which is also the last)element in the list is very easy. For eg. to delete 23,
if(l->element==x) //here, x=23
{
if(l->rptr==NULL&&l->lptr==NULL)
{
l=r=NULL;//makes the list empty
}
}
-
Deleting a node in the beginning(when the list has more than one element):
For eg. Consider the doubly linked list shown below. To delete the node containing 45, we have to manipulate the left and right pointer of the next node(to the node to be deleted) so that the next node becomes the L node of the list.
(l->rptr)->lptr=NULL;
l=l->rptr;
Here, R node becomes the L node(rather the first node) of the list.
-
Deleting a node in the middle:
To delete a particular node in the middle,(here,temp node) the list is traversed till the node to be deleted is identified and then the required node is deleted as shown.As such deletion of a node(in the middle) is easier in a doubly linked list than in a singly linked list because the user needs to keep track of only one node-temp node(here). Whereas in a singly linked list one has to keep track of the prev and temp node.
(temp->lptr)->rptr=temp->rptr;
(temp->rptr)->lptr=temp->lptr;
-
Deleting a node in the end:
To delete a node in the end, traverse the list till the last node is reached using temp node. Now,temp node is made as the R node and the last node is deleted as shown below:
(temp->lptr)->rptr=NULL;
r=temp->lptr;
| < Prev | Next > |
|---|
