Delete Operations in Doubly Linked List using JavaScript
This article will demonstrate how to perform delete operations in a Doubly Linked List Data Structure using JavaScript. We will see different approaches to deleting elements from the Doubly Linked List.
Steps to Delete Element Node from Doubly Linked List
A doubly linked list has two pointers that link it with the previous and next node. So if we have to delete an element node we have to modify the linking pointers as shown.
To delete the Node we have to follow these steps:
- Traverse to the Node to be deleted and consider it the current node i.e. 3.
- Link the next pointer of the previous node i.e. 45 the next node of the current node
- previous.next => curr.next
- Link the prev pointer of the current node’s next i.e. 1 to the previous node i.e. 45.
- next.prev => previous
- Change the value of the current node to null to wipe it from the memory.
- curr => null
Types of Delete Operations in a Doubly Linked List
- Delete an element from the Start
- Delete an element from the End
- Delete an element at a certain position
- Delete an element using the element value
These operations will modify the Doubly Linked List as Shown below:
Consider this Doubly Linked List:
After removing the first element:
After removing middle element:
After removing Last element:
Type 1: Delete an element from the Start
To remove node from start we have to access and shift the head pointer:
- Consider if List is null then Output ‘List is Empty’. Else
- Let a curr variable and assign head value to it
- curr => head
- Now, move/ shift the head pointer one step
- head => head.next
- Make the prev link of the head as null
- head.prev => null
- Assign null to the curr value to remove the node from memory.
- curr => null
Example:
JavaScript
deleteStart() { if ( this .head == null ) { console.log( "List is empty" ); return ; } let curr = this .head; this .head = this .head.next; this .head.prev = null ; let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } |
Type 2: Delete an element from the End
To remove node from start we have to access and shift the tail pointer:
- Consider if List is null then Output ‘List is Empty’. Else,
- Let a curr variable and assign tail value to it.
- Now, move/ shift the tail pointer one step backward.
- tail => tail.prev
- Make the next link of the tail as null.
- tail.next => null
- Assign null to the curr value to remove the node from memory.
- curr => null
Example:
JavaScript
deleteEnd() { if ( this .head == null ) { console.log( "List is empty" ); return ; } let curr = this .tail; this .tail = this .tail.prev; this .tail.next = null ; let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } |
Type 3: Delete an element at a certain position
To remove node from start we have to traverse to target node and then delete it:
- Consider if List is null then Output ‘List is Empty’. Else,
- Check if Target index is 0, then use the steps above for removing element at start of call the function deleteStart. Else,
- Let a curr variable and assign head value to it.
- curr => head
- Now, Iterate n times to traverse and reach the target node.
- curr =>curr.next
- if current element become equal to null then return output “Not enough elements”
- After completetion of loop Check if current element is same as tail call the deleteEnd method. Else,
- Link the next pointer of the previous node the next node of the current node
- previous.next => curr.next
- Link the prev pointer of the current node’s next to the previous node.
- next.prev => previous
- Change the value of the current node to null to wipe it from the memory.
- curr => null
Example:
JavaScript
// Delete element at specific position deleteAt(pos) { // If list is null or empty if ( this .head == null ) { console.log( "List is empty" ); return ; } if (pos == 0) return this .deleteStart(); // Create curr pointer to traverse let curr = this .head; // Travesre until reach the reqired element while (pos > 0) { // curr = curr.next; pos -= 1; // If list do not contain enough elements if (curr == null ) return console.log( "Incorrect Position! Index does not exist." ); // Shift the poiter at every iteration curr = curr.next; } if (curr == this .tail) return this .deleteEnd(); // Create pointer for Elements before and after // the element is to be deleted let previous = curr.prev; let next = curr.next; // Remove element from given position previous.next = next; next.prev = previous; // To remove and display deleted data let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } |
Type 4: Delete an element using the element value
To remove node from start we have to traverse to target node and then delete it:
- Consider if List is null then Output ‘List is Empty’. Else,
- Check if Target valut is equal to head .data, then use the steps above for removing element at start of call the function deleteStart. Else,
- Let a curr variable and assign head value to it.
- curr => head
- Now, traverse the list until list is finish or reach the target node.
- curr =>curr.next
- if current element become equal to null then return output “Not enough elements”
- After completetion of loop, Check if current element is same as tail call the deleteEnd method. Else,
- Link the next pointer of the previous node the next node of the current node
- previous.next => curr.next
- Link the prev pointer of the current node’s next to the previous node.
- next.prev => previous
- Change the value of the current node to null to wipe it from the memory.
- curr => null
Example:
JavaScript
// To delete element using value deleteVal(val) { // If list is null or empty if ( this .head == null ) { console.log( "List is empty" ); return ; } if ( this .head.data == val) return this .deleteStart(); // Create curr pointer to traverse let curr = this .head; // Travesre until reach the reqired element while (curr && curr.data !== val) { // Shift the poiter at every iteration curr = curr.next; // If list do not contain enough elements if (curr == null ) return console.log( "Incorrect Value! Elements does not exist." ); } if (curr == this .tail) return this .deleteEnd(); // Create pointer for Elements before and after // the element is to be deleted let previous = curr.prev; let next = curr.next; // Remove element from given position previous.next = next; next.prev = previous; // To remove and display deleted data let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } |
Implementation of all delete operations
Example: In this example, we will insert some elements and show all of the above mentined approaches to delete element nodes.
JavaScript
// Doubly Linked list Node class Node { // Constructor to create a new node // next and prev is by default initialized as null constructor(val) { // To store the value this .data = val; // To link the next Node this .next = null ; // TO link the previous Node this .prev = null ; } } // Doubly Linked List class DoublyLinkedList { // Constructor to create a new linked list constructor() { // To contain the first item of the list this .head = null ; // To contain the last item of the list this .tail = null ; } // To check if the list is empty isEmpty() { if ( this .head == null ) return true ; return false ; } // Method to add item at the last of doubly linked list insertEnd(val) { // Create a temporary variable let temp = new Node(val); // If the list is empty link assign // new node to both head and tail if ( this .head == null ) { this .head = temp; this .tail = temp; } // else add item to the tail and shift tail else { temp.prev = this .tail; this .tail.next = temp; this .tail = this .tail.next; } console.log( "inserted at end" , val); } insertStart(val) { // Create a temporary variable let temp = new Node(val); // If the list is empty link assign // new node to both head and tail if ( this .head == null ) { this .head = temp; this .tail = temp; } // else add item to the head and shift head backward else { temp.next = this .head; this .head.prev = temp; this .head = temp; } console.log( "inserted at start" , val); } // method to insert value at given index insertAt(val, pos) { // If the index is 0 use insertStart // method to insert value as 0 position if (pos == 0) return this .insertStart(val); let index = pos; let curr = this .head; // Iterate to the element present // just before given index while (pos > 1) { pos -= 1; // If list do not contain enough elements if (curr === null ) return console.log( "Incorrect Position! Index does not exist." , pos, curr.data ); // Shift the pointer at every iteration curr = curr.next; } // After reaching required index create new node let temp = new Node(val); // Insert node at the required position temp.next = curr.next; temp.prev = curr; curr.next.prev = temp; curr.next = temp; console.log( "inserted at index" , index, "value" , val ); } // To traverse and display the list display() { // Check if the List is empty if (! this .isEmpty()) { // traverse the list using new current pointer let curr = this .head; console.log( "Required list is" ); while (curr !== null ) { // Display element console.log(curr.data); // Shift the current pointer curr = curr.next; } } } displayRev() { // Check if the List is empty if (! this .isEmpty()) { // traverse the list using new current pointer let curr = this .tail; console.log( "Required list in reverse order is" ); while (curr !== null ) { // Display element console.log(curr.data); // Shift the current pointer curr = curr.prev; } } } // Delete element at Start deleteStart() { if ( this .head == null ) { console.log( "List is empty" ); return ; } let curr = this .head; this .head = this .head.next; this .head.prev = null ; let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } // Delete element at End deleteEnd() { if ( this .head == null ) { console.log( "List is empty" ); return ; } let curr = this .tail; this .tail = this .tail.prev; this .tail.next = null ; let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } // Delete element at specific position deleteAt(pos) { // If list is null or empty if ( this .head == null ) { console.log( "List is empty" ); return ; } if (pos == 0) return this .deleteStart(); // Create curr pointer to traverse let curr = this .head; // Travesre until reach the reqired element while (pos > 0) { // curr = curr.next; pos -= 1; // If list do not contain enough elements if (curr == null ) return console.log( "Incorrect Position! Index does not exist." ); // Shift the poiter at every iteration curr = curr.next; } if (curr == this .tail) return this .deleteEnd(); // Create pointer for Elements before and after // the element is to be deleted let previous = curr.prev; let next = curr.next; // Remove element from given position previous.next = next; next.prev = previous; // To remove and display deleted data let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } // To delete element using value deleteVal(val) { // If list is null or empty if ( this .head == null ) { console.log( "List is empty" ); return ; } if ( this .head.data == val) return this .deleteStart(); // Create curr pointer to traverse let curr = this .head; // Traverse until reach the reqired element while (curr && curr.data !== val) { // Shift the poiter at every iteration curr = curr.next; // If list do not contain enough elements if (curr == null ) return console.log( "Incorrect Value! Elements does not exist." ); } if (curr == this .tail) return this .deleteEnd(); // Create pointer for Elements before and after // the element is to be deleted let previous = curr.prev; let next = curr.next; // Remove element from given position previous.next = next; next.prev = previous; // To remove and display deleted data let delValue = curr.data; curr = null ; console.log( "Removed element: " + delValue); } } // Create new Doubly Linked List const dll = new DoublyLinkedList(); // Add elements in the list dll.insertEnd(25); dll.insertEnd(27); dll.insertStart(17); dll.insertStart(29); dll.insertAt(65, 3); // Display the list dll.display(); // Delete element prestent at index 3 dll.deleteAt(3); // Delete element node from start dll.deleteStart(); // Delete element node from end dll.deleteEnd(); // Delete element node with input value dll.deleteVal(25); // Display the reverse list dll.display(); |
Output:
inserted at end 25
inserted at end 27
inserted at start 17
inserted at start 29
inserted at index 3 value 65
Required list is
29
17
25
65
27
Removed element: 65
Removed element: 29
Removed element: 27
Removed element: 25
Required list is
17
Contact Us