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 4 of 7

  • Delete the first node: Assign the link in the top-referenced Node's next field to top:

    top = top.next; // Reference the second Node (or NULL if there is only one Node)


    Figure 7 presents before and after views of a list where the first Node is deleted. In that figure, Node B disappears and Node A becomes the first Node.

    Figure 7. Before and after views of a singly linked list where the first Node is deleted. The red X and dotted lines signify top's change of reference from Node B to Node A. Click on thumbnail to view full-size image.

  • Delete any node but the first node: Locate the Node that precedes the Node to be deleted and assign the link in the Node-to-be-deleted's next link field to the preceding Node's next link field. The following pseudocode (which assumes Figure 6's linked list and extends that figure's associated pseudocode) deletes Node D:

    temp = top
WHILE temp.name IS NOT "A"
   temp = temp.next
END WHILE
// We assume that temp references Node A
temp.next = temp.next.next
// Node D no longer exists


    Figure 8 presents before and after views of a list where an intermediate Node is deleted. In that figure, Node D disappears.

    Figure 8. Before and after views of a singly linked list where an intermediate Node is deleted. The red X and dotted lines signify Node A's change of link from Node D to Node C. Click on thumbnail to view full-size image.

    Listing 2 presents the Java equivalent to the earlier deletion pseudocode examples:

    Listing 2. SLLDelDemo.java

    // SLLDelDemo.java
class SLLDelDemo
{
   static class Node
   {
      String name;
      Node next;
   }
   public static void main (String [] args)
   {
      // Build Figure 6's singly linked list (i.e., B A D C)
      Node top = new Node ();
      top.name = "C";
      top.next = null;
      Node temp = new Node ();
      temp.name = "D";
      temp.next = top;
      top = temp;
      temp = new Node ();
      temp.name = "A";
      temp.next = top;
      top = temp;
      temp = new Node ();
      temp.name = "B";
      temp.next = top;
      top = temp;
      dump ("Initial singly-linked list", top);
      // 1. Delete the first node
      top = top.next;
      dump ("After first node deletion", top);
      // Put back B
      temp = new Node ();
      temp.name = "B";
      temp.next = top;
      top = temp;
      // 2. 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);
   }
   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 ();
   }
}


    When you run SLLDelDemo, you observe the following output: 

    Initial singly linked list B A D C 
After first node deletion A D C 
After D node deletion B A C


    Caution
    Because Java initializes an object's reference fields to null during that object's construction, it isn't necessary to explicitly assign null to a link field. Don't ignore those null assignments in your source code; their absence reduces your code's clarity.


    After studying SLLDelDemo, you might be wondering what happens if you assign null to the top-referenced node: does the garbage collector collect the entire list? For an answer to that question, compile and run Listing 3:

  • Print
  • Feedback

Resources