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

a lot of the nonstandard LinkedList code with the concepts presented in
Section 17.3.
Figure 17.23 shows size , which is trivial, and contains , which is also trivial
because it calls the private findPos routine that does all the work. findPos deals
with null values at lines 30-34; otherwise, it would be four lines of code.
Figure 17.24 shows the various add methods. All of these eventually fun-
nel into the last add method at lines 39-47, which splices into the doubly
linked list as was done in Section 17.3. It requires a private routine, getNode ,
whose implementation we will discuss shortly. getNode returns a reference to
1 /**
2 * Returns the number of items in this collection.
3 * @return the number of items in this collection.
4 */
5 public int size( )
6 {
7 return theSize;
8 }
9
10 /**
11 * Tests if some item is in this collection.
12 * @param x any object.
13 * @return true if this collection contains an item equal to x.
14 */
15 public boolean contains( Object x )
16 {
17 return findPos( x ) != NOT_FOUND;
18 }
19
20 /**
21 * Returns the position of first item matching x
22 * in this collection, or NOT_FOUND if not found.
23 * @param x any object.
24 * @return the position of first item matching x
25 * in this collection, or NOT_FOUND if not found.
26 */
27 private Node<AnyType> findPos( Object x )
28 {
29 for( Node<AnyType> p = beginMarker.next; p != endMarker; p = p.next )
30 if( x == null )
31 {
32 if( p.data == null )
33 return p;
34 }
35 else if( x.equals( p.data ) )
36 return p;
37
38 return NOT_FOUND;
39 }
figure 17.23
size and contains for standard LinkedList class