|
|
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
Page 5 of 7
Listing 3. GCDemo.java
// GCDemo.java
class GCDemo
{
static class Node
{
String name;
Node next;
protected void finalize () throws Throwable
{
System.out.println ("Finalizing " + name);
super.finalize ();
}
}
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);
top = null;
temp = null;
for (int i = 0; i < 100; i++)
System.gc ();
}
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 ();
}
}
GCDemo creates the same four-node list as SLLDelDemo. After dumping the nodes to the standard output device, GCDemo assigns null to both top and temp. Next, GCDemo executes System.gc (); up to 100 times. What happens next? Look at the output (which I observe on my Windows platform) below:
Initial singly-linked list B A D C Finalizing C Finalizing D Finalizing A Finalizing B
The output reveals that all the singly linked list's nodes are finalized (and garbage collected). As a result, you don't need
to worry about explicitly setting each node's link(s) to null when it comes time to destroy a singly (or any other kind of)
linked list. (You might need to increase the number of System.gc (); executions if your output doesn't include the finalizing messages.)
Many useful algorithms exist for singly linked lists. One such algorithm is concatenation, which implies that you attach one singly linked list to the end of another.
Another useful algorithm is inversion. That algorithm reverses a singly linked list's links to let you traverse its nodes
in the opposite direction. The following pseudocode extends the previous pseudocode to reverse the top1-referenced list's links.
Listing 4 illustrates the concatenation and inversion algorithms:
Listing 4. CIDemo.java
// CIDemojava
class CIDemo
{
static class DictEntry
{
String word;
String meaning;
DictEntry next;
}
// ListInfo is necessary because buildList() must return two pieces
// of information
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);
}
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;
}
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 ();
}
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;
}
}
CIDemo declares a DictEntry nested top-level class whose objects hold words and meanings. (To keep the program simple, I avoid meanings. You can add
them if desired.) CIDemo also declares ListInfo to track references to the first and last DictEntry nodes in a singly linked list.