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:
- 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:
package com.netSurfingZone.doublyLinkedList;
public class DoublyNode<T> {
private T data ;
private DoublyNode<T> next;
private DoublyNode<T> previous;
public DoublyNode(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public DoublyNode<T> getNext() {
return next;
}
public void setNext(DoublyNode<T> next) {
this.next = next;
}
public DoublyNode<T> getPrevious() {
return previous;
}
public void setPrevious(DoublyNode<T> previous) {
this.previous = previous;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((next == null) ? 0 : next.hashCode());
result = prime * result + ((previous == null) ? 0 : previous.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof DoublyNode))
return false;
DoublyNode other = (DoublyNode) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (next == null) {
if (other.next != null)
return false;
} else if (!next.equals(other.next))
return false;
if (previous == null) {
if (other.previous != null)
return false;
} else if (!previous.equals(other.previous))
return false;
return true;
}
@Override
public String toString() {
return "[data=" + data + "]";
}
}
Doubly Linked List :
package com.netSurfingZone.doublyLinkedList;
import com.study.doublyLinkedList.DoublyNode;
public class DoublyLinkedList<T>{
private int size;
private DoublyNode<T> root;
/**
* Delete the data from first occurrence
* @param data
*/
public void delete(T data) {
if(data==null) {
return;
}
boolean dataFound=false;
DoublyNode<T> currentNode=this.root;
while(!dataFound) {
if(currentNode.getData().equals(data)) {
DoublyNode<T> previousNode=currentNode.getPrevious();
DoublyNode<T> nextNode=currentNode.getNext();
if(previousNode !=null) {
previousNode.setNext(nextNode);
}
else {
this.root=nextNode;
}
if(nextNode !=null) {
nextNode.setPrevious(previousNode);
}
dataFound=true;
}
else {
currentNode=currentNode.getNext();
}
}
size--;
}
public void deleteByIndex( int index) {
if(this.root==null) {
return;
}
if(index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index is 0 , means needs to remove first node
if(index == 0) {
DoublyNode<T> secondNode = this.root.getNext();
if(secondNode!=null) {
secondNode.setPrevious(null);
}
this.root=secondNode;
}
// If index is last , means needs to remove last node
else if(index == this.size -1) {
DoublyNode<T> lastNode = getLastNode(this.root);
DoublyNode<T> secondLastNode = lastNode.getPrevious();
secondLastNode.setNext(null);
}
// Remove any index data
else {
DoublyNode<T> nodeToBeDelete = getNode(index);
DoublyNode<T> next = nodeToBeDelete.getNext();
DoublyNode<T> previous = nodeToBeDelete.getPrevious();
next.setPrevious(previous);
previous.setNext(next);
}
size--;
}
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (root == null) {
root = new DoublyNode<T>(data);
} else {
DoublyNode<T> newNode = new DoublyNode<T>(data);
DoublyNode<T> lastNode = getLastNode(root);
lastNode.setNext(newNode);
newNode.setPrevious(lastNode);
}
size++;
}
/**
* Add element at first.
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
DoublyNode<T> newNode = new DoublyNode<T>(data);
if (this.root != null) {
this.root.setPrevious(newNode);
newNode.setNext(this.root);
this.root = newNode;
} else {
this.root = newNode;
}
size++;
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
DoublyNode<T> newNode = new DoublyNode<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left node as newly created Node.
DoublyNode<T> rightNode = getNode(index);
DoublyNode<T> leftNode = rightNode.getPrevious();
leftNode.setNext(newNode);
newNode.setPrevious(leftNode);
newNode.setNext(rightNode);
rightNode.setPrevious(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
}
/**
* Returns the Doubly Node at given index
* @param index
* @return
*/
private DoublyNode<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.root;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.root);
}
int pointer = 0;
DoublyNode<T> pointerNode = this.root;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
/**
* Returns last node of given doubly node
* @param node
* @return
*/
private DoublyNode<T> getLastNode(DoublyNode<T> node) {
if(node !=null) {
DoublyNode<T> lastNode = node;
if (lastNode.getNext() != null) {
return getLastNode(lastNode.getNext());
} else {
return lastNode;
}
}
return null;
}
/**
* Returns next consecutive node of given doubly node
* @param node
* @return
*/
private DoublyNode<T> next(DoublyNode<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}
public int size() {
return this.size;
}
public void clear() {
this.root = null;
this.size = 0;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((root == null) ? 0 : root.hashCode());
result = prime * result + size;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof DoublyLinkedList))
return false;
DoublyLinkedList other = (DoublyLinkedList) obj;
if (root == null) {
if (other.root != null)
return false;
} else if (!root.equals(other.root))
return false;
if (size != other.size)
return false;
return true;
}
@Override
public String toString() {
String represent = "[";
DoublyNode<T> nextNode = this.root;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
}
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 :
package com.netSurfingZone.dto;
public class Item {
private Integer itemId;
private String itemName;
private Double price;
public Item(Integer itemId, String itemName, Double price) {
super();
this.itemId = itemId;
this.itemName = itemName;
this.price = price;
}
public Integer getItemId() {
return itemId;
}
public void setItemId(Integer itemId) {
this.itemId = itemId;
}
public String getItemName() {
return itemName;
}
public void setItemName(String itemName) {
this.itemName = itemName;
}
public Double getPrice() {
return price;
}
public void setPrice(Double price) {
this.price = price;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemName=" + itemName + ", price=" + price + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((itemId == null) ? 0 : itemId.hashCode());
result = prime * result + ((itemName == null) ? 0 : itemName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Item))
return false;
Item other = (Item) obj;
if (itemId == null) {
if (other.itemId != null)
return false;
} else if (!itemId.equals(other.itemId))
return false;
if (itemName == null) {
if (other.itemName != null)
return false;
} else if (!itemName.equals(other.itemName))
return false;
return true;
}
}
Now, we will test the delete operations written above in double linked list by adding some items and later remove items.
package com.netSurfingZone.doublyLinkedList;
import com.netSurfingZone.dto.Item;
public class TestDoublyLinkedList {
public static void main(String[] args) {
DoublyLinkedList<Item> doublyLinkedList=new DoublyLinkedList<>();
Item item1=new Item(101, "DELL Latitude 5647", 300.0);
Item item2=new Item(102, "Mac Book", 1000.0);
Item item3=new Item(103, "Mac Book Pro", 2000.0);
Item item4=new Item(104, "HP Elitebook", 700.0);
System.out.println(item1.getItemName() +" added.");
doublyLinkedList.add(item1);
System.out.println(item2.getItemName() +" added.");
doublyLinkedList.add(item2);
System.out.println(item3.getItemName() +" added.");
doublyLinkedList.addAtFirst(item3);
System.out.println(item4.getItemName() +" added.");
doublyLinkedList.add(item4);
System.out.println(item2.getItemName() +" added again.");
doublyLinkedList.add(item2);
System.out.println("");
System.out.println("***Delete item "+item2.getItemName()+ " by passing object.It will delete first occurrence. ***");
doublyLinkedList.delete(item2);
System.out.println("Doubly linked list after removing " +item2.getItemName());
System.out.println(doublyLinkedList);
System.out.println("");
System.out.println("***Delete item by passing index = 2***");
doublyLinkedList.deleteByIndex(2);
System.out.println("Doubly linked list after removing item at index =2" );
System.out.println(doublyLinkedList);
}
}
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)
