Data structures and algorithms in Java, Part 4: Singly linked lists

Like arrays, which were introduced in Part 3 of this tutorial series, linked lists are a fundamental data structure category upon which more complex data structures can be based. Unlike a sequence of elements, however, a linked list is a sequence of nodes, where each node is linked to the previous and next node in the sequence. Recall that a node is an object created from a self-referential class, and a self-referential class has at least one field whose reference type is the class name. Nodes in a linked list are linked via a node reference. Here’s an example:

class Employee
{
   private int empno;
   private String name;
   private double salary;
   public Employee next;
   // Other members.
}

In this example, Employee is a self-referential class because its next field has type Employee. This field is an example of a link field because it can store a reference to another object of its class–in this case another Employee object.

This tutorial introduces the ins and outs of singly linked lists in Java programming. You’ll learn operations for creating a singly linked list, inserting nodes into a singly linked list, deleting nodes from a singly linked list, concatenating a singly linked list to another singly linked list, and inverting a singly linked list. We’ll also explore algorithms most commonly used for sorting singly linked lists, and conclude with an example demonstrating the Insertion Sort algorithm.

What is a singly linked list?

A singly linked list is a linked list of nodes where each node has a single link field. In this data structure, a reference variable contains a reference to the first (or top) node; each node (except for the last or bottom node) links to the next one; and the last node’s link field contains the null reference to signify the list’s end. Although the reference variable is commonly named top, you can choose any name you want.

Figure 1 presents a singly linked list with three nodes.

IDG

Below is pseudocode for a singly linked list.

DECLARE CLASS Node
  DECLARE STRING name
  DECLARE Node next
END DECLARE
DECLARE Node top = NULL

Node is a self-referential class with a name data field and a next link field. top is a reference variable of type Node that holds a reference to the first Node object in a singly linked list. Because the list doesn’t yet exist, top‘s initial value is NULL.

Creating a singly linked list in Java

You create a singly linked list by attaching a single Node object. The following pseudocode creates a Node object, assigns its reference to top, initializes its data field, and assigns NULL to its link field:

top = NEW Node
top.name = "A"
top.next = NULL

Figure 2 shows the initial singly linked list that emerges from this pseudocode.

IDG

This operation has a time complexity of O(1)–constant. Recall that O(1) is pronounced “Big Oh of 1.” (See Part 1 for a reminder of how time and space complexity measurements are used to evaluate data structures.)

Inserting nodes into a singly linked list

Inserting a node into a singly linked list is somewhat more complicated than creating a singly linked list because there are three cases to consider:

• Insertion before the first node.
• Insertion after the last node.
• Insertion between two nodes.

Insertion before the first node

A new node is inserted before the first node by assigning the top node’s reference to the new node’s link field and assigning the new node’s reference to the top variable. This operation is demonstrated by the following pseudocode:

DECLARE Node temp
temp = NEW Node
temp.name = "B"
temp.next = top
top = temp

The resulting two-Node list appears in Figure 3.

IDG

This operation has a time complexity of O(1).

Insertion after the last node

A new node is inserted after the last node by assigning null to the new node’s link field, traversing the singly linked list to find the last node, and assigning the new node’s reference to the last node’s link field, as the following pseudocode demonstrates:

temp = NEW Node
temp.name = "C"
temp.next = NULL
DECLARE Node temp2
temp2 = top 
// We assume top (and temp2) are not NULL 
// because of the previous pseudocode.
WHILE temp2.next NE NULL
   temp2 = temp2.next
END WHILE
// temp2 now references the last node.
temp2.next = temp

Figure 4 reveals the list following the insertion of Node C after Node A.

IDG

This operation has a time complexity of O(n)–linear. Its time complexity could be improved to O(1) by maintaining a reference to the last node. In that case it wouldn’t be necessary to search for the last node.

Insertion between two nodes

Inserting a node between two nodes is the most complex case. You insert a new node between two nodes by traversing the list to find the node that comes before the new node, assigning the reference in the found node’s link field to the new node’s link field, and assigning the new node’s reference to the found node’s link field. The following pseudocode demonstrates these tasks:

temp = NEW Node
temp.name = "D"
temp2 = top 
// We assume that the newly created Node inserts after Node 
// A and that Node A exists. In the real world, there is no 
// guarantee that any Node exists, so we would need to check 
// for temp2 containing NULL in both the WHILE loop's header 
// and after the WHILE loop completes.
WHILE temp2.name NE "A"
   temp2 = temp2.next
