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

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting

Recursion

Part IV: Trees and Sets

Trees

Sets

Part V: Advanced Topics

Advanced Linear Structures

Strings

Advanced Trees

Graphs

Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading

Index

show all menu





Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake
Similar book on Amazon

Flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net