Java programming fundamentals: Datastructures and algorithms in Java

Java 101: Datastructures and algorithms in Java, Part 4

Searching and sorting with singly linked lists and their algorithms in Java

1 2 Page 2
Page 2 of 2

Listing 2. SSLDemo.java (version 2)


public final class SLLDemo
{
   private static class DictEntry
   {
      String word;
      String meaning;
      DictEntry next;
   }

   // ListInfo is necessary because buildList() must return two pieces
   // of information.

   private static class ListInfo
   {
      DictEntry top;
      DictEntry last;
   }

   public static void main(String[] args)
   {
      String[] wordsMaster = { "aardvark", "anxious", "asterism" };
      ListInfo liMaster = new ListInfo();
      buildList(liMaster, wordsMaster);
      dump("Master list =", liMaster.top);
      String[] wordsWorking = { "carbuncle", "catfish", "color" };
      ListInfo liWorking = new ListInfo();
      buildList(liWorking, wordsWorking);
      dump("Working list =", liWorking.top);

      // Perform the concatenation

      liMaster.last.next = liWorking.top;
      dump("New master list =", liMaster.top);
      invert(liMaster);
      dump("Inverted new master list =", liMaster.top);
   }

   private static void buildList(ListInfo li, String[] words)
   {
      if (words.length == 0)
         return;

      // Create a node for first word/meaning.

      li.top = new DictEntry();
      li.top.word = words[0];
      li.top.meaning = null;

      // Initialize last reference variable to
      // simplify append and make concatenation possible.

      li.last = li.top;
      for (int i = 1; i < words.length; i++)
      {
         // Create (and append) a new node for next word/meaning.

         li.last.next = new DictEntry();
         li.last.next.word = words[i];
         li.last.next.meaning = null;

         // Advance last reference variable to simplify append and 
         // make concatenation possible.

         li.last = li.last.next;
      }
      li.last.next = null;
   }

   private static void dump(String msg, DictEntry topEntry)
   {
      System.out.print(msg + " ");
      while (topEntry != null)
      {
         System.out.print(topEntry.word + " ");
         topEntry = topEntry.next;
      }
      System.out.println();
   }

   private static void invert(ListInfo li)
   {
      DictEntry p = li.top, q = null, r;
      while (p != null)
      {
         r = q;
         q = p;
         p = p.next;
         q.next = r;
      }
      li.top = q;
   }
}

Compile Listing 2 as follows:


javac SLLDemo.java

Run the resulting application as follows:


java SLLDemo

You should observe the following output:


Master list = aardvark anxious asterism 
Working list = carbuncle catfish color 
New master list = aardvark anxious asterism carbuncle catfish color 
Inverted new master list = color catfish carbuncle asterism anxious aardvark

Algorithms for searching and sorting singly linked lists

It's a very common programming task to search a singly linked list for specific data items. While the Linear Search algorithm (introduced in Part 2) is most frequently used for this type of task, various other algorithms are available. You might be tempted to adapt the Binary Search algorithm in pursuit of better performance, but in this case you'd be disappointed. The list would have to be repeatedly searched for the desired node and performance would degrade to O(n). A better option is Merge Sort, which is a divide and conquer algorithm that divides the unsorted list into n sublists (each sublist contains one element, and a list of one element is considered sorted). Merge Sort repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining: the sorted list.

Another possibility is Insertion Sort, which we used to sort an array in Part 2. Now we'll use this algorithm to sort a singly linked list.

Example #3: Insertion Sort for singly linked lists

Insertion Sort orders a singly linked list of n data items into ascending or descending order. It starts with an initially empty (and therefore trivially sorted) list. Nodes are taken off the list one at a time, and then inserted into the proper place in the sorted list. If the list being sorted is empty, the sorted list has the desired result.

The following pseudocode expresses Insertion Sort in a singly linked list of strings/ascending sort context:


// Exit if list is empty or contains one node.
IF top EQ NULL OR top.next EQ NULL THEN
   END
END IF
// sTop is first node of sorted list.
DECLARE Node sTop = NULL
WHILE top NE NULL
   DECLARE Node current = top
   top = top.next
   IF sTop EQ NULL OR current.name LT sTop.name THEN
      // Insert into the head of the sorted list (sTop) or as the first 
      // element into an empty sorted list.
      current.next = sTop
      sTop = current
   ELSE
      // Insert current element into the proper position in the nonempty 
      // sorted list.
      DECLARE Node p = sTop
      WHILE p NE NULL
         // p.next EQ NULL means last element of the sorted list.
         // current.name LT p.next.name means middle of the sorted list.
         IF p.next EQ NULL OR current.name LT p.next.name THEN
            // Insert into the middle of the sorted list or as the last 
            // element.
            current.next = p.next
            p.next = current
            BREAK // Finished.
         END IF
         p = p.next
      END WHILE
   END IF
END WHILE

In its worst and average cases, Insertion Sort has a time complexity of O(n2)--quadratic. In its best case, where the list is sorted or nearly sorted, its time complexity is O(n). As far as space complexity is concerned, Insertion Sort requires O(1) additional space (for variable storage).

I've created an InsSort Java application that lets you experiment with Insertion Sort. The application's source code is shown in Listing 3.

Listing 3. InsSort.java


public final class InsSort
{
   private static class Node
   {
      String name;
      Node next;
   }

   public static void main(String[] args)
   {
      Node top = null;

      // 1. The singly linked list does not exist.

      top = new Node();
      top.name = "B";
      top.next = null;

      // 2. The singly linked list exists and the node must be inserted
      //    after the last node.

      Node temp = new Node();
      temp.name = "D";
      temp.next = null;
      Node temp2 = top;
      while (temp2.next != null)
         temp2 = temp2.next;
      temp2.next = temp;

      // 3. The singly linked list exists and the node must be inserted
      //    after the last node.

      temp = new Node();
      temp.name = "C";
      temp.next = null;
      temp2 = top;
      while (temp2.next != null)
         temp2 = temp2.next;
      temp2.next = temp;

      // 4. The singly linked list exists and the node must be inserted
      //    after the last node.

      temp = new Node();
      temp.name = "A";
      temp.next = null;
      temp2 = top;
      while (temp2.next != null)
         temp2 = temp2.next;
      temp2.next = temp;

      // 5. Dump the unsorted list.

      dump("Unsorted list", top);

      // 6. Sort the list.

      top = sort(top);

      // 7. Dump the sorted list.

      dump("Sorted list", top);
   }

   private static void dump(String msg, Node topNode)
   {
      System.out.print(msg + " ");
      while (topNode != null)
      {
         System.out.print(topNode.name + " ");
         topNode = topNode.next;
      }
      System.out.println();
   }

   private static Node sort(Node top)
   {
      if (top == null || top.next == null)
         return top;

      Node sTop = null;
      while (top != null)
      {
         Node current = top;
         top = top.next;
         if (sTop == null || current.name.compareTo(sTop.name) < 0)
         {
            current.next = sTop;
            sTop = current;
         }
         else
         {
            Node p = sTop;
            while (p != null)
            {
               if (p.next == null || current.name.compareTo(p.next.name) < 0)
               {
                  current.next = p.next;
                  p.next = current;
                  break;
               }
               p = p.next;
            }
         }
      }
      return sTop;
   }
}

Compile Listing 3 as follows:


javac InsSort.java

Run the resulting application as follows:


java InsSort

You should observe the following output:


Unsorted list B D C A 
Sorted list A B C D

Conclusion to Part 4

This article has introduced singly linked lists and all of the essential operations for working with them in Java. The final article in this series introduces doubly linked lists and circular-linked lists. Read it now!

1 2 Page 2
Page 2 of 2