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
After Reversing 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:
- Declare 3 node variables , current, previous, next and initialize current=root node.
- Repeat steps 3, 4 and 5 till current != null.
- next= next node of current node & previous=previous node of current node.
- reverse the both pointers next & previous. next node of current node =previous & previous node of current node =next.
- assign current = previous node of current
- 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:
Now, we will see the algorithm and execution process of reverse a doubly linked list using stack. First, push all the nodes of doubly linked list starting from root node to stack and after pushing all the nodes of the doubly linked list, root of the doubly linked list will be at very bottom and top will have the end node of doubly linked list. Basically, Stack reverse the order of insertion. Now, pop the nodes from top of the stack and keep adding to the root node to form doubly linked list. Similar algorithm and execution process are written for Singly Linked List . Please refer and try to implement the similar logic for doubly linked list. Please leave your comments in case of any issue/discussions.
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;
import com.study.doublyLinkedList.DoublyNode;
public class DoublyLinkedList<T>{
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--;
}
/**
* 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;
}
}
Testing:
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.add(item3);
System.out.println(item4.getItemName() +" added.");
doublyLinkedList.add(item4);
System.out.println("");
System.out.println("Original Doubly Linked List : " +doublyLinkedList);
doublyLinkedList.reverse(true);
System.out.println("");
System.out.println("Doubly Linked List after reversal: " +doublyLinkedList);
}
}
Output:
*************************************************************************************************************
DELL Latitude 5647 added.
Mac Book added.
Mac Book Pro added.
HP Elitebook added.
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]]]
*************************************************************************************************************
Hope you like this post. Please leave your comments/suggestions.
You may like:
Introduction of Doubly Linked List(DLL)
Delete Operation in Doubly Linked List
Iterator For Doubly Linked List
