Sorting of linked list in Java
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.
- 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 < private T data ; private Nodenode; public Node(T data) < this.data = data; >public Node getNode() < return node; >public void setNode(Node 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 < private int size = 0; private Nodenode; /** * Sort Linked list using Merge sort algorithm * */ public void sort() < this.node=sort(this.node); >private Node sort(Node node) < if(node ==null || node.getNode()==null) < return node; >// Get the middle of the linked list Node middleNode=getMiddle(node); Node rightNode=middleNode.getNode(); // set the next of middle node to null middleNode.setNode(null); Node leftNode=node; // Apply mergeSort on left list Node sortedLeft = sort(leftNode); // Apply mergeSort on right list Node sortedRight = sort(rightNode); Node sortedList =mergerSortedList(sortedLeft,sortedRight); return sortedList; > /** * Merge two nodes left node and right node in increasing order * @param left * @param right * @return */ private Node mergerSortedList(Node left , Node right) < NodemergedList=null; if(left== null ) < return right; >if(right== null ) < return left; >if (left.getData().hashCode() 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 getMiddle(Node node) < if(node ==null || node.getNode()==null) < return node; >Node fastPointer=node.getNode(); Node 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() < Nodecurrent=this.node; Node previous=null; Node 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 Stackstack=new Stack (); Node 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()) < NoderootNode=stack.pop(); Node 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(data); > else < NodenewNode = new Node(data); Node 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 newNode = new Node(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) < NodenewNode = new Node(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 leftNode = getNode(index - 1); Node 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) < NodepointerNode = 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 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 pointerNode = this.node; while (pointer else < pointerNode = next(pointerNode); pointer++; >> return null; > private Node getLastNode(Node node) < NodelastNode = node; if (lastNode.getNode() != null) < return getLastNode(lastNode.getNode()); >else < return lastNode; >> private Node next(Node 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 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 leftNode = getNode(index - 1); Node 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 = "["; NodenextNode = 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) < SinglyLinkedListlinkedList=new SinglyLinkedList(); 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); > > Hope you like this post. Please leave your comments/suggestions.
How to sort a LinkedList In Java?
In this post, we will look at how we can sort a LinkedList in Java using some inbuilt functions. We will be looking at the below points.
- How to sort a LinkedList in ascending order?
- Second, how to sort a LinkedList in descending order?
- And lastly, we will see how we can sort a Linked List of custom-made objects?
Let’s have a look at all of them one by one.
How to sort a LinkedList in ascending order?
We will be using the Collections.sort() method of the Collections class in java.util package to sort the linked list.
What does this method do? It will accept a list as an argument and sort the list in ascending order ( according to the natural ordering of the element ). It is a static method, so we can directly call this method using its class name.
Note: To use this method, the elements of the LinkedList must implement a Comparable interface, and all of the elements of the LinkedList should also be mutually comparable.
Code Example
import java.util.Collections; import java.util.LinkedList; public class Codekru < public static void main(String[] args) < LinkedListli = new LinkedList(); li.add(62); li.add(53); li.add(42); li.add(23); li.add(453); System.out.println("LinkedList before sorting: " + li.toString()); Collections.sort(li); // sorting the elements of the linked list System.out.println("LinkedList after sorting in ascending order: " + li.toString()); > > LinkedList before sorting: [62, 53, 42, 23, 453] LinkedList after sorting: [23, 42, 53, 62, 453]Sorting a linked list in descending order
Sorting a linked list in descending order is pretty easy as we only have to reverse the linked list sorted in ascending order ( which we already did above).
We will be using the Collections.reverse() function, a static function to reverse the list passed in its arguments. So, sorting a linked list in descending order is only a two-step process –
import java.util.Collections; import java.util.LinkedList; public class Codekru < public static void main(String[] args) < LinkedListli = new LinkedList(); li.add(62); li.add(53); li.add(42); li.add(23); li.add(453); System.out.println("LinkedList before sorting: " + li.toString()); Collections.sort(li); // sorting the elements of the linked list Collections.reverse(li); // reversing the linked list System.out.println("LinkedList after sorting in descending order: " + li.toString()); > > LinkedList before sorting: [62, 53, 42, 23, 453] LinkedList after sorting in descending order: [453, 62, 53, 42, 23]Sorting a LinkedList of custom-made objects
Let’s make a class named Person having two variables ( age and height ), and we will try to sort a list of Person objects based on their age in ascending order. We have not made any getters and setters methods to make the code look shorter. 😛
class Person < int age; int height; public Person(int age, int height) < this.age = age; this.height = height; >// using toString() method to print only the person's age public String toString() < return "Person's age: " + age; >>
Now, as we want to sort based on age, we will have to implement the Comparator interface and its compare method.
class PersonComparator implements Comparator < @Override public int compare(Person o1, Person o2) < return o1.age - o2.age; >>
Now, what would the above piece of code do? It would help us compare two person objects based on their age and sort them in ascending order. If you want to sort them in descending order, you must reverse the result returned by the compare function.
Collections.sort() method has one more overloaded static method that accepts two arguments – one is the list itself, and another is the implemented class of the comparator, which is PersonComparator in our case. So, we will have to pass the LinkedList along with the PersonComparator in the Collection.sort() function to sort the Person’s object list based on their age.
Complete example
class Person < int age; int height; public Person(int age, int height) < this.age = age; this.height = height; >// using toString() method to print only the person's age public String toString() < return "Person's age: " + age; >> class PersonComparator implements Comparator < @Override public int compare(Person o1, Person o2) < return o1.age - o2.age; >> public class Codekru < public static void main(String[] args) < LinkedListli = new LinkedList(); li.add(new Person(11,124)); li.add(new Person(9,134)); li.add(new Person(8,104)); li.add(new Person(43,184)); System.out.println("LinkedList before sorting: " + li.toString()); PersonComparator pc = new PersonComparator(); Collections.sort(li,pc); // sorting the elements of the linked list System.out.println("LinkedList after sorting in descending order: " + li.toString()); > > LinkedList before sorting: [Person's age: 11, Person's age: 9, Person's age: 8, Person's age: 43] LinkedList after sorting in descending order: [Person's age: 8, Person's age: 9, Person's age: 11, Person's age: 43]Here, we have sorted the LinkedList of Person objects in the ascending order of their age.
What if we try to use the Collection.sort() method on a list containing different types of objects?
Here, we will take a linked list with elements of type Integer and String and then try to sort it using the Collection.sort() function.
public class Codekru < public static void main(String[] args) < LinkedListli = new LinkedList(); li.add(3); li.add(45); li.add("hello"); li.add("codekru"); System.out.println("LinkedList before sorting: " + li.toString()); Collections.sort(li); // sorting the elements of the linked list System.out.println("LinkedList after sorting in descending order: " + li.toString()); > > Exception in thread "main" java.lang.Error: Unresolved compilation problem: The method sort(List) in the type Collections is not applicable for the arguments (LinkedList)We hope that you have liked the article. If you have any doubts or concerns, please feel free to write us in the comments or mail us at [email protected].