Sorted Linked Lists and Sorted Arrays Java Example

If there is requirement for an application to maintain the data in sorted order within the list, then you need to use sorted linked lists. In this tutorial you will see how to implement sorted linked list using Java.

In a sorted list, the items are sorted by key value. You often delete the smallest or largest item in the list. But you can also use find() and delete() methods to search and delete specific links in the list.

Sorted Linked Lists Vs Sorted Arrays

In general you use sorted list in many situations where you use sorted array. The advantage of sorted list over sorted array is speed of insertion and the list can expand and fill available memory, while an array is limited to a fixed size.

Sorted list is difficult to implement when compared to sorted array.

Application: When to use Sorted Linked List ?

If an application frequently accesses the smallest item from the list, and fast insertion is not critical then Sorted Linked List is the effective choice

Sorted Linked List Example

package com.sneppets.dsalgo;

/**
 * Link
 */
class Link{
	//data
	public int intData;
	//next link in the list
	public Link next;
	//constructor
	public Link(int iData)
	{
		intData = iData;
	}
	//display link
	public void displayLink()
	{
		System.out.print(intData + " ");
	}
}

class SortedLinkedList{
	
	//reference to first link
	private Link first;
	
	//constructor
	public SortedLinkedList()
	{
		//no links yet
		first = null;
	}
	//return true if there are no links
	public boolean isEmpty()
	{
		return (first == null);
	}
	//logic to insert in order
	public void insert(int key)
	{
		//create a new link
		Link newLink = new Link(key);
		//set previous link to null, and use this null value to check whether you are at starting of the list
		Link prevLink = null;
		//set current link to first
		Link curLink = first;
		//until end of list is reached or if key of the link being inserted is greater than the key that is currently being examined
		while (curLink != null && key > curLink.intData)
		{
			prevLink = curLink;
			//go to next item in the list
			curLink = curLink.next;
		}		
		if(prevLink == null)
		{	//if at the beginning of the list or the list is empty, then set first --> newLink
			first = newLink;
		}
		else
		{	//if not at the beginning of the list, then set old prevLink --> newLink
			prevLink.next = newLink;
		}
		//newLink --> old current
		newLink.next = curLink;			
	}
	
	//return and delete first link
	public Link deleteFirst()
	{
		//save first link
		Link temp = first;
		//delete first link
		first = first.next;
		//return first link
		return temp;		
	}
	
	public void displayList()
	{
		System.out.println("List (Sorted) from first to last :");
		//start from beginning of the list
		Link curLink = first;
		//until end of list is reached
		while (curLink != null)
		{
			//print link details
			curLink.displayLink();
			//move to next link
			curLink = curLink.next;
		}
		System.out.println(" ");
	}
}

public class SortedLinkedListExample {
	
	public static void main(String[] args)
	{
		//create new sorted list
		SortedLinkedList sortedLinkedList = new SortedLinkedList();
		//insert items
		sortedLinkedList.insert(30);
		sortedLinkedList.insert(60);
		//display list
		sortedLinkedList.displayList();
		//insert 4 more
		sortedLinkedList.insert(20);
		sortedLinkedList.insert(10);
		sortedLinkedList.insert(40);
		sortedLinkedList.insert(50);
		//display list
		sortedLinkedList.displayList();
		//delete one item from first
		sortedLinkedList.deleteFirst();
		//display list
		sortedLinkedList.displayList();
		
	}
}

In the main() method we insert two items with key values 30 and 60. Then we insert four more items 20, 10, 40 and 50. These values are inserted at the appropriate places so that the end list is sorted.

Finally, we delete one item, to show that the items will always be deleted from the beginning of the list. After each change, the list is displayed. Here is the output from SortedLinkedListExample.java

Output

List (Sorted) from first to last :
30 60  
List (Sorted) from first to last :
10 20 30 40 50 60  
List (Sorted) from first to last :
20 30 40 50 60

Efficiency of sorted linked list

Sorted Linked List requires O(N) comparisons or O(N/2) comparisons on average for insertion and deletion, since the appropriate location must be found by traversing through the list.

If the item to be inserted or deleted is in/at the beginning of the list then it requires O(1) time.

Sorted Linked Lists and Sorted Arrays Java Example

Sorted Linked Lists Vs Sorted Arrays

Application: When to use Sorted Linked List ?

Sorted Linked List Example

Efficiency of sorted linked list

Recommended Posts

References