A linked list is a List object (that is, an object in a class that implements the List interface)
in which the following property is satisfied:
Each element is contained in an object, called an Entry object, that also includes a reference,
called a link, to another Entry object. For each Entry object except the one that
holds the last element in the collection, the link is to the Entry object that contains the
next element in the collection.
A linked list that also satisfies the following property:
Each Entry object except the first also includes a link to the Entry object that contains the
previous element.
is called a doubly linked list. Otherwise, it is called a singly linked list.
The SinglyLinkedList class (partially) implements a singly linked list. The purpose
of developing the SinglyLinkedList class is to introduce you to the topics of
links and iterators, and thus to prepare you for the focal point of the chapter: the
LinkedList class, part of the Java Collections Framework. LinkedList objects lack the
random-access ability of ArrayList objects. But, by using an iterator, an element can
be added to or removed from a LinkedList in only constant time; for adding to or
removing from an ArrayList object, worstTime(n) is linear in n. This advantage of
LinkedList objects is best suited for consecutive insertions and deletions because, for
the task of getting to the index of the first insertion or deletion, worstTime(n) is linear
in n.
The Java Collections Framework’s implementation of the LinkedList class stores
the elements in a circular, doubly linked structure with a dummy entry. Another possible
implementation is a noncircular, doubly linked structure with head and tail fields.
The application, a simple line editor, took advantage of the LinkedList class’s
ability to quickly make consecutive insertions and deletions anywhere in a Linked
List object.
