Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

JavaWorld.com

Datastructures and algorithms, Part 2

Explore linked lists, stacks, queues, and trees

By Jeff Friesen, JavaWorld.com, 06/13/03

  • Print
  • Feedback

Page 3 of 7

  • The singly linked list does not exist: This is the simplest case. Create a Node, assign its reference to top, initialize its nonlink field, and assign NULL to its link field. The following pseudocode performs those tasks:

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


    Figure 3 shows the initial singly linked list that emerges from the pseudocode above.

    Figure 3. The initial singly linked list contains the solitary Node A

  • The node must be inserted before the first node:. Create a Node, initialize its nonlink field, assign top's reference to the next link field, and assign the newly created Node's reference to top. The following pseudocode (which assumes that the previous pseudocode has executed) performs those tasks:

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


    The resulting two-Node list appears in Figure 4.

    Figure 4. The expanded two-Node singly linked list places Node B ahead of Node A

  • The node must be inserted after the last node. Create a Node, initialize its nonlink field, assign NULL to the link field, traverse the singly linked list to find the last Node, and assign the newly created Node's reference to the last Node's next link field. The following pseudocode performs those tasks:

    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 IS NOT NULL
   temp2 = temp2.next
END WHILE
// temp2 now references the last node
temp2.next = temp


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

    Figure 5. Node C comes last in the expanded three-node singly linked list

  • The node must be inserted between two nodes: This is the most complex case. Create a Node, initialize its nonlink field, traverse the list to find the Node that appears before the newly created Node to be inserted, assign the link in that previous Node's next link field to the newly created Node's next link field, and assign the newly created Node's reference to the previous Node's next link field. The following pseudocode performs those tasks:

    temp = NEW Node
temp.name = "D"
temp2 = top 
// We assume that the newly created Node is inserted 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 IS NOT "A"
   temp2 = temp2.next
END WHILE
// temp2 now references Node A.
temp.next = temp2.next
temp2.next = temp


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

    Figure 6. The ever-growing singly linked list places Node D between Nodes A and C. Click on thumbnail to view full-size image.

    Listing 1 presents the Java equivalent to the earlier insertion pseudocode examples:

    Listing 1. SLLInsDemo.java

    // SLLInsDemo.java
class SLLInsDemo
{
   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);
   }
   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 ();
   }
}


    The static void dump(String msg, Node topNode) method iterates over the list and prints out its contents. When you run SLLInsDemo, repeated calls to that method result in the following output, which agrees with what you see in Figures 3 through 6: 

    Case 1 A 
Case 2 B A 
Case 3 B A C 
Case 4 B A D C


    Note
    SLLInsDemo and earlier pseudocode examples employed a linked-list-oriented linear-search algorithm to find a specific Node. You'll undoubtedly use that algorithm in your own programs:

    • Search for the final Node:

      // Assume top references a singly linked list of at least one Node.
Node temp = top // We use temp and not top. If top were used, we 
                // couldn't access the singly linked list after 
                // the search finished because top would refer 
                // to the final Node.
WHILE temp.next IS NOT NULL
   temp = temp.next
END WHILE
// temp now references the last Node.
    • Search for a specific Node:

      // Assume top references a singly linked list of at least one Node. 
Node temp = top
WHILE temp IS NOT NULL AND temp.name IS NOT "A" // Search for "A".
   temp = temp.next
END WHILE
// temp either references Node A or contains NULL if Node A not found.


    A second common singly-linked list algorithm is node-deletion. Unlike node-insertion, there are only two cases to consider: delete the first node and delete any node but the first node. Each case assumes a singly linked list with at least one node exists:

  • Print
  • Feedback

Resources