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

The main thread executes CIDemo's public static void main(String [] args) method. That thread twice calls the static void buildList (ListInfo li, String [] words) method to create each of two singly linked lists: a master list (whose nodes populate with words from the wordsMaster array), and a working list (whose nodes populate with words from the wordsWorking array). Prior to each buildList (ListInfo li, String [] words) method call, the main thread creates and passes a ListInfo object. That object returns the first and last node references. (A method call directly returns a single data item only.) After building a singly linked list, the main thread calls static void dump (String msg, DictEntry topEntry) to dump a message and the words in a list's nodes to the standard output device.

You might be wondering about the need for ListInfo's last field. That field serves a dual purpose: First, last simplifies the creation of each list, where nodes are appended. Second, that field simplifies concatenation, which amounts to nothing more than executing the following line of code: liMaster.last.next = liWorking.top;. Once concatenation completes and the main thread dumps the resulting master list to the standard output device, that thread calls the static void invert (ListInfo li) method to invert the master list—and then dumps the inverted master list to standard output.

When run, CIDemo produces 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


Doubly linked lists

Singly linked lists restrict node-traversal to a single direction: you can't traverse a singly linked list in the opposite direction unless you first use the inversion algorithm to reverse node links, which takes time. After the reverse traversal, you probably need to repeat inversion to restore node-traversal to the original direction, which takes more time. A second problem involves node deletion: you cannot delete an arbitrary node without access to the node's predecessor. These problems disappear when you use a doubly linked list.

A doubly linked list is a linked list of nodes, where each node has a pair of link fields. One link field lets you traverse the list in a forward direction, whereas the other lets you traverse the list in a backward direction. For the forward direction, a reference variable holds a reference to the first node. Each node links to the next node via the next link field, except for the last node, whose next link field contains null to signify the list's end (in the forward direction). Similarly, for the backward direction, a reference variable holds a reference to the forward direction's last node, which you interpret as the first node. Each node links to the previous node via the previous link field, and the forward direction's first node's previous link field contains null to signify the list's end. Figure 9 presents a three-node doubly linked list, where topForward references the first node in a forward direction and topBackward references the first node in a backward direction.

  • Print
  • Feedback

Resources