Linked lists - Data Structures and Problem Solving Using Java - page 633

along with its associated iterators. There are lots of routines, but most are
short.

A popular convention is to create a circularly linked list, in which the
last cell's next link references first , which can be done with or without a
header. Typically, it is done without a header because the header's main pur-
pose is to ensure that every node has a previous node, which is already true
for a nonempty circularly linked list. Without a header, we have only the
empty list as a special case. We maintain a reference to the first node, but
that is not the same as a header node. We can use circularly linked lists and
doubly linked lists simultaneously, as shown in Figure 17.18. The circular list
is useful when we want searching to allow wraparound, as is the case for
some text editors. In Exercise 17.16 you are asked to implement a circularly
and doubly linked list.

In a circularly linked
list , the last cell's
next link references
first . This action is
useful when wrap-
around matters.

sorted linked lists

17.4

Sometimes we want to keep the items in a linked list in sorted order, which we
can do with a sorted linked list. The fundamental difference between a sorted
linked list and an unsorted linked list is the insertion routine. Indeed, we can
obtain a sorted list class by simply altering the insertion routine from our
already written list class. Because the insert routine is part of the LinkedList
class, we should be able to base a new derived class, SortedLinkedList , from
LinkedList . We can, and it is shown in Figure 17.19.
The new class has two versions of insert . One version takes a position
and then ignores it; the insertion point is determined solely by the sorted
order. The other version of insert requires more code.
The one-parameter insert uses two LinkedListIterator objects to traverse
down the corresponding list until the correct insertion point is found. At that
point we can apply the base class insert routine.

We can maintain
items in sorted
order by deriving a
SortedLinkedList
class from
LinkedList .

figure 17.18
A circularly and doubly
linked list

a b c d

first