This story appeared on JavaWorld at
http://www.javaworld.com/javaworld/jw-06-2003/jw-0613-java101.html
This story appeared on JavaWorld at
http://www.javaworld.com/javaworld/jw-06-2003/jw-0613-java101.html
Last month's column brought you into the computer science world of datastructures and algorithms by focusing on the array datastructure and associated algorithms. Developers view the array as a fundamental datastructure because it serves as the basis for more complex datastructures, such as stacks, queues, and trees. Developers also view the fundamental linked-list datastructure as a foundation for more complex datastructures.
This article wraps up a two-part series that explores datastructures and algorithms. You first learn about the linked-list datastructure in terms of its single, double, and circular variants. While learning those variants, you discover the related linked-list algorithms for node-insertion/deletion, concatentation, inversion, and insertion-sort. I also discuss the advantages and disadvantages of the linked list and array, a rule-of-thumb for deciding when to use each datastructure in your own programs, and whether or not both can integrate into useful hybrid datastructures. Finally, you receive an introduction to the more complex stack, queue, and tree datastructures.
| Note |
|---|
| Though Java supplies its own classes and interfaces to meet many of your datastructure and algorithm needs, you might need a specific datastructure or algorithm that Java doesn't supply. A basic knowledge of those topics should simplify the task of creating that datastructure/algorithm. |
Read the whole series: "Datastructures and Algorithms," Jeff Friesen (JavaWorld)
In addition to the array, another datastructure that receives much use is the linked list. The linked-list datastructure involves four concepts: the self-referential class, node, link field, and link:
class Employee{ private int empno; private String name; private double salary; public Employee next; // Other members}Employee is a self-referential class because its next field has type Employee.
next is a link field. In contrast, empno, name, and salary are nonlink fields. next's reference to an Employee node is a link. The four concepts above lead to the following definition: a linked list is a sequence of nodes that interconnect via the links in their link fields. Computer scientists use a special notation to illustrate linked lists. A variant of that notation, which I use in this article, appears in Figure 1.
Figure 1. A special notation for illustrating linked lists
Figure 1 presents three nodes: A, B, and C. Each node divides into a contents area (in orange) and one or more link areas (in green). The contents area represents all nonlink fields, and each link area represents a link field. A's single link area and C's link areas incorporate an arrow to signify a reference to some other node of the same type (or a subtype). B's single link area incorporates an X to signify a null reference. In other words, B doesn't connect to any other node.
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.
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.
Figure 2. A three-node singly linked list contains connected nodes A, B, and C
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 nextEND DECLAREDECLARE 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:
Node, assign its reference to top, initialize its nonlink field, and assign NULL to its link field. The following pseudocode performs those tasks:top = NEW Nodetop.name = "A"top.next = NULL
Figure 3 shows the initial singly linked list that emerges from the pseudocode above.
Figure 3. The initial singly linked list contains the solitary Node A
Node, initialize its nonlink field, assign top's reference to the next link field, and assign the newly created Node's reference to top. The following pseudocode (which assumes that the previous pseudocode has executed) performs those tasks:DECLARE Node temptemp = NEW Nodetemp.name = "B"temp.next = toptop = temp
The resulting two-Node list appears in Figure 4.
Figure 4. The expanded two-Node singly linked list places Node B ahead of Node A
Node, initialize its nonlink field, assign NULL to the link field, traverse the singly linked list to find the last Node, and assign the newly created Node's reference to the last Node's next link field. The following pseudocode performs those tasks:temp = NEW Nodetemp.name = "C"temp.next = NULLDECLARE Node temp2temp2 = top// We assume top (and temp2) are not NULL// because of the previous pseudocodeWHILE temp2.next IS NOT NULL temp2 = temp2.nextEND WHILE// temp2 now references the last nodetemp2.next = temp
Figure 5 reveals the list following the insertion of Node C after Node A.
Figure 5. Node C comes last in the expanded three-node singly linked list
Node, initialize its nonlink field, traverse the list to find the Node that appears before the newly created Node to be inserted, assign the link in that previous Node's next link field to the newly created Node's next link field, and assign the newly created Node's reference to the previous Node's next link field. The following pseudocode performs those tasks:temp = NEW Nodetemp.name = "D"temp2 = top// We assume that the newly created Node is inserted after Node// A and that Node A exists. In the real world, there is no// guarantee that any Node exists, so we would need to check// for temp2 containing NULL in both the WHILE loop's header// and after the WHILE loop completes.WHILE temp2.name IS NOT "A" temp2 = temp2.nextEND WHILE// temp2 now references Node A.temp.next = temp2.nexttemp2.next = temp
Figure 6 presents the list following the insertion of Node D between Nodes A and C.
Figure 6. The ever-growing singly linked list places Node D between Nodes A and C. Click on thumbnail to view full-size image.
Listing 1 presents the Java equivalent to the earlier insertion pseudocode examples:
Listing 1. SLLInsDemo.java
// SLLInsDemo.javaclass SLLInsDemo{ static class Node { String name; Node next; } public static void main (String [] args) { Node top = null; // 1. The singly linked list does not exist top = new Node (); top.name = "A"; top.next = null; dump ("Case 1", top); // 2. The singly linked list exists, and the node must be inserted // before the first node Node temp; temp = new Node (); temp.name = "B"; temp.next = top; top = temp; dump ("Case 2", top); // 3. The singly linked list exists, and the node must be inserted // after the last node temp = new Node (); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump ("Case 3", top); // 4. The singly linked list exists, and the node must be inserted // between two nodes temp = new Node (); temp.name = "D"; temp2 = top; while (temp2.name.equals ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump ("Case 4", 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 (); }}The static void dump(String msg, Node topNode) method iterates over the list and prints out its contents. When you run SLLInsDemo, repeated calls to that method result in the following output, which agrees with what you see in Figures 3 through 6:
Case 1 ACase 2 B ACase 3 B A CCase 4 B A D C
| Note |
|---|
SLLInsDemo and earlier pseudocode examples employed a linked-list-oriented linear-search algorithm to find a specific Node. You'll undoubtedly use that algorithm in your own programs:
|
A second common singly-linked list algorithm is node-deletion. Unlike node-insertion, there are only two cases to consider: delete the first node and delete any node but the first node. Each case assumes a singly linked list with at least one node exists:
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.
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 = topWHILE temp.name IS NOT "A" temp = temp.nextEND WHILE// We assume that temp references Node Atemp.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.javaclass 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 CAfter first node deletion A D CAfter 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:
Listing 3. GCDemo.java
// GCDemo.javaclass 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 CFinalizing CFinalizing DFinalizing AFinalizing 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
// CIDemojavaclass 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.
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 asterismWorking list = carbuncle catfish colorNew master list = aardvark anxious asterism carbuncle catfish colorInverted new master list = color catfish carbuncle asterism anxious aardvark
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.
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.javaclass 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: ABCBackward singly-linked list: CBAForward singly-linked list (after deletion): ACBackward singly-linked list (after deletion): CA
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.javaclass 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.
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 offer the following advantages over arrays:
In contrast, arrays offer the following advantages over linked lists:
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).
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.
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:
this reference. 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.javapackage 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.javapackage 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.javapackage 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.javapackage 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.javaimport 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 objectPushing Character objectPushing Thread objectPushing "One last item"One push too manyThread[A,5,main]CStackDemo@7182c1WorldHelloOne pop too manyLinkedListStack Demo--------------------Pushing "Hello"Pushing "World"Pushing StackDemo objectPushing Character objectPushing Thread objectPushing "One last item"One last itemThread[A,5,main]CStackDemo@cac268WorldHelloOne pop too many
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:
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.javapackage 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.javapackage 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.javapackage 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.javapackage 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.javapackage 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.javaimport 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 = trueIs full = falseInserting "This"Inserting "is"Inserting "a"Inserting "sentence"Inserting "."Inserting "One last item"One insert too manyIs empty = falseIs full = trueThis [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 manyArrayCircularQueue Demo---------------------Is empty = trueIs full = falseInserting "This"Inserting "is"Inserting "a"Inserting "sentence"Inserting "."Inserting "One last item"One insert too manyIs empty = falseIs full = trueThis [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
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.javaimport 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 = 2Word = Count, Count = 2Word = Create, Count = 1Word = Display, Count = 3Word = IOException, Count = 1Word = If, Count = 4Word = Insert, Count = 1Word = Left, Count = 1Word = Otherwise, Count = 2Word = Place, Count = 2Word = Read, Count = 1Word = Right, Count = 1Word = String, Count = 4Word = 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. |
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.
All contents copyright 1995-2007 Java World, Inc. http://www.javaworld.com