In this post, we will discuss the sorting of the linked list. There are many algorithms available for the sorting of linked list. Merge sort is preferred for Linked List because of costly operation for random access of elements. Quicksort is faster in the case of indexed based data structures but for non-indexed data structures, performance will be slow. So, because of slow random access of linked list, makes Quick Sort very slow and Heap Sort completely impossible. Merge sort is based on the Divide and Conquer strategy. The time complexity of Merge Sort is O(n Log n). Merge sort requires additional memory space to store the intermediate data.
Before implementation of merge sort for linked list in JAVA, we will see the algorithm and execution process.
Algorithm:
- If root node is NULL or there is only one element in linked list then return the root node.
- If step 1 is false, then call the steps 3 recursively till leftNode and rightNode has only one element .
- Divide the linked list into two half, leftNode and rightNode.
- Sort the leftNode and rightNode separately.
- Merge the sorted leftNode and rightNode in recursive manner.
- Finally, point the root node as merged sorted nodes.
By seeing the algorithm based on recursive calls, it’s somewhat hard to understand. Now, to describe this algorithm, we will see the execution process, which will show step-by-step process.
Execution Process: Suppose, we have linked list of type Integer.
We will see the implementation in JAVA. Basically, we will have two methods, sort(root ) and mergeSortedList(left, right). sort() method will break the node into two half and keep calling itself recursively till left node and right node size is equal to 1.Now, merge left node and right node and maintain the increasing order. To merge any node, we should check the each node value of right node with each node value of left node.[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;
/**
* Sort Linked list using Merge sort algorithm
*
*/
public void sort() {
this.node=sort(this.node);
}
private Node<T> sort(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
// Get the middle of the linked list
Node<T> middleNode=getMiddle(node);
Node<T> rightNode=middleNode.getNode();
// set the next of middle node to null
middleNode.setNode(null);
Node<T> leftNode=node;
// Apply mergeSort on left list
Node<T> sortedLeft = sort(leftNode);
// Apply mergeSort on right list
Node<T> sortedRight = sort(rightNode);
Node<T> sortedList =mergerSortedList(sortedLeft,sortedRight);
return sortedList;
}
/**
* Merge two nodes left node and right node in increasing order
* @param left
* @param right
* @return
*/
private Node<T> mergerSortedList(Node<T> left , Node<T> right){
Node<T> mergedList=null;
if(left== null ) {
return right;
}
if(right== null ) {
return left;
}
if (left.getData().hashCode() <= right.getData().hashCode()) {
mergedList = left;
mergedList.setNode(mergerSortedList(left.getNode(), right));
}
else {
mergedList = right;
mergedList.setNode(mergerSortedList(left, right.getNode()));
}
return mergedList;
}
/**
* Returns the data at middle of the linked list
* @return
*/
public T getMiddle() {
return getMiddle(this.node).getData();
}
/**
*
* @param node
* @return
*/
private Node<T> getMiddle(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
Node<T> fastPointer=node.getNode();
Node<T> slowPointer=node;
// Move fast pointer by two and slow pointer by one
// Finally slow pointer will point to middle node when fast
// pointer will reach at end of the linked list
while (fastPointer !=null) {
fastPointer=fastPointer.getNode();
if(fastPointer!=null) {
slowPointer=slowPointer.getNode();
fastPointer=fastPointer.getNode();
}
}
return slowPointer;
}
/**
* 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.singlyLinkedList;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Integer> linkedList=new SinglyLinkedList<Integer>();
linkedList.add(37);
linkedList.add(19);
linkedList.add(7);
linkedList.add(54);
linkedList.add(76);
System.out.println("Original List: "+ linkedList);
System.out.println(" ");
linkedList.sort();
System.out.println("After sorting: " + linkedList);
}
}
Output:
Original List: [37,19,7,54,76]
After sorting: [7,19,37,54,76]
—————————————————————————————————————-
Hope you like this post. Please leave your comments/suggestions.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list.
- Reverse of Singly Linked List.
- Implementation of Index based Linked List.
- Remove duplicate node from linked list.
- Rotation of Linked List.
- Intersection of two linked lists.
- Iterator for singly linked list java.
