DOUBLE LINKED LIST
Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer).
In a singly linked list, we could traverse only in one direction, because each node contains address of the next node and it doesn't have any record of its previous nodes. However, doubly linked list overcome this limitation of singly linked list.
A sample node in a doubly linked list is shown in the figure.
In C, structure of a node in doubly linked list can be given as :
struct node
{
struct node *prev;
int data;
struct node *next;
struct node *head;
}
Memory Representation of a doubly linked list
Generally, doubly linked list consumes more space for every node and therefore, causes more expansive basic operations such as insertion and deletion. However, we can easily manipulate the elements of the list since the list maintains pointers in both the directions (forward and backward).
In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer points to the starting address 1. Since this is the first element being added to the list therefore the prev of the list contains null or -1. The next node of the list resides at address 4 therefore the first node contains 4 in its next pointer.
We can traverse the list in this way until we find any node containing null or -1 in its next part.
START is used to store the address of the first node. In this example, START = 1, so the first data is stored at address 1, which is H. Since this is the first node, it has no previous node and hence stores NULL or –1 in the PREV field. We will traverse the list until we reach a position where the NEXT entry contains –1 or NULL. This denotes the end of the linked list. When we traverse the DATA and NEXT in this manner, we will finally see that the linked list in the above example stores characters that when put together form the word "HELLO".
Operations on doubly linked list
The following operations are performed on double linked list
1) Insertion
Case 1: The new node is inserted at the beginning.
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node
2) Deletion
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The node after a given node is deleted.
Case 4: The node before a given node is deleted.
3) Searching
4) Traversing
INSERTION
Case 1:Inserting a Node at the Beginning of a Doubly Linked List
Suppose we want to add a new node with data 9 as the first node of the list. Then the following changes will be done in the linked list.
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
start -> prev = new_node;
new_node -> next = start;
new_node -> prev = NULL;
start = new_node;
return start;
}
CASE 2 :Inserting a Node at the End end of a Doubly Linked List
In order to insert a node in doubly linked list at the end, we must make sure whether the list is
empty or it contains any element.
EX:Suppose we want to add a new node with data 9 as the last node of the list. Then the following changes will be done in the linked list.
- In Step 6, we take a pointer variable PTR and initialize it with START.
- In the while loop, we traverse through the linked list to reach the last node. Once we reach the last node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node.
- Remember that the NEXT field of the new node contains NULL which signifies the end of the linked list. The PREV field of the NEW_NODE will be set so that it points to the node pointed by PTR.
{
struct node *ptr, *new_node;int num;printf("\n Enter the data : ");scanf("%d", &num);new_node = (struct node *)malloc(sizeof(struct node));new_node -> data = num;ptr=start;while(ptr -> next != NULL)ptr = ptr -> next;ptr -> next = new_node;new_node -> prev = ptr;new_node -> next = NULL;return start;
}
Case 3:Inserting a Node After a Given Node in a Doubly Linked List
Suppose we want to add a new node with value 9 after the node containing 3.
- In Step 5, we take a pointer PTR and initialize it with START. That is, PTR now points to the first node of the linked list.
- In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM. We need to reach this node because the new node will be inserted after this node.
- Once we reach this node, we change the NEXT and PREV fields in such a way that the new node is inserted after the desired node.
struct node *insert_after(struct node *start)
{
struct node *new_node, *ptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value after which the data has to be inserted : ");
scanf("%d", &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
new_node -> prev = ptr;
new_node -> next = ptr -> next;
ptr -> next -> prev = new_node;
ptr -> next = new_node;
return start;
Case 4:Inserting a Node Before a Given Node in a Doubly Linked List}
struct node *insert_before(struct node *start)
{
struct node *new_node, *ptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value before which the data has to be inserted : ");
scanf("%d", &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
new_node -> next = ptr;
new_node -> prev = ptr-> prev;
ptr -> prev -> next = new_node;
ptr -> prev = new_node;
return start;
}
Deletion:
In this we will see how a node is deleted from an already existing doubly linked list. We will take four cases and then see how deletion is done in each case.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The node after a given node is deleted.
Case 4: The node before a given node is deleted.
Case 1:Deleting the First Node from a Doubly Linked List
- In Step 1 of the algorithm, we check if the linked list exists or not. If START = NULL, then it signifies that there are no nodes in the list and the control is transferred to the last statement of the algorithm.
- However, if there are nodes in the linked list, then we use a temporary pointer variable PTR that is set to point to the first node of the list. For this, we initialize PTR with START that stores the address of the first node of the list.
- In Step 3, START is made to point to the next node in sequence and finally the memory occupied by PTR (initially the first node of the list) is freed and returned to the free pool.
struct node *delete_beg(struct node *start){
struct node *ptr;ptr = start;start = start -> next;start -> prev = NULL;free(ptr);return start;
Case 2:Deleting the Last Node from a Doubly Linked List}
To delete the last node from the linked list, then the following changes will be done in the linked list.
- In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list.
- The while loop traverses through the list to reach the last node. Once we reach the last node, we can also access the second last node by taking its address from the PREV field of the last node.
- To delete the last node, we simply have to set the next field of second last node to NULL, so that it now becomes the (new) last node of the linked list.
- The memory of the previous last node is freed and returned to the free pool.
struct node *delete_end(struct node *start)
{struct node *ptr;
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> prev -> next = NULL;
free(ptr);
return start;
}
Case 3:Deleting the Node After a Given Node in a Doubly Linked List
Suppose we want to delete the node that succeeds the node which contains data value 4. Then the following changes will be done in the linked list.
- In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the doubly linked list.
- The while loop traverses through the linked list to reach the given node. Once we reach the node containing VAL, the node succeeding it can be easily accessed by using the address stored in its NEXT field.
- The NEXT field of the given node is set to contain the contents in the NEXT field of the succeeding node.
- Finally, the memory of the node succeeding the given node is freed and returned to the free pool.
struct node *delete_after(struct node *start)
{struct node *ptr, *temp;int val;printf("\n Enter the value after which the node has to deleted : ");scanf("%d", &val);ptr = start;while(ptr -> data != val)ptr = ptr -> next;temp = ptr -> next;ptr -> next = temp -> next;temp -> next -> prev = ptr;free(temp);return start;}
- In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list.
- The while loop traverses through the linked list to reach the desired node. Once we reach the node containing VAL, the PREV field of PTR is set to contain the address of the node preceding the node which comes before PTR.
- The memory of the node preceding PTR is freed and returned to the free pool.
{
struct node *ptr, *temp;int val;printf("\n Enter the value before which the node has to deleted : ");scanf("%d", &val);ptr = start;while(ptr -> data != val)ptr = ptr -> next;temp = ptr -> prev;if(temp == start)start = delete_beg(start);else{
ptr -> prev = temp -> prev;temp -> prev -> next = ptr;
}free(temp);return start;
}
No comments:
Post a Comment