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

public AnyType remove( ) figure 17.20b

Class skeleton for
standard LinkedList
class ( continued )

33

{ /* Added in Java 5; same as removeFirst */ }

34

public AnyType removeFirst( )

35

{ /* Figure 17.27 */ }

36

public AnyType removeLast( )

37

{ /* Figure 17.27 */ }

38

public boolean remove( Object x )

39

{ /* Figure 17.28 */ }

40

public AnyType get( int idx )

41

{ /* Figure 17.25 */ }

42

public AnyType set( int idx, AnyType newVal )

43

{ /* Figure 17.25 */ }

44

public AnyType remove( int idx )

45

{ /* Figure 17.27 */ }

46

public void clear( )

47

{ /* Figure 17.22 */ }

48

public Iterator<AnyType> iterator( )

49

{ /* Figure 17.29 */ }

50

public ListIterator<AnyType> listIterator( int idx )

51

{ /* Figure 17.29 */ }

52

53
54 private int theSize;
55 private Node<AnyType> beginMarker;
56 private Node<AnyType> endMarker;
57 private int modCount = 0;
58
59 private static final Node<AnyType> NOT_FOUND = null;
60 private Node<AnyType> findPos( Object x )
61 { /* Figure 17.23 */ }
62 private AnyType remove( Node<AnyType> p )
63 { /* Figure 17.27 */ }
64 private Node<AnyType> getNode( int idx )

{ /* Figure 17.26 */} 65

66 }

class. The iterator pattern was described in Chapter 6. The same pattern was
used in the ArrayList implementation with inner classes in Chapter 15.
The list class keeps track of its size in a data member declared at line 54.
We use this approach so that the size method can be performed in constant
time. modCount is used by the iterators to determine if the list has changed while
an iteration is in progress; the same idea was used in ArrayList . beginMarker
and endMarker correspond to head and tail in Section 17.3. All the methods use
signatures that we have shown before.
Figure 17.21 shows the Node class, which is similar to the ListNode
class. The main difference is that, because we use a doubly linked list, we
have both prev and next links.
Note that inner and nested classes are considered part of the outer class.
Thus, regardless of whether the Node 's data fields are public or private, they will
be visible to the LinkedList class. Because the Node class itself is private, only
the LinkedList class will be able to see that Node is a valid type. Consequently,
in this instance, it does not matter whether the node's data fields are public or