Linked Lists - Building Java Programs: A Back to Basics Approach - page 971

Chapter Summary

A linked list is a data structure that stores an ordered
sequence of elements using a chain of objects called
nodes. Each node refers to at least one other node in the
list. The overall list object keeps references to a small
number of these nodes, such as the front or back node.

When you are performing complex list operations such
as adding to a sorted list, it is important to think about all
of the possible cases in which the method might be called.
Is the list empty, does it have a single element, or does
it have many elements? Will our element of interest be
added or removed from the beginning, middle, or end of
the list?

A node has a data and next field. You can connect one
node to another by assigning its next field to refer to
the other node. It is possible to make chains of nodes of
arbitrary length in this way.

When you create two tests separated by an && or || ,be
sure to place the more “robust” test before the more
“sensitive” test, especially if the robust test's failure
would cause the sensitive test to throw an exception.

The end of a chain of nodes, the next reference of the last
node, is null .

One way to traverse a list is with two current references
that are one node apart, also called the inchworm
approach.

When you are trying to rearrange one ordering of nodes
into another, you must be careful about the order in which
you change the references. If you change the ordering so
that no variable or field refers to a given node, the node is
lost and cannot be recovered.

A list interface can be created to represent an abstract
data type that is implemented by both array lists and
linked lists. The list interface allows client code to treat
both types of lists the same way.

You can traverse a linked list by creating a temporary node
reference (called current in our examples) and looping
through the overall list of nodes. Such a loop can stop
when the program finds a particular value or encounters a
null next node (the end of the list).

A linked list iterator keeps a reference to its current
position in the list. This class is often written as an inner
class inside the overall list class so that the iterator has
direct access to the list's nodes.

It is often desirable to stop one node before the relevant
part of the list that you are searching for, because, in order
to change the list, you often must change the next field of
the prior node.

A generic linked list class can store objects of any type E
rather than just integers.

Self-Check Problems

Section 16.1: Working with Nodes
1. What is the difference between a linked list and an array list? How are they similar?

2. What is the difference between a linked node and a linked list? How are they related and connected?