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

1 /**
2 * Remove the first occurrence of an item.
3 * @param x the item to remove.
4 */
5 public void remove( AnyType x )
6 {
7 LinkedListIterator<AnyType> p = findPrevious( x );
8
9 if( p.current.next != null )
10 p.current.next = p.current.next.next; // Bypass deleted node
11 }

figure 17.12
The remove routine for the LinkedList class

If the first half of the and is false, the result is automatically false and the sec-
ond half is not evaluated.

Our next routine removes some element x from the list. We need to decide
what to do if x occurs more than once or not at all. Our routine removes the
first occurrence of x and does nothing if x is not in the list. To make that hap-
pen, we find p , which is the cell prior to the one containing x , via a call to
findPrevious . The code for implementing the remove routine is shown in
Figure 17.12. This code is not foolproof: There may be two iterators, and one
can be left logically in limbo if the other removes a node. The findPrevious
routine is similar to the find routine and is shown in Figure 17.13.

This code is not
foolproof: There
may be two itera-
tors, and one can
be left dangling if
the other removes
a node.

1 /**
2 * Return iterator prior to the first node containing an item.
3 * @param x the item to search for.
4 * @return appropriate iterator if the item is found. Otherwise, the
5 * iterator corresponding to the last element in the list is returned.
6 */
7 public LinkedListIterator<AnyType> findPrevious( AnyType x )
8 {
9 ListNode<AnyType> itr = header;
10
11 while( itr.next != null && !itr.next.element.equals( x ) )
12 itr = itr.next;
13
14 return new LinkedListIterator<AnyType>( itr );
15 }

figure 17.13
The findPrevious routine—similar to the find routine—for use with remove