Collections - Java Software Solutions: Foundations of Program Design - page 625

info info info info

list

next next next next

FIGURE 13.3 Deleting a node from a list

Another operation that would be helpful in the list ADT would be a delete
method to remove a particular node. Recall from our discussion in Chapter 3 that
by removing all references to an object, it becomes a candidate for garbage collec-
tion. Figure 13.3 shows how references would be updated to delete a node from
a list. Care must be taken to accomplish the modifications to the references in the
proper order to ensure that other nodes are not lost and that references continue
to refer to valid, appropriate nodes in the list.

Other Dynamic List Representations
You can use different list implementations, depending on the specific
needs of the program you are designing. For example, in some situ-
ations it may make processing easier to implement a

KEY CONCEPT
Many variations on the implementa-
tion of dynamically linked lists can
be defined.

doubly linked
list in which each node has not only a reference to the next node in
the list but another reference to the previous node in the list. Our
generic Node class might be declared as follows:

class Node
{
int info;
Node next, prev;
}

Figure 13.4 shows a doubly linked list. Note that, like a single linked list, the
next reference of the last node is null . Similarly, the previous node of the first
node is null since there is no node that comes before the first one. This type of
structure makes it easy to move back and forth between nodes in the list but
requires more effort to set up and modify.

info info info info

list

next
prev

next next next

prev prev prev

FIGURE 13.4 A doubly linked list