Sorted Linked List

Overview

Concept

A sorted linked list data structure is a type of linked list in which all the elements are sorted based upon some ordering. For example, with numbers, the ordering is a natural ordering such as smallest to largest, or largest to smallest. With objects, typically, some sort of function to compare two objects will need to be invoked to determine the ordering of the objects. Each element in a sorted linked list is referred to as a node. In a singly linked list implementation, each node contains a reference to the object stored in the node and a reference to the next node. In a doubly linked list implementation, each node contains a reference to the object stored in the node, a reference to the next node, as well as, a reference to the previous node. As a result of each node being ordered, various operations upon the list such as finding the maximum or minimum value contained in the sorted linked list are faster than an unsorted linked  list implementation. This comes at the expense of slowing down the insertion and removal operations.

Algorithmic Complexity

Big-O

HeapsHeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Sorted Linked List-O(1)O(1)O(n)O(n)O(1)O(m+n)

Implementation

Java Implementation

This is an example Java program to implement a sorted singly linked list.  This program was compiled and successfully tested under Java version 1.8.


/**
 * Node implementation for a sorted singly-linked list.
 * 
 * www.algorithmiccomplexity.com 
 */
public class Node
{
   protected int myData;

   protected Node myNextNode;

   public Node(int data, Node nextNode)
   {
      myData = data;
      myNextNode = nextNode;
   }

   public Node getNextNode()
   {
      return myNextNode;
   }

   public int getData()
   {
      return myData;
   }
}

/**
 * Sorted linked list implementation.
 *
 * www.algorithmiccomplexity.com 
 */
public class SortedSinglyLinkedList
{
   private Node myStartingNode;

   public int mySize;

   public SinglyLinkedList()
   {
      myStartingNode = null;
      mySize = 0;
   }

   public int getSize()
   {
      return mySize;
   }

   public boolean isEmpty()
   {
      return (mySize == 0);
   }

   public void insert(int value)
   {
      // Implementation coming soon!
   }

   @Override
   public String toString()
   {
      Node startingNode = myStartingNode;

      return ""; // TODO implementation coming soon!
   }

   public void main(String[] args)
   {
      SortedSinglyLinkedList singlyLinkedList = new SortedSinglyLinkedList();
      singlyLinkedList.insert(5);
      singlyLinkedList.insert(2);
      singlyLinkedList.insert(0);
      singlyLinkedList.insert(10);
      singlyLinkedList.insert(3);

      System.out.println(singlyLinkedList);
      // Output should be 0, 2, 3, 5, 10
   }
}

References

Wikipedia: Linked list