chevron_left
208 points
13 6 5

Hello reader, Welcome to my post :)

In this post, we shall see how we can sort the linked list without making use of the collections class in java. We shall see what are the available techniques for sorting the linked list. Without further delay, we would step into the discussion below.

 

What is a linked list?

Linked list can be explained as a data structure which stores the data elements in the form of nodes in a non contiguous manner. The nodes would be arranged inside the linked list one by one, with each node pointing to its adjacent next node. The node would comprise the data which forms the actual element and pointer to the next node. The first node would be called as the head and the last node on the right would be termed as the tail node. Based on the reference to the next node, the linked list can be distinguished into several types 

  • Singly linked list
  • Doubly linked list
  • Circular linked list

Suppose we have a linked list containing 7 elements in them, we can think of a linked list, as a building with as many storeys as the elements. When we want to navigate to the 6th floor in the building, we tend to utilise the lift and traverse all the storeys before reaching the destination. Likewise inside the linked list, in order to traverse to the nth node, one has to start from the head node and traverse all the nodes before the nth node, in order to reach to the nth node.

 

Sorting a linked list:

Usually, for the purpose of sorting a linked list, we tend to make use of the collections.sort function provided by java. This function provides the flexibility to sort the linked list either in the ascending or descending manner with ease. In case if we don't want to use the collections class for sorting the linked list, we have the below sorting techniques which can be used for sorting the linked list

  • Bubble sort
  • Insertion sort
  • Quick sort
  • Merge sort

However, all the sorting techniques help to sort the linked list, merge sort remains the most preferred approach. Since the traversal of a random node in a linked list is slow, other algorithms tend to perform in a poor manner. We would see how we can leverage the merge sort to sort the given linked list.

 

Merge sort:

On a high level, the merge sort works on the principle of divide and conquer algorithm. The given data structure would be divided into two parts, then again subjected to split operation and eventually the merging operation takes place. The final output would be in a sorted manner. Likewise, the  given linked list would be subjected to split operation, where it would be split into the two different lists - right and left. This split operation recurses till the sub lists get sorted, subsequently would be subjected to the merge operation. This merge operation continues and ultimately there would be two lists, which are again merged and arranged into a single sorted linked list. The below code snippet explains the merge sort applied on a linked list – 

node divideAndConquer(node head)
		{
			// Base case 
			if (head == null || head.next == null)
			{
				return head;
			}

			// get the middle of the list
			node middleNode = getMiddleNode(head);
			node nextOfMiddle = middleNode.next;

			// set next of middle node to null
			middleNode.next = null;

			node left = divideAndConquer(head);
           		           node right = divideAndConquer(nextOfMiddle);

			
			node resultHeadNode = mergeAndSort(left, right);
			
			return resultHeadNode;
		}


		node mergeAndSort(node left, node right)
		{
			node output = null;
			
			// Base case
			if (left == null)
				return right;
			if (right == null)
				return left;

			// Recursion
			if (left.val < right.val)
			{
				output = left;
				output.next = mergeAndSort(left.next, right);
			}
			else
			{
				output = right;
				output.next = mergeAndSort(left, right.next);
			}
			
			return output;
		}

		
		// get the middle of the linked list
		public static node getMiddleNode(node head)
		{
			if (head == null)
				return head;

			node slow = head;
			node fast = head;

			while (fast.next != null && fast.next.next != null)
			{
				slow = slow.next;
				fast = fast.next.next;
			}
			
			return slow;
		}

Here the head of the linked list is being provided as the input parameter to the divideAndConquer method. From the head node, the middle node of the linked list is being computed. Subsequently the right and left node are arrived at, then subjected to the recursion with the head value being null as the base case. Then every time when the left and right nodes are found, they are subjected to another method, which compares whether the left value is greater or lesser than the right value. It employs the principle of recursion again to arrive at the output. Using this particular algorithm, the given linked list can easily be sorted. 

 

Thus we have come to the end of this post. Hope you found this post informative.

Thanks for reading :)

1 Comment

You've done a fantastic job of explaining it. Now I know what to do, thank you.

More Posts

Sort array without using sort function in Java Hafsa_Rao - Oct 1
Sort String array java without using sort method kesav.eee - May 15
C++ how to create a linked list sakshi - Jul 30
how to sort a string in java Hasnain_khan - Oct 13, 2020
Polynomial addition and multiplication using linked list in c - Part 1 SharadMagar450 - Aug 3
Polynomial addition and multiplication using linked list in c - Part 2 SharadMagar450 - Aug 3
clear a linked list java DivyaN - Aug 9
Traversal of a linked list in C Yogesh Sharma - Aug 18
How to make an array of linked lists in Java mhfaisal - Jul 10
Delete duplicate-value nodes from a sorted linked list kesav.eee - Aug 10