Reverse a Singly Linked List

By
PRAKASH BADAL
-

In previous post, we saw the methods to get the data based on index and get the index of data in linked list.In this post, we will see the algorithm to reverse a singly linked list and implement in JAVA.

Examples:

1. Original linked list : 1->2->3->4->5->NULL

Reversed linked list : 5->4->3->2->1->NULL

2. Original linked list : 1->NULL

Reversed linked list : 1->NULL

3. Original linked list : NULL

Reversed linked list : NULL

We can reverse a singly linked list by reversing the pointers in reverse direction. This is very common algorithm to reverse the singly linked list.Apart from this, we will see the other algorithm where we will reverse a singly linked list using Stack.

By reversing the pointers : See the below algorithm and their execution process.

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
  4. next node of current node = previous . Here, we are reversing the pointer.
  5. current=next
  6. assign the root node as previous , root=previous.

Execution process:

Reverse using Stack  : Now, we will see the algorithm to reverse a singly linked list using Stack.See the below steps and execution process.

Algorithm:

Put the nodes of linked list starting from root node to Stack.

  1. Create an object of Stack of Node<T> . Create node variable,  current and assign the root node.
  2. Repeat steps 3 and 4 till current node is not null.
  3. push the current node to stack. stack.push(current).
  4. assign current as next node of current node. current=next node of current node.

Now, Stack has all the nodes where root node at bottom and rear node at top.Clear the linked list and pop the nodes from stack and update the pointers.

  1. clear the linked list by updating the reference of root as null. root=null
  2. Pop the top node from stack and assign it to root. root=stack.pop().
  3. Create 2 node variables, previous and current and assign as root node.
  4. Repeat steps 5, 6 and 7 till stack is not empty.
  5. pop the node from stack and assign to current. current=stack.pop().
  6. Set next node of previous node as current.
  7. previous=current
  8. Finally, set next node of previous node as NULL. Here previous will be the last node in linked list.

Execution process:

Now, we will have these two algorithm implementation in JAVA. [Try Yourself]

package com.study.singlyLinkedList;

public class Node<T> {

	private T data ;
	
	private Node<T> node;

	public Node(T data) {
		this.data = data;
	}

	public Node<T> getNode() {
		return node;
	}

	public void setNode(Node<T> node) {
		this.node = node;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	@Override
	public String toString() {
		return data+"" ;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((data == null) ? 0 : data.hashCode());
		result = prime * result + ((node == null) ? 0 : node.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof Node))
			return false;
		Node other = (Node) obj;
		if (data == null) {
			if (other.data != null)
				return false;
		} else if (!data.equals(other.data))
			return false;
		if (node == null) {
			if (other.node != null)
				return false;
		} else if (!node.equals(other.node))
			return false;
		return true;
	}
	
	
}

package com.study.singlyLinkedList;

import java.util.Stack;

public class SinglyLinkedList<T> {
	private int size = 0;
	private Node<T> node;
	
	/**
	 * Reverse the linked list by reversing the pointers in reverse direction
	 */
	public void reverse() {
		Node<T> current=this.node;
		Node<T> previous=null;
		Node<T> next=null;
		while(current !=null) {
			next = current.getNode();
			current.setNode(previous);
			previous=current;
			current=next;
		}
		this.node=previous;
	}
	/**
	 * Reverse the linked list using stack
	 */
	public void reverseUsingStack() {
		// Push all node  to Stack starting from root
		Stack<Node<T>> stack=new Stack<Node<T>>();
		Node<T> currentNode=this.node;
		while(currentNode !=null) {
			stack.push(currentNode);
			currentNode=currentNode.getNode();
		}
		// clear the linked list.
		this.node = null;
		this.size = 0;
		//Pop the data from Stack and add it to linked list
		if(!stack.empty()) {
			Node<T> rootNode=stack.pop();
			Node<T> previousNode=rootNode;
			currentNode=rootNode;
			while(!stack.empty()) {
				currentNode = stack.pop();
				previousNode.setNode(currentNode);
				previousNode=currentNode;
			}
			previousNode.setNode(null);
			this.node=rootNode;
		}
	}
	
	/**
	 * Add element at last.
	 * 
	 * @param data
	 */
	public void add(T data) {
		if (data == null) {
			return;
		}
		if (node == null) {
			node = new Node<T>(data);
		} else {
			Node<T> newNode = new Node<T>(data);
			Node<T> lastNode = getLastNode(node);
			lastNode.setNode(newNode);
		}
		size++;
	}

	
	/**
	 * Add element at first. set the newly created node as root node
	 * 
	 * @param data
	 */
	public void addAtFirst(T data) {
		if (data == null) {
			return;
		}
		Node<T> newNode = new Node<T>(data);
		if (this.node != null) {
			newNode.setNode(this.node);
			this.node = newNode;
		} else {
			this.node = 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) {
			Node<T> newNode = new Node<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 nose as newly created Node.
			Node<T> leftNode = getNode(index - 1);
			Node<T> rightNode = getNode(index);
			newNode.setNode(rightNode);
			leftNode.setNode(newNode);
			size++;
		} else {
			throw new IndexOutOfBoundsException("Index not available.");
		}
	}

