Delete operation in doubly linked list

Delete a node in a doubly linked list is more efficient than the same operation in singly linked list. In this post, we will see the different delete operation in doubly linked list. Basically, we will have two methods, delete and deleteByIndex.

To add some data to doubly linked list, we need other supporting methods to add the elements to doubly linked list, so we will use the same code written in previous post to add some elements. Below is the algorithm and execution process for deleting a node from a doubly linked list.

Methods:

  1. delete(T data) : Input of this method can be any object of generic type T. This method will delete the first occurrence of object from given doubly linked list, if data is present otherwise no change in doubly linked list.[Try Yourself]

       Algorithm:

  • Declare a variables “currentNode” and initialize with root node.
  • Repeat the below steps till input data found at currentNode.
  • If data on currentNode is equal to input data, link previous node and next node.To link previous and next node, set previousNode.next(nextNode) and nextNode.previous(previousNode). Reduce the size of the doubly linked list by 1.
  • If data on currentNode is not equal to input data, update the currentNode = currentNode.next.

       Execution Process:

 

2.  deleteByIndex(int index) : This method will delete the element at particular input index. There will be three cases. First case, if input index is 0 , then we just need to update the previous node of second node( next to root node) as NULL and set root node as second node. Second case, if input index is size-1 (delete last element), then update the next node of second last node of doubly linked list as NULL. Third case, if input index is between 1 to size-2, then see the below algorithm and execution process to delete node.[Try Yourself]

      Algorithm:

  • Declare a variable nodeToBeDeleted and assign the value as doubly node at input index .
  • Get the next and previous nodes of nodeToBeDeleted (next , previous).
  • Set the previous node of next as previous.
  • Set the next node of previous ad next.
  • decrease the size of doubly linked list by 1.

      Execution Process:

Below is the implementation of these two algorithms.

Doubly Node:

 

Doubly Linked List :

We will create a DTO class called Item.java to add the item to the doubly linked list and later perform the delete operations. As per the equals() and hashCode() implementation of Item.java, if two items have same itemId and itemName , then those two items are equals.

Item :

 

Now, we will test the delete operations written above in double linked list by adding some items and later remove items.

 

Result:

DELL Latitude 5647 added.

Mac Book added.

Mac Book Pro added.

HP Elitebook added.

Mac Book added again.

***Delete item Mac Bookby passing object.It will delete first occurrence. ***

Doubly linked list after removing Mac Book

[DoublyNode [data=Item [itemId=103, itemName=Mac Book Pro, price=2000.0]],DoublyNode [data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]],DoublyNode [data=Item [itemId=104, itemName=HP Elitebook, price=700.0]],DoublyNode [data=Item [itemId=102, itemName=Mac Book, price=1000.0]]]

***Delete item by passing index = 2***

Doubly linked list after removing item at index =2

[DoublyNode [data=Item [itemId=103, itemName=Mac Book Pro, price=2000.0]],DoublyNode [data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]],DoublyNode [data=Item [itemId=102, itemName=Mac Book, price=1000.0]]]

************************************************************************************************************************************************

 

Hope you like this post. Please leave your comments/suggestions 🙂

 

You may link:

Introduction of Doubly Linked List(DLL)

Delete Operation in Doubly Linked List

Reverse a Doubly Linked List

Iterator For Doubly Linked List

Top