# Reverse a Doubly Linked list

In this post, we will see how to reverse a doubly linked list by reversing the reference pointers of nodes using recursion. Also there is a popular way to reverse a linked list using Stack. The basic algorithmsÂ are same for both reversal of Singly Linked List and Doubly Linked List. Only the difference is, in case of doubly linked list, we need to reverse the two pointers next and previous.

Example:

Â Â Â Â  Original Doubly Linked List

Reverse a Doubly Linked List By Reversing The Reference Pointers:

We will see the algorithm and execution process of reverse a doubly linked list by reversing the reference pointers. We could achieve this by two ways. 1. Traverse through the each node using while loop and reverse the reference pointers. 2. Traverse through the each node using Recursion and reverse the reference pointers. Core logic for both the process is same as we just need to reverse the reference pointers of each nodes.

Algorithm:

1. Declare 3 node variables , current,Â  previous, next and initialize current=root node.
2. Repeat steps 3, 4 and 5 till current != null.
3. next= next node of current node & previous=previous node of current node.
4. reverse the both pointers next & previous. next node of current node =previous & previous node of current node =next.
5. assign current = previous node of current
6. At last, set the root node as previous node of previous means root node will be the last node.

Execution process:

Reverse a Doubly Linked List Using Stack:

Below is the code written for reversal of doubly linked list using recusion.

```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.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;
}

}```
```package com.netSurfingZone.doublyLinkedList;

private int size;
private DoublyNode<T> root;

public void reverse(boolean recursive) {
if(this.root==null) {
return;
}
if(!recursive) {
DoublyNode<T> current=this.root;
DoublyNode<T> next=null;
DoublyNode<T> previous=null;
while(current!=null) {
next=current.getNext();
previous=current.getPrevious();
//swip next with previous and previous with next
current.setNext(previous);
current.setPrevious(next);
current=current.getPrevious();
}
this.root=previous.getPrevious();
}
else {
this.root=reverseByRecursion(this.root);
}
}

private DoublyNode<T> reverseByRecursion(DoublyNode<T> currentNode) {
DoublyNode<T> current=currentNode;
DoublyNode<T> next=null;
DoublyNode<T> previous=null;
if(current!=null) {
next=current.getNext();
previous=current.getPrevious();
//swip next with previous and previous with next
current.setNext(previous);
current.setPrevious(next);
current=current.getPrevious();
if(current!=null) {
return reverseByRecursion(current);
}
else {
return previous.getPrevious();
}
}
return null;
}

/**
* 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;
}
}
```

Testing:

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

Output:

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

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

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

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

You may like: