List Nodes
The structures in this chapter are composed of list nodes. A list node contains only one element, but it also contains (a reference to) another list node. A list node is represented by an instance of a class called, not surprisingly, ListNode (Figure 6-1).
Figure 6-1. A ListNode contains another ListNode unless next is null.
This arrangement allows us to make a chain of ListNodes, each containing a reference to the next one (Figure 6-2). The next field of the last node is null.
Figure 6-2. A chain of three ListNodes.
There are a number of ways to create the data structure in Figure 6-2. One is to create the nodes and then link them together:
ListNode node1 = new ListNode("A"); ListNode node2 = new ListNode("B"); ListNode node3 = new ListNode("C"); node1.setNext(node2); node2.setNext(node3);
An alternate approach, taking advantage of the overloaded constructor, is to create the entire chain with one expression:
new ListNode ("A", new ListNode ("B", new ListNode("C")))
As we'll see later in this chapter, these chains of nodes are usually constructed gradually, with nodes being added or removed as elements are pushed onto a Stack, removed from a Queue, and so on.
We can splice a node out of a chain if we can find the node's predecessor. For example, if the nodes in Figure 6-2 are named node1, node2, and node3, then the method invocation
node1.setNext(node2.getNext());
results in the situation shown in Figure 6-3.
Figure 6-3. Splicing a node out of a chain.
The code for the ListNode class is simple (Figure 6-4).
Figure 6-4. The ListNode class.
|
1 /** Node in a linked list. */ 2 public class ListNode { 3 4 /** The item stored in this node. */ 5 private E item; 6 7 /** The node following this one. */ 8 private ListNode next; 9 10 /** Put item in a node with no next node. */ 11 public ListNode(E item) { 12 this.item = item; 13 next = null; 14 } 15 16 /** Put item in a node with the specified next node. */ 17 public ListNode(E item, ListNode next) { 18 this.item = item; 19 this.next = next; 20 } 21 22 /** Return the item stored in this node. */ 23 public E getItem() { 24 return item; 25 } 26 27 /** Return the next node. */ 28 public ListNode getNext() { 29 return next; 30 } 31 32 /** Replace the item stored in this node. */ 33 public void setItem(E item) { 34 this.item = item; 35 } 36 37 /** Set the next node. */ 38 public void setNext(ListNode next) { 39 this.next = next; 40 } 41 42 } |
It is sometimes useful to have a doubly linked node, which knows about both the previous and the next node (Figure 6-5).
Figure 6-5. A DoublyLinkedNode knows about both its predecessor and its successor.
A chain of DoublyLinkedNodes is somewhat hairy looking, because there is one sequence of references leading forward and another leading backward (Figure 6-6).
Figure 6-6. A chain of DoublyLinkedNodes. For clarity, type parameters have been omitted.
A chain of DoublyLinkedNodes is more difficult to maintain than a chain of singly linked nodes, but it has its uses. We can traverse the chain in either direction. Also, if we have a particular node, we can splice it out of the list without advance knowledge of its predecessor. This allows us to write a method remove() in the DoublyLinkedNode class (Figure 6-7).
Figure 6-7. The remove() method from the DoublyLinkedList class.
|
1 /** Splice this node out of its chain. */ 2 public void remove() { 3 if (prev != null) { 4 prev.next = next; 5 } 6 if (next != null) { 7 next.prev = prev; 8 } 9 } |
The rest of the code for the DoublyLinkedNode class is straightforward. It is left as Problem 6.25.
Exercises
| 6.1 |
Write code to produce the data structure shown in Figure 6-8. Figure 6-8. A circular chain of nodes, for Exercise 6.1. |
| 6.2 |
Can the item field of a ListNode contain a ListNode? Can it be null? |
| 6.3 |
Draw the data structure in Figure 6-6 as it would appear after invoking remove() on the middle node. |
Stacks and Queues
|