END WHILE
// temp2 now references Node A.
temp.next = temp2.next
temp2.next = temp

Figure 5 presents the list following the insertion of Node D between Nodes A and C.

IDG

This operation has a time complexity of O(n).

Deleting nodes from a singly linked list

Deleting a node from a singly linked list is also somewhat more complicated than creating a singly linked list. However, there are only two cases to consider:

• Deletion of the first node.
• Deletion of any node but the first node.

Deletion of the first node

Deleting the first node involves assigning the link in the first node’s link field to the variable that references the first node, but only when there is a first node:

IF top NE NULL THEN
   top = top.next; // Reference the second Node (or NULL when there's only one Node).
END IF

Figure 6 presents before and after views of a list where the first Node has been deleted. Node B disappears and Node A becomes the first Node.

IDG

This operation has a time complexity of O(1).

Deletion of any node but the first node

Deleting any node but the first node involves locating the node that precedes the node to be deleted and assigning the reference in the node-to-be-deleted’s link field to the preceding node’s link field. Consider the following pseudocode:

IF top NE NULL THEN
   temp = top
   WHILE temp.name NE "A"
      temp = temp.next
   END WHILE
   // We assume that temp references Node A.
   temp.next = temp.next.next
   // Node D no longer exists.
END IF

Figure 7 presents before and after views of a list where an intermediate Node is deleted. Node D disappears.

IDG

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I’ve created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application’s source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

public final class SLLDemo
{
   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 = "A";
      top.next = null;
      dump("Case 1", top);

      // 2. The singly linked list exists and the node must be inserted
      //    before the first node.

      Node temp;
      temp = new Node();
      temp.name = "B";
      temp.next = top;
      top = temp;
      dump("Case 2", top);

      // 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;
      Node temp2;
      temp2 = top;
      while (temp2.next != null)
         temp2 = temp2.next;
      temp2.next = temp;
      dump("Case 3", top);

      // 4. The singly linked list exists and the node must be inserted
      //    between two nodes.

      temp = new Node();
      temp.name = "D";
      temp2 = top;
      while (temp2.name.equals("A") == false)
         temp2 = temp2.next;
      temp.next = temp2.next;
      temp2.next = temp;
      dump("Case 4", top);

      // 5. Delete the first node.

      top = top.next;
      dump("After first node deletion", top);

      // 5.1 Restore node B.

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

      // 6. Delete any node but the first node.

      temp = top;
      while (temp.name.equals("A") == false)
         temp = temp.next;
      temp.next = temp.next.next;
      dump("After D node deletion", 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();
   }
}

Compile Listing 1 as follows:

javac SLLDemo.java

Run the resulting application as follows:

java SLLDemo

You should observe the following output:

Case 1 A 
Case 2 B A 
Case 3 B A C 
Case 4 B A D C 
After first node deletion A D C 
After D node deletion B A C

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

DECLARE Node top1 = NULL
DECLARE Node top2 = NULL
// Assume code that creates top1-referenced singly linked list.
// Assume code that creates top2-referenced singly linked list.
// Concatenate top2-referenced list to top1-referenced list.
IF top1 EQ NULL
   top1 = top2
   END
END IF
// Locate final Node in top1-referenced list.
DECLARE Node temp = top1
WHILE temp.next NE NULL
   temp = temp.next
END WHILE
// Concatenate top2 to top1.
temp.next = top2
END

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2‘s value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there’s no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list’s links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list’s links:

DECLARE Node p = top1 // Top of original singly linked list.
DECLARE Node q = NULL // Top of reversed singly linked list.
DECLARE Node r        // Temporary Node reference variable.
WHILE p NE NULL       // For each Node in original singly linked list ...
   r = q              // Save future successor Node's reference.
   q = p              // Reference future predecessor Node.
   p = p.next         // Reference next Node in original singly linked list.
   q.next = r         // Link future predecessor Node to future successor Node.
END WHILE
top1 = q              // Make top1 reference first Node in reversed singly linked list.
END

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

I’ve created a second version of the SLLDemo Java application that demonstrates concatenation and inversion. Listing 2 presents this application’s source code.

Listing 2. Java application demo for concatenation and inversion in singly linked lists (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

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(n²)–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. A Java application for experimenting with Insertion Sort (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