Unsorted Linked List

Overview

Concept

An unsorted linked list data structure is a type of linked list in which the elements are not sorted. 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. Since the list is not ordered, various operations upon the list such as finding the maximum or minimum value contained in the unsorted linked list are slower than a sorted linked list implementation since every node has to be traversed. However, this increases the speed of the insertion and removal operations compared to a sorted linked list.

Algorithmic Complexity

Big-O

HeapsHeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Unsorted Linked List-O(n)O(n)O(1)O(1)O(1)O(1)

Implementation

Java Implementation

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


/**
 * Node implementation for an unsorted 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;
   }
}

/**
 * Unsorted linked list implementation.
 *
 * www.algorithmiccomplexity.com 
 */
public class UnsortedSinglyLinkedList
{
   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()
   {
      return ""; // TODO implementation coming soon!
   }

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

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

References

Wikipedia: Linked list