Featured White Papers

• Measuring Risk to Improve Java Software Quality
• Do You Really Get Classloaders?
• Pragmatic Continuous Delivery with Jenkins, Nexus, and LiveRebel
• Your Next Java Web App: Less XML, No Long Restarts, Fewer Hassles
• Coding with JRebel, Java Forever Changed
• 2012 Developer Productivity Report: Java Tools, Tech, Devs, and Data

Sponsored Links

• Graph databases are 1000x faster than relational.

  Learn More!

• Career opportunities at Harman- Careers That'll Rock Your Socks Off.

  Learn More!

• Developer-friendly Java PDF libraries by Qoppa Software

  Live Demos

• Stop blaming your app! Diagnose Java performance issues.

  Free tool >

• UrbanCode: Go From Continuous Integration to
  Continuous Delivery

  Learn More!

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

Datastructures and algorithms, Part 2

Explore linked lists, stacks, queues, and trees

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

Page 2 of 7

Although you can create many kinds of linked lists, three popular linked list variants are the single, double, and circular linked lists. Let's explore those variants, beginning with the singly linked list.

Singly linked lists

A singly linked list is a linked list of nodes, where each node has a single link field. A reference variable holds a reference to the first node, each node (except the last) links to the next node, and the last node's link field contains null to signify the list's end. Although the reference variable is commonly named top, you can choose any name you want. Figure 2 presents a three-node singly linked list, where top references the A node, A connects to B, B connects to C, and C is the final node.

One common singly linked list algorithm is node-insertion. That algorithm is somewhat involved because it must deal with four cases: when the node must be inserted before the first node; when the node must be inserted after the last node; when the node must be inserted between two nodes; and when the singly linked list does not exist. Before studying each case, consider the following pseudocode:

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

The pseudocode above declares a Node self-referential class with a name nonlink field and a next link field. The pseudocode also declares a top reference variable (of type Node) that holds a reference to the first Node in a singly linked list. Because the list does not yet exist, top's initial value is NULL. Each of the following four cases assumes the Node and top declarations: