|
|
Featured White Papers
- Why choose an Open Source BPM?
- 10 FAQs on Business Process Management
- Best Practices for Getting Started with BPM
- Free Your Devs From The Pain Of Java Redeploys
- Increase Velocity 40% by Using JRebel
- What Developers Want: The End of Application Redeploys
- Developer Productivity Report: Java Tools, Tech, Devs, and Data
- Coding with JRebel: Java Forever Changed
- Utilizing Fast Testing to Transform Java Development
- 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
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
Page 7 of 7
Figure 9. A three-node doubly linked list lets you traverse a sequence of nodes forwards and backwards
| Tip |
|---|
| Think of a doubly linked list as a pair of singly linked lists that each interconnect the same nodes. |
The insertion and deletion of a doubly linked list's nodes are common operations. Those operations are accomplished via algorithms that base themselves on the singly linked list's node-insertion and node-deletion algorithms (because a doubly linked list is just a pair of singly linked lists that interconnect the same nodes).
Listing 5 demonstrates node-insertion to create Figure 9's list, node-deletion as it removes Node B from that list, and forward and backward list-traversal:
Listing 5. DLLDemo.java
// DLLDemo.java
class DLLDemo
{
static class Node
{
String name;
Node next;
Node prev;
}
public static void main (String [] args)
{
// Build a doubly linked list
Node topForward = new Node ();
topForward.name = "A";
Node temp = new Node ();
temp.name = "B";
Node topBackward = new Node ();
topBackward.name = "C";
topForward.next = temp;
temp.next = topBackward;
topBackward.next = null;
topBackward.prev = temp;
temp.prev = topForward;
topForward.prev = null;
// Dump forward singly linked list
System.out.print ("Forward singly-linked list: ");
temp = topForward;
while (temp != null)
{
System.out.print (temp.name);
temp = temp.next;
}
System.out.println ();
// Dump backward singly linked list
System.out.print ("Backward singly-linked list: ");
temp = topBackward;
while (temp != null)
{
System.out.print (temp.name);
temp = temp.prev;
}
System.out.println ();
// Reference node B
temp = topForward.next;
// Delete node B
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
// Dump forward singly linked list
System.out.print ("Forward singly-linked list (after deletion): ");
temp = topForward;
while (temp != null)
{
System.out.print (temp.name);
temp = temp.next;
}
System.out.println ();
// Dump backward singly linked list
System.out.print ("Backward singly-linked list (after deletion): ");
temp = topBackward;
while (temp != null)
{
System.out.print (temp.name);
temp = temp.prev;
}
System.out.println ();
}
}
When run, DLLDemo produces the following output:
Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA
Insertion-sort algorithm
You'll sometimes want to create a doubly linked list that organizes its nodes in order based on a nonlink field. Traversing the doubly linked list in one direction presents those nodes in ascending order. Similarly, a reverse traversal presents them in descending order. The bubble-sort algorithm is inappropriate for that task because it requires array indexes. In contrast, insertion-sort builds either a singly linked list or a doubly linked list in order of some nonlink field by identifying the insert position for each new node and inserting it at the insert position. Listing 6 demonstrates the insertion-sort algorithm:
Listing 6. InsSortDemo.java
// InsSortDemo.java
class InsSortDemo
{
// Note: To keep Employee simple, I've omitted various constructor and
// nonconstructor methods. In practice, such methods would be present.
static class Employee
{
int empno;
String name;
Employee next;
Employee prev;
}
public static void main (String [] args)
{
// Data for a doubly linked list of Employee objects. The lengths of
// the empnos and names arrays must agree.
int [] empnos =
{
687, 325, 567, 100, 987, 654, 234
};
String [] names =
{
"April", "Joan", "Jack", "George", "Brian", "Sam", "Alice"
};
Employee topForward = null;
Employee topBackward = null;
// Prime the doubly linked list by creating the first node.
topForward = new Employee ();
topForward.empno = empnos [0];
topForward.name = names [0];
topForward.next = null;
topForward.prev = null;
topBackward = topForward;
// Insert remaining Employee nodes (in ascending order -- via empno)
// into the doubly linked list.
for (int i = 1; i < empnos.length; i++)
{
// Create and initialize a new Employee node.
Employee e = new Employee ();
e.empno = empnos [i];
e.name = names [i];
e.next = null;
e.prev = null;
// Locate the first Employee node whose empno is greater than
// the empno of the Employee node to be inserted.
Employee temp = topForward;
while (temp != null && temp.empno <= e.empno)
temp = temp.next;
// temp is either null (meaning that the Employee node must be
// appended) or not null (meaning that the Employee node must
// be inserted prior to the temp-referenced Employee node).
if (temp == null)
{
topBackward.next = e; // Append new Employee node to
// forward singly linked list.
e.prev = topBackward; // Update backward singly linked
topBackward = e; // list as well.
}
else
{
if (temp.prev == null)
{
e.next = topForward; // Insert new Employee node at
topForward = e; // head of forward singly linked
// list.
temp.prev = e; // Update backward singly linked
// list as well.
}
else
{
e.next = temp.prev.next; // Insert new Employee node
temp.prev.next = e; // after last Employee node
// whose empno is smaller in
// forward singly linked list.
e.prev = temp.prev; // Update backward
temp.prev = e; // singly linked list as well.
}
}
}
// Dump forward singly linked list (ascending order).
System.out.println ("Ascending order:\n");
Employee temp = topForward;
while (temp != null)
{
System.out.println ("[" + temp.empno + ", " + temp.name + "] ");
temp = temp.next;
}
System.out.println ();
// Dump backward singly linked list (descending order).
System.out.println ("Descending order:\n");
temp = topBackward;
while (temp != null)
{
System.out.println ("[" + temp.empno + ", " + temp.name + "] ");
temp = temp.prev;
}
System.out.println ();
}
}
InsSortDemo simplifies its operation by first creating a primary Employee node. For each of the remaining Employee nodes, InsSortDemo locates the appropriate insert position based on the empno nonlink field, and then inserts Employee at that position. When you run InsSortDemo, you observe the following output:
Ascending order: [100, George] [234, Alice] [325, Joan] [567, Jack] [654, Sam] [687, April] [987, Brian] Descending order: [987, Brian] [687, April] [654, Sam] [567, Jack] [325, Joan] [234, Alice] [100, George]
Both insertion-sort and bubble-sort exhibit roughly the same performance.
Circular linked lists
The link field in the last node of a singly linked list contains a null link, as do, in a doubly linked list, the link fields in the last nodes of the forward and backward singly linked lists. Suppose instead that the last nodes contained links to the first nodes. In that situation, you end up with a circular linked list, as Figure 10 illustrates.
Figure 10. A circular linked list (based on a singly linked list) connects the last node to the first node
The circular linked list is often used to repeatedly process nodes in a specific order. Such nodes might represent server connections, processors waiting for a critical section, and so on. That datastructure also serves as the basis for a variant of a more complex datastructure: the queue (which I explore later in this article).
Linked lists versus arrays
Linked lists offer the following advantages over arrays:
- They don't require extra memory to support expansion. In contrast, arrays require extra memory if expansion is necessary. (Once all elements contain data items, no new data items can append to an array.)
- They offer faster node insertion/deletion than equivalent array-based operations. Only links need to update after identifying the insert/delete position. From an array perspective, data item insertion requires the movement of all other data items to create an empty element. Similarly, deletion of an existing data item requires the movement of all other data items to remove an empty element. All data item movement takes time.
In contrast, arrays offer the following advantages over linked lists:
- Array elements occupy less memory than nodes because elements don't require link fields
- Arrays offer faster access to data items, via integer-based indexes
Linked lists are most appropriate when dealing with dynamic data. In other words, insertions and deletions are frequent. In contrast, arrays are most appropriate where data is static. In other words, data item insertions and deletions are rare. (Don't forget: If you run out of room when adding data items to an array, you must create a larger array, copy the original array's data items to the larger array, and dispose of the original. That takes time, which affects performance—especially if done repeatedly.)
Merging a singly linked list with a one-dimensional array to access nodes via array indexes accomplishes nothing. You waste memory, because you need array elements plus nodes, and time, because you need to move the array's data items whenever you insert or delete a node. However, it's still possible to integrate the array with the linked list to create a useful datastructure (for example, the hash table datastructure).
The stack, queue, and tree datastructures
Developers use array and linked-list variants to build a variety of complex datastructures. This section explores three of those datastructures: the stack, the queue, and the tree. When presenting algorithms, for brevity, I present those algorithms in Java source code only.
Remember with stacks
The stack is a datastructure where data-item insertions and retrievals/deletions are made at one end, which is known as the top of the stack. Because the last inserted data item is the first retrieved/deleted data item, developers commonly refer to stacks as LIFO (last-in, first-out) datastructures.
Data items push (insert) onto and pop (retrieve/delete) off the stack's top. Figure 11 illustrates a stack with three String data items that each push onto the stack's top.
Figure 11. A stack with three pushed String data items
As Figure 11 shows, the stack builds down in memory. For each data-item push, the previous top data item and all lower data
items move farther down. When the time arrives to pop a data item from the stack, the top data item (which Figure 11 reveals
as "third") is retrieved and deleted from the stack.
Stacks are useful in various programming scenarios. Two common scenarios:
- Stacks hold return addresses: When code calls a method, the address of the first instruction following the call pushes onto the top of the current thread's method-call stack. When the called method's return instruction executes, that address pops off the top of that stack and execution continues at the address. If a method calls another method, the stack's LIFO behavior ensures that the second method's return instruction transfers execution to the first method, and the first method's return instruction transfers execution to whatever code follows the code that called the first method. As a result, a stack "remembers" return addresses on behalf of called methods.
- Stacks hold each called method's parameters and local variables: When a method is called, the JVM allocates memory near the return address that stores all the called method's parameters
and that method's local variables. If the method is an instance method, one of the parameters that stores on the stack is
the current object's
thisreference.
It's common to implement a stack using either a one-dimensional array or a singly linked list. In the one-dimensional array
scenario, an integer variable, typically named top, holds the index of the top data item. Similarly, a reference variable, also typically named top, references the top node (containing the top data item) in the singly linked list scenario.
I modeled my stack implementations after the architecture found in Java's Collections API. My implementations consist of a
Stack interface for maximum flexibility, ArrayStack and LinkedListStack implementation classes, and a FullStackException support class. For distribution ease, I packaged those classes in a com.javajeff.cds package, where cds stands for complex datastructures. Listing 7 presents the Stack interface:
Listing 7. Stack.java
// Stack.java
package com.javajeff.cds;
public interface Stack
{
boolean isEmpty ();
Object peek ();
void push (Object o);
Object pop ();
}
Stack's four methods determine if the stack is empty, retrieves the top data item without deleting it from the stack, places an
arbitrary data item on the stack's top, and retrieves/deletes the top data item. Apart from an implementation-specific constructor,
your program needs to call only those methods.
Listing 8 presents a one-dimensional array-based implementation of Stack:
Listing 8. ArrayStack.java
// ArrayStack.java
package com.javajeff.cds;
public class ArrayStack implements Stack
{
private int top = -1;
private Object [] stack;
public ArrayStack (int maxElements)
{
stack = new Object [maxElements];
}
public boolean isEmpty ()
{
return top == -1;
}
public Object peek ()
{
if (top < 0)
throw new java.util.EmptyStackException ();
return stack [top];
}
public void push (Object o)
{
if (top == stack.length - 1)
throw new FullStackException ();
stack [++top] = o;
}
public Object pop ()
{
if (top < 0)
throw new java.util.EmptyStackException ();
return stack [top--];
}
}
ArrayStack reveals a stack as a combination of a private top integer index and stack one-dimensional array-reference variables. top identifies the top data item in stack and initializes to -1 to signify an empty stack. When creating an ArrayStack object, call public ArrayStack(int maxElements) with an integer value that specifies the maximum number of elements. Any attempt to pop a data item off an empty stack's
top results in pop() throwing a java.util.EmptyStackException object. Similarly, any attempt to push more than maxElements data items onto the stack results in push(Object o) throwing a FullStackException object, whose code appears in Listing 9:
Listing 9. FullStackException.java
// FullStackException.java
package com.javajeff.cds;
public class FullStackException extends RuntimeException
{
}
For symmetry with EmptyStackException, FullStackException extends RuntimeException. As a result, you don't need to attach FullStackException to a method's throws clause.
Listing 10 presents a singly linked list-based implementation of Stack:
Listing 10. LinkedListStack.java
// LinkedListStack.java
package com.javajeff.cds;
public class LinkedListStack implements Stack
{
private static class Node
{
Object o;
Node next;
}
private Node top = null;
public boolean isEmpty ()
{
return top == null;
}
public Object peek ()
{
if (top == null)
throw new java.util.EmptyStackException ();
return top.o;
}
public void push (Object o)
{
Node temp = new Node ();
temp.o = o;
temp.next = top;
top = temp;
}
public Object pop ()
{
if (top == null)
throw new java.util.EmptyStackException ();
Object o = top.o;
top = top.next;
return o;
}
}
LinkedListStack reveals a stack as a combination of a private Node nested top-level class and a private top reference variable that initializes to null to signify an empty stack. Unlike its one-dimensional array counterpart, LinkedListStack doesn't require a constructor because it dynamically expands as more data items push. Thus, void push(Object o) does not need to throw a FullStackException object. However, Object pop() still must check for an empty stack scenario, which might result in a thrown EmptyStackException object.
Now that you've seen the interface and three classes that make up my stack datastructure implementations, let's play. Listing
11 demonstrates most of my com.javajeff.cds package's stack support:
Listing 11. StackDemo.java
// StackDemo.java
import com.javajeff.cds.*;
class StackDemo
{
public static void main (String [] args)
{
System.out.println ("ArrayStack Demo");
System.out.println ("---------------");
stackDemo (new ArrayStack (5));
System.out.println ("LinkedListStack Demo");
System.out.println ("--------------------");
stackDemo (new LinkedListStack ());
}
static void stackDemo (Stack s)
{
System.out.println ("Pushing \"Hello\"");
s.push ("Hello");
System.out.println ("Pushing \"World\"");
s.push ("World");
System.out.println ("Pushing StackDemo object");
s.push (new StackDemo ());
System.out.println ("Pushing Character object");
s.push (new Character ('C'));
System.out.println ("Pushing Thread object");
s.push (new Thread ("A"));
try
{
System.out.println ("Pushing \"One last item\"");
s.push ("One last item");
}
catch (FullStackException e)
{
System.out.println ("One push too many");
}
System.out.println ();
while (!s.isEmpty ())
System.out.println (s.pop ());
try
{
s.pop ();
}
catch (java.util.EmptyStackException e)
{
System.out.println ("One pop too many");
}
System.out.println ();
}
}
When StackDemo runs, that application produces the following output:
ArrayStack Demo --------------- Pushing "Hello" Pushing "World" Pushing StackDemo object Pushing Character object Pushing Thread object Pushing "One last item" One push too many Thread[A,5,main] C StackDemo@7182c1 World Hello One pop too many LinkedListStack Demo -------------------- Pushing "Hello" Pushing "World" Pushing StackDemo object Pushing Character object Pushing Thread object Pushing "One last item" One last item Thread[A,5,main] C StackDemo@cac268 World Hello One pop too many
Prioritize with queues
The queue is a datastructure where data-item insertions are made at one end (the queue's rear) and data-item retrievals/deletions are made at the other end (the queue's front). Because the first inserted data item is the first retrieved/deleted data item, developers commonly refer to queues as FIFO (first-in, first-out) datastructures.
Developers frequently work with two kinds of queues: linear and circular. In either queue, data items are inserted at the queue's rear, move toward the queue's front, and are retrieved/deleted from the front. Figure 12 illustrates linear and circular queues.
Figure 12. Linear and circular queues with four and seven inserted integer data items, respectively.
Figure 12's linear queue stores four integer data items, with integer 1 first. That queue is full and cannot store additional
integer data items because rear identifies the rightmost (final) slot. The reason for the empty slot, which front identifies, involves the linear queue's behavior. Initially, front and rear identify the leftmost slot, which indicates an empty queue. To store integer 1, rear advances one slot to the right and 1 stores in that slot. To retrieve/delete integer 1, front advances one slot to the right.
| Note |
|---|
To signal that the linear queue is empty, you don't need to waste a slot, although that approach is often convenient. Instead,
assign the same value that indicates a nonexistent slot to front and rear. For example, assuming a one-dimensional array-based implementation, front and rear could each contain -1. Index 0 then indicates the leftmost slot, and data items are inserted beginning at that index.When |
Figure 12's circular queue stores seven integer data items, with integer 1 first. That queue is full and cannot store another
integer data item until front advances one slot in a clockwise direction (to recover integer 1) and rear advances one slot in a clockwise direction (to identify the slot that will contain the new integer). As with the linear queue,
the reason for the empty slot, which front identifies, involves the circular queue's behavior. Initially, front and rear identify the same slot, which indicates an empty queue. rear then advances one slot for each new insertion. Similarly, front advances one slot for each retrieval/deletion.
Queues are useful in various programming scenarios. Two common scenarios:
- Thread scheduling: A JVM or an underlying operating system might establish multiple queues to coincide with different thread priorities. The thread information blocks because all threads of a given priority store in the associated queue.
- Print jobs: Because a printer is typically much slower than a computer, an operating system often hands off print jobs to its printing subsystem, which inserts those jobs into a print queue. The first job in that queue prints first, and the last job prints last.
Developers often use the one-dimensional array to implement a queue. However, if multiple queues need to coexist, or queue
insertions must occur for priority reasons at a slot other than the rear, developers typically switch to the doubly linked
list. With a one-dimensional array, integer variables (often named front and rear) hold indexes to the queue's front and rear elements. My implementations of linear and circular queues use the one-dimensional
array and begin with Listing 12's Queue interface:
Listing 12. Queue.java
// Queue.java
package com.javajeff.cds;
public interface Queue
{
void insert (Object o);
boolean isEmpty ();
boolean isFull ();
Object remove ();
}
Queue declares four methods for storing a data item in a queue, determining if a queue is empty, determining if a queue is full,
and retrieving/deleting a data item from a queue. Call those methods (and a constructor) to work with any Queue implementation.
Listing 13 presents a one-dimensional array-based linear queue implementation of Queue:
Listing 13. ArrayLinearQueue.java
// ArrayLinearQueue.java
package com.javajeff.cds;
public class ArrayLinearQueue implements Queue
{
private int front = -1, rear = -1;
private Object [] queue;
public ArrayLinearQueue (int maxElements)
{
queue = new Object [maxElements];
}
public void insert (Object o)
{
if (rear == queue.length - 1)
throw new FullQueueException ();
queue [++rear] = o;
}
public boolean isEmpty ()
{
return front == rear;
}
public boolean isFull ()
{
return rear == queue.length - 1;
}
public Object remove ()
{
if (front == rear)
throw new EmptyQueueException ();
return queue [++front];
}
}
ArrayLinearQueue reveals a queue as a combination of private front, rear, and queue variables. front and rear initialize to -1 to signify an empty queue. As with ArrayStack's constructor, call public ArrayLinearQueue(int maxElements) with an integer value that specifies the maximum number of elements during the construction of an ArrayLinearQueue object.
ArrayLinearQueue's insert(Object o) method throws a FullQueueException object when rear identifies the final one-dimensional array element. FullQueueException's code appears in Listing 14:
Listing 14. FullQueueException.java
// FullQueueException.java
package com.javajeff.cds;
public class FullQueueException extends RuntimeException
{
}
ArrayLinearQueue's remove() method throws an EmptyQueueException object when front equals rear. Listing 15 presents that class's code:
Listing 15. EmptyQueueException.java
// EmptyQueueException.java
package com.javajeff.cds;
public class EmptyQueueException extends RuntimeException
{
}
Listing 16 presents a one-dimensional array-based circular-queue implementation of Queue:
Listing 16. ArrayCircularQueue.java
// ArrayCircularQueue.java
package com.javajeff.cds;
public class ArrayCircularQueue implements Queue
{
private int front = 0, rear = 0;
private Object [] queue;
public ArrayCircularQueue (int maxElements)
{
queue = new Object [maxElements];
}
public void insert (Object o)
{
int temp = rear;
rear = (rear + 1) % queue.length;
if (front == rear)
{
rear = temp;
throw new FullQueueException ();
}
queue [rear] = o;
}
public boolean isEmpty ()
{
return front == rear;
}
public boolean isFull ()
{
return ((rear + 1) % queue.length) == front;
}
public Object remove ()
{
if (front == rear)
throw new EmptyQueueException ();
front = (front + 1) % queue.length;
return queue [front];
}
}
ArrayCircularQueue reveals an implementation, in terms of private field variables and a constructor, similar to ArrayLinearQueue. The insert(Object o) method is interesting in that it saves rear's current value before advancing that variable to point to the next slot. If the circular queue is full, rear restores to its original value before a FullQueueException object is thrown. rear's restoration is necessary because front equals rear (at that point), and a subsequent call to remove() results in a thrown EmptyQueueException object (even when the circular queue isn't empty).
After studying the code to the interface and various classes that make up my one-dimensional array-based implementations of the queue datastructure, consider Listing 17, an application that demonstrates linear and circular queues:
Listing 17. QueueDemo.java
// QueueDemo.java
import com.javajeff.cds.*;
class QueueDemo
{
public static void main (String [] args)
{
System.out.println ("ArrayLinearQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayLinearQueue (5));
System.out.println ("ArrayCircularQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayCircularQueue (6)); // Need one more slot because
// of empty slot in circular
// implementation
}
static void queueDemo (Queue q)
{
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
System.out.println ("Inserting \"This\"");
q.insert ("This");
System.out.println ("Inserting \"is\"");
q.insert ("is");
System.out.println ("Inserting \"a\"");
q.insert ("a");
System.out.println ("Inserting \"sentence\"");
q.insert ("sentence");
System.out.println ("Inserting \".\"");
q.insert (".");
try
{
System.out.println ("Inserting \"One last item\"");
q.insert ("One last item");
}
catch (FullQueueException e)
{
System.out.println ("One insert too many");
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
}
System.out.println ();
while (!q.isEmpty ())
System.out.println (q.remove () + " [Is empty = " + q.isEmpty () +
", Is full = " + q.isFull () + "]");
try
{
q.remove ();
}
catch (EmptyQueueException e)
{
System.out.println ("One remove too many");
}
System.out.println ();
}
}
When QueueDemo runs, that application produces the following output:
ArrayLinearQueue Demo --------------------- Is empty = true Is full = false Inserting "This" Inserting "is" Inserting "a" Inserting "sentence" Inserting "." Inserting "One last item" One insert too many Is empty = false Is full = true This [Is empty = false, Is full = true] is [Is empty = false, Is full = true] a [Is empty = false, Is full = true] sentence [Is empty = false, Is full = true] . [Is empty = true, Is full = true] One remove too many ArrayCircularQueue Demo --------------------- Is empty = true Is full = false Inserting "This" Inserting "is" Inserting "a" Inserting "sentence" Inserting "." Inserting "One last item" One insert too many Is empty = false Is full = true This [Is empty = false, Is full = false] is [Is empty = false, Is full = false] a [Is empty = false, Is full = false] sentence [Is empty = false, Is full = false] . [Is empty = true, Is full = false] One remove too many
Hierarchically organize with trees
A tree is a finite group of nodes, where one of those nodes serves as the root and remaining nodes organize below the root in a hierarchical fashion. A node that references a node below is a parent node. Similarly, a node referenced from a node above is a child node. Nodes without children are leaf nodes. A node may be both a parent node and a child node, or a child node and a leaf node.
A parent node may reference as many child nodes as necessary. In many situations, a parent node only references a maximum
of two child nodes. Trees based on such nodes are known as binary trees. Figure 13 presents a binary tree that stores seven String words in alphabetical order.
Figure 13. A seven-node binary tree stores "page" in the root node. Click on thumbnail to view full-size image.
Insert nodes, delete nodes, and traverse nodes in binary or other kinds of trees through recursion. (To learn about that elegant computing technique, read the sidebar, "Recursion.") For brevity, I don't delve into recursive node-insertion, node-deletion, and tree-traversal algorithms. Instead, I present a word-counting application's source code to demonstrate recursive node-insertion and tree-traversal in Listing 18. That code uses node-insertion to create a binary tree, where each node contains a word and a count of word occurrences, and displays those words and counts in alphabetical order via the move-left-examine-node-move-right variant of the tree-traversal algorithm.
Listing 18. WC.java
// WC.java
import java.io.*;
class TreeNode
{
String word; // Word being stored.
int count = 1; // Count of words seen in text.
TreeNode left; // Left subtree reference.
TreeNode right; // Right subtree reference.
public TreeNode (String word)
{
this.word = word;
left = right = null;
}
public void insert (String word)
{
int status = this.word.compareTo (word);
if (status > 0) // word argument precedes current word
{
// If left-most leaf node reached, then insert new node as
// its left-most leaf node. Otherwise, keep searching left.
if (left == null)
left = new TreeNode (word);
else
left.insert (word);
}
else
if (status < 0) // word argument follows current word
{
// If right-most leaf node reached, then insert new node as
// its right-most leaf node. Otherwise, keep searching right.
if (right == null)
right = new TreeNode (word);
else
right.insert (word);
}
else
this.count++;
}
}
class WC
{
public static void main (String [] args) throws IOException
{
int ch;
TreeNode root = null;
// Read each character from standard input until a letter
// is read. This letter indicates the start of a word.
while ((ch = System.in.read ()) != -1)
{
// If character is a letter then start of word detected.
if (Character.isLetter ((char) ch))
{
// Create StringBuffer object to hold word letters.
StringBuffer sb = new StringBuffer ();
// Place first letter character into StringBuffer object.
sb.append ((char) ch);
// Place all subsequent letter characters into StringBuffer
// object.
do
{
ch = System.in.read ();
if (Character.isLetter ((char) ch))
sb.append ((char) ch);
else
break;
}
while (true);
// Insert word into tree.
if (root == null)
root = new TreeNode (sb.toString ());
else
root.insert (sb.toString ());
}
}
display (root);
}
static void display (TreeNode root)
{
// If either the root node or the current node is null,
// signifying that a leaf node has been reached, return.
if (root == null)
return;
// Display all left-most nodes (i.e., nodes whose words
// precede words in the current node).
display (root.left);
// Display current node's word and count.
System.out.println ("Word = " + root.word + ", Count = " +
root.count);
// Display all right-most nodes (i.e., nodes whose words
// follow words in the current node).
display (root.right);
}
}
Because of extensive comments, I won't discuss the code. Instead, I suggest you play with this application, as follows: To
count the number of words in a file, issue a command line that includes the < redirection symbol. For example, count the number of words in WC.java by issuing java WC <WC.java. A few lines of output that result from that command line appear below:
Word = Character, Count = 2 Word = Count, Count = 2 Word = Create, Count = 1 Word = Display, Count = 3 Word = IOException, Count = 1 Word = If, Count = 4 Word = Insert, Count = 1 Word = Left, Count = 1 Word = Otherwise, Count = 2 Word = Place, Count = 2 Word = Read, Count = 1 Word = Right, Count = 1 Word = String, Count = 4 Word = StringBuffer, Count = 5
| Note |
|---|
| Because space doesn't permit me to delve into trees, other datastructures, and associated algorithms, and because Java is this column's focus, I recommend that you obtain a good computer science textbook that explores datastructures and algorithms in a Java context. |
Review
The array and linked list datastructures are like two sides to the same coin. To build upon last month's exploration of the array, this month's column explored the linked list. You learned about that datastructure's single, double, and circular variants, and related algorithms. The article also compared arrays with linked lists, where you discovered advantages and disadvantages to each fundamental datastructure. I concluded by exploring the more complex stack, queue, and tree datastructures. During that exploration, you learned how to use either an array variant or a linked-list variant to create a stack, an array variant to create two kinds of queues, and a linked-list variant to create a binary tree. You also learned about recursion, which is useful in tree-based algorithms for node-insertion, node-deletion, and tree-traversal.
I encourage you to email me with any questions you might have involving either this or any previous article's material. (Please keep such questions relevant to material discussed in this column's articles.) Your questions and my answers will appear in the relevant study guides.
Please note that this is the final installment to the Java 101 column.
About the author
Jeff Friesen has been involved with computers for the past 23 years. He holds a degree in computer science and has worked with many computer languages. Jeff has also taught introductory Java programming at the college level. In addition to writing for JavaWorld, he has written his own Java book for beginners? Java 2 by Example, Second Edition (Que Publishing, 2001; ISBN: 0789725932)?and helped write Using Java 2 Platform, Special Edition (Que Publishing, 2001; ISBN: 0789724685). Jeff goes by the nickname Java Jeff (or JavaJeff).- Feedback
More from JavaWorld
Resources
- Download this article's source code and resource files
http://www.javaworld.com/javaworld/jw-06-2003/java101/jw-0613-java101.zip - Read the whole series"Datastructures and Algorithms," Jeff Friesen (JavaWorld)
- For a glossary specific to this article, homework, and more, see the Java 101 study guide that accompanies this article
http://www.javaworld.com/javaworld/jw-06-2003/jw-0613-java101guide.html - Check out past Java 101 articles
http://www.javaworld.com/javaworld/topicalindex/jw-ti-java101.html - Browse the Core Java section of JavaWorld's Topical Index
http://www.javaworld.com/channel_content/jw-core-index.shtml - Java experts answer your toughest Java questions in JavaWorld's Java Q&A column
http://www.javaworld.com/javaworld/javaqa/javaqa-index.html - For Tips 'N Tricks, see
http://www.javaworld.com/javaworld/javatips/jw-javatips.index.html - Sign up for JavaWorld's free weekly Core Java email newsletter
http://www.javaworld.com/subscribe