	public T get(int index) {
		return getNode(index).getData();
	}
	/**
	 * Returns the index of data. Index starts from 0 to n. If data not found in 
	 * list, return -1
	 * 
	 * @param data
	 * @return
	 */
	public int indexof(T data) {
		Node<T> pointerNode = this.node;
		int index = 0;
		while (pointerNode != null && pointerNode.getData() != null) {
			if (pointerNode.getData().equals(data)) {
				return index;
			} else {
				pointerNode = pointerNode.getNode();
				index++;
			}
		}
		return -1;
	}

	private Node<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.node;
		}
		// If index= size, return last node
		if (index == this.size - 1) {
			return getLastNode(this.node);
		}
		int pointer = 0;
		Node<T> pointerNode = this.node;
		while (pointer <= index) {
			if (pointer == index) {
				return pointerNode;
			} else {
				pointerNode = next(pointerNode);
				pointer++;
			}
		}
		return null;
	}

	private Node<T> getLastNode(Node<T> node) {

		Node<T> lastNode = node;
		if (lastNode.getNode() != null) {
			return getLastNode(lastNode.getNode());
		} else {
			return lastNode;
		}
	}


	private Node<T> next(Node<T> node) {
		if (node.getNode() != null) {
			return node.getNode();
		} else {
			return null;
		}
	}

	public int size() {
		return this.size;
	}

	/**
	 * Delete the first occurrence of element from linked list if exists and returns
	 * true. If data not available , it returns false;
	 * 
	 * @param data
	 * @return
	 */
	public boolean delete(T data) {
		if (this.node == null) {
			return false;
		}
		Node<T> pointerNode = this.node;
		// If input data is the head of linked list.
		if (pointerNode.getData().equals(data)) {
			this.node = next(pointerNode);
			size--;
			return true;
		}
		int indexofData = indexof(data);
		if(indexofData >0 ) {
			return deleteByIndex(indexofData);
		}
		else {
			return false;
		}
	}

	/**
	 * Delete the data by index.
	 * 
	 * @param index
	 * @return
	 */
	public boolean deleteByIndex(int index) {
		if (this.node == null) {
			return false;
		}
		if (index < 0 || index > this.size - 1) {
			throw new IndexOutOfBoundsException("Index not available.");
		}
		// If index=0 , put head node = Node at index 1.
		if (index == 0) {
			if(this.node.getNode()!=null) {
			this.node = getNode(index + 1);
			}else {
				this.node=null;
			}
			size--;
			return true;
		}
		// If index= size -1 means need to delete last node, get the 2nd last node and
		// set next node as null.
		if (index == this.size - 1) {
			getNode(index - 1).setNode(null);
			size--;
			return true;
		}

		// if index is in between 0 and size of linked list , set Node of leftNode as
		// rightNode
		Node<T> leftNode = getNode(index - 1);
		Node<T> rightNode = getNode(index + 1);
		leftNode.setNode(rightNode);
		size--;
		return true;
	}
	
	/**
	 * Clear the linked list 
	 */
	public void clear() {
		this.node = null;
		this.size = 0;
	}
	
	@Override
	public String toString() {
		String represent = "[";
		Node<T> nextNode = this.node;
		while (nextNode != null) {
			represent = represent + nextNode.toString();
			nextNode = next(nextNode);
			if (nextNode != null) {
				represent = represent + ",";
			}
		}
		represent = represent + "]";
		return represent;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((node == null) ? 0 : node.hashCode());
		result = prime * result + size;
		return result;
	}

	/**
	 * Two linked list is equal when their size is equals and both have similar node structure
	 */
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof SinglyLinkedList))
			return false;
		SinglyLinkedList other = (SinglyLinkedList) obj;
		if (node == null) {
			if (other.node != null)
				return false;
		} else if (!node.equals(other.node))
			return false;
		if (size != other.size)
			return false;
		return true;
	}

}


package com.study.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.study.singlyLinkedList;

import com.study.DTO.Item;

public class TestSinglyLinkedList {

	public static void main(String[] args) {
		SinglyLinkedList<Item> linkedList=new SinglyLinkedList<Item>();
		
		linkedList.add(new Item(101, "IPhone-5S", 200.00));
		linkedList.add(new Item(102, "IPhone-6S", 500.00));
		linkedList.add(new Item(103, "IPhone-XX", 1000.00));
		System.out.println("Original List: "+ linkedList);
		System.out.println(" ");
		
		linkedList.reverse();
		
		System.out.println("After reversing List: "+ linkedList);
		System.out.println(" ");
		
		linkedList.reverseUsingStack();
		
		System.out.println("After reversing using stack List: "+ linkedList);
		System.out.println(" ");
	}
}

 

Output:

Original List: [Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0]]

After reversing List: [Item [itemId=103, itemName=IPhone-XX, price=1000.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=101, itemName=IPhone-5S, price=200.0]]

After reversing using stack List: [Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0]]

 

 

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

In next post, we will see the implementation to get the middle of a Singly Linked List.

You may like –

RELATED ARTICLESMORE FROM AUTHOR