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

The last routine we write here is an insertion routine. We pass an element
to be inserted and a position p . This particular insertion routine inserts an ele-
ment after position p , as shown in Figure 17.14. Note that the insert routine
makes no use of the list it is in; it depends only on p .

The insert routine
takes constant
time.

With the exception of the find and findPrevious routines (and remove ,
which calls findPrevious ), all the operations that we have coded so far take
O (1) time. The find and findPrevious routines take O ( N ) time in the worst
case because the entire list might need to be traversed if the element either is
not found or is last in the list. On average, the running time is O ( N ), because
on average half the list must be traversed.

The find and
findPrevious
routines take O ( N )
time.

We certainly could have added more operations, but this basic set is quite
powerful. Some operations, such as retreat , are not efficiently supported by
this version of the linked list; variations on the linked list that allow constant-
time implementation of that and other operators are discussed later in this
chapter.

The retreat
method is not effi-
ciently supported. A
doubly linked list is
used if that is a lia-
bility.

doubly linked lists
and circularly linked lists

17.3

As we mentioned in Section 17.2, the singly linked list does not efficiently
support some important operations. For instance, although it is easy to go to
the front of the list, it is time consuming to go to the end. Although we can
easily advance via advance , implementing retreat cannot be done efficiently
with only a next link. In some applications that might be crucial. For instance,

A doubly linked list
allows bidirectional
traversal by storing
two links per node.

1 /**
2 * Insert after p.
3 * @param x the item to insert.
4 * @param p the position prior to the newly inserted item.
5 */
6 public void insert( AnyType x, LinkedListIterator<AnyType> p )
7 {
8 if( p != null && p.current != null )
9 p.current.next = new ListNode<AnyType>( x, p.current.next );
10 }

figure 17.14
The insertion routine for the LinkedList class