A doubly linked list is a specialized version of a single linked list. We know that a singly linked list is a collection of nodes, each of which has a data component and a reference to the next node. Like a singly linked list, a doubly linked list is also a collection of nodes. Each node in this is made up of a data component and two pointers. The first pointer points to the node before it, while the second pointer points to the node after it.
Graphical Depiction of a node in Doubly Linked List
Each node of doubly linked list consists of three components, namely, previous pointer, data, and next pointer whose graphical depiction is shown below:
Let’s, see an example of a doubly linked list in the diagram below:
The first node in a doubly linked list must always be pointed by the head. The first node’s previous field and the final node’s next field must always be NULL. We can traverse the doubly linked list in the forward and backward directions since it includes two pointers, previous, and next. This is the major benefit of a doubly linked list over a simply linked list.
Doubly Linked List Operations
We execute the following operations on a doubly linked list:
- Insertion
- Deletion
- Display
Insertion
The insertion operation in a double linked list can be done in one of three ways:
- Insertion at the beginning.
- Insertion at the end.
- Insertion at a specific point.
Insertion at the Beginning
We can use the instructions below to add a new node to the doubly linked list’s beginning:
Step 1: Make a newNode with the specified value and set newNode→previous to NULL.
Step 2: Verify that the list is empty (head == NULL).
Step 3: Assign NULL to newNode→next and newNode to head if it is empty.
Step 4: Assign head to newNode→next and newNode to head if it is not empty.
Insertion at the end
To add a new node to the end of the doubly linked list, perform the procedures below:
Step 1: Make a newNode with the specified value and set newNode→next to NULL.
Step 2: Verify that the list is empty (head == NULL).
Step 3: If it’s empty, set newNode→previous to NULL and newNode to head.
Step 4: If it isn’t empty, create a temp node pointer and initialize it with head.
Step 5: Continue shifting the temp to the next node in the list until it reaches the last node (or until temp→next equals NULL).
Step 6: Set newNode to temp→next and temp to newNode→previous.
Insertion at a specific point
To insert a new node after a node in a doubly linked list, perform the procedures below:
Step 1: Create a newNode using the supplied value.
Step 2: Verify that the list is empty (head == NULL).
Step 3: If it’s empty, set NULL to newNode→previous as well as to newNode→next and set newNode to head.
Step 4: If it’s not empty, create two node pointers, temp1 and temp2, and set temp1 to head.
Step 5: Continue advancing temp1 to its next node until it reaches the node where we want to put the newNode (until temp1 data equals location, where location is the node value).
Step 6: Check whether temp1 has reached the last node at all times. If you get to the last node, the message ‘Given node is not found in the list! Insertion is not possible!’ will appear and the function is terminated. If not, shift temp1 to the next node.
Step 7: Set temp1→next to temp2, newNode to temp1→next, temp1 to newNode→previous, temp2 to newNode→next and newNode to temp2→previous
Deletion
The deletion operation in a double linked list may be accomplished in three ways:
- Deletion from the top
- Deletion from the end
- Deletion of a Specific Node
Deletion from the top
To delete a node from the beginning of the doubly linked list, apply the instructions below:
Step 1: Check to see if the list is empty (head == NULL).
Step 2: If the list is empty, display the message ‘List is Empty! Deletion is not feasible’, and the function is terminated.
Step 3: Define a Node pointer ‘temp’ and initialize it with head if it is not empty.
Step 4: Verify that the list only has one node (temp previous→equals temp→next).
Step 5: Set head to NULL and remove temp (Setting Empty list conditions) if it is TRUE.
Step 6: If the answer is FALSE, place temp→next to the head, NULL to the head→previous, and remove temp.
Deletion from the end
To remove a node from the end of the doubly linked list, perform the instructions below:
Step 1: Check to see if the list is empty (head == NULL).
Step 2: If it’s empty, show ‘List is Empty! Deletion is not feasible’, and the function is terminated.
Step 3: Define a Node pointer ‘temp’ and initialize it with head if it is not empty.
Step 4: Verify that the list only includes one Node (temp→previous and temp→next are both NULL).
Step 5: If it’s TRUE, set head to NULL and remove temp. After that, exit the function. (Setting the criterion for an empty list)
Step 6: If the answer is FALSE, move the temp till it reaches the final node on the list. (until the temp→next equals NULL)
Deletion of a Specific Node
The instructions below can be used to remove a specific node from the doubly linked list:
Step 1: Check to see if the list is empty (head == NULL).
Step 2: If the list is empty, display the message ‘List is Empty! Deletion is not allowed’, and the function is terminated.
Step 3: If it isn’t empty, create a ‘temp’ Node pointer and initialize it with head.
Step 5: If the last node is reached, the message ‘Given node not found in the list! Deletion is not possible!’ is displayed and the function is terminated.
Step 6: If we’ve arrived at the specific node we want to remove, check to see if the list contains just one node.
Step 7: Set head to NULL and remove temp (free (temp)) if the list only includes one node and that is the node to be eliminated.
Step 8: If the list has more than one node, see if temp is the first node in the list (temp == head).
Step 9: If temp is the first node, shift the head to the next node (head = head→next), change the previous node’s head to NULL (head previous = NULL) and delete temp.
Step 10: If temp isn’t the first node in the list, make sure it’s the final one (temp→next == NULL).
Step 11: Set temp of previous of next to NULL (temp→previous→next = NULL) and remove temp (free (temp)) if temp is the final node.
Step 12: Set temp of previous of next to temp of next (temp→previous next = temp→next), temp of next of previous to temp of previous (temp→next→previous = temp→previous), and remove temp (free (temp)) if temp is not the first or final node.
Display
The items of a double linked list can be shown using the instructions below:
Step 1: Check to see if the list is empty (head == NULL).
Step 2: If it’s empty, display the message ‘List is Empty!’ and exit the method.
Step 3: If it isn’t empty, create a temp Node pointer and initialize it with head.
Step 4: Write ‘NULL←’ on the screen.