# 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:

```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 + "]";
}

}
```

```package com.netSurfingZone.doublyLinkedList;

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--;
}
/**
*
* @param 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++;
}

/**
*
* @param 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
* 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) {
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
} 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;
return false;
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 static void main(String[] args) {

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("");

System.out.println("***Delete item "+item2.getItemName()+ " by passing object.It will delete first occurrence. ***");
System.out.println("Doubly linked list after removing " +item2.getItemName());
System.out.println("");

System.out.println("***Delete item  by passing index = 2***");
System.out.println("Doubly linked list after removing item at index =2" );
}
}
```

Result:

***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]]]

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