第3章 表、栈和队列

 1 public class MyArrayList<AnyType> implements Iterable<AnyType>
 2 {
 3     public static final int DEFAULT_CAPACITY = 10;
 4 
 5     public int theSize;
 6     public AnyType[] theItems;
 7 
 8     public MyArrayList()
 9     { doClear(); }
10 
11     public void clear()
12     { doClear(); }
13 
14     public void doClear()
15     { theSize = 0; ensureCapacity(DEFAULT_CAPACITY); }
16 
17     public int size()
18     { return theSize; }
19     public boolean isEmpty()
20     { return size() == 0; }
21     public void trimTosize()
22     { ensureCapacity(size()); }
23 
24     public AnyType get(int idx)
25     {
26         if (idx < 0 || idx >= size())
27             throw new ArrayIndexOutOfBoundsException();
28         return theItems[idx];
29     }
30 
31     public AnyType set(int idx, AnyType newVal)
32     {
33         if(idx < 0 || idx >= size())
34             throw new ArrayIndexOutOfBoundsException();
35         AnyType old = theItems[idx];
36         theItems[idx] = newVal;
37         return old;
38     }
39 
40     public void ensureCapacity(int newCapacity)
41     {
42         if (newCapacity < theSize)
43             return;
44 
45         AnyType[] old = theItems;
46         theItems = (AnyType [])new Object[newCapacity];
47         for (int i = 0; i < size(); i++)
48             theItems[i] = old[i];
49     }
50 
51     public boolean add(AnyType x)
52     {
53         add(size(),x);
54         return true;
55     }
56 
57     public void add(int idx, AnyType x)
58     {
59         if (theItems.length == size())
60             ensureCapacity(size() * 2 + 1);
61         for (int i = theSize; i > idx; i--)
62             theItems[i] = theItems[i - 1];
63         theItems[idx] = x;
64 
65         theSize++;
66     }
67 
68     public AnyType remove(int idx)
69     {
70         AnyType removedItem = theItems[idx];
71         for (int i = idx; i < size() - 1; i++)
72             theItems[i] = theItems[i + 1];
73         theSize--;
74         return removedItem;
75     }
76 
77     public java.util.Iterator<AnyType> iterator()
78     { return new ArrayListIterator(); }
79 
80     private class ArrayListIterator implements java.util.Iterator<AnyType>
81     {
82         private int current = 0;
83 
84         public boolean hasNext()
85         { return current < size(); }
86 
87         public AnyType next()
88         {
89             if (!hasNext())
90                 throw new java.util.NoSuchElementException();
91             return theItems[current++];
92         }
93 
94         public void remove()
95         { MyArrayList.this.remove(--current); }
96     }
97 }

  1 public class MyLinkedList<AnyType> implements Iterable<AnyType>
  2 {
  3     private static class Node<AnyType>
  4     {
  5         public AnyType data;
  6         public Node<AnyType> prev;
  7         public Node<AnyType> next;
  8 
  9         public Node(AnyType d, Node<AnyType> p, Node<AnyType> n)
 10         { data = d; prev = p; next = n; }
 11     }
 12 
 13     public MyLinkedList()
 14     { doClear(); }
 15 
 16     public void clear()
 17     { doClear(); }
 18     public void doClear()
 19     {
 20         beginMarker = new Node<AnyType>(null, null, null);
 21         endMarker = new Node<AnyType>(null, beginMarker, null);
 22         beginMarker.next = endMarker;
 23 
 24         theSize = 0;
 25         modCount++;
 26     }
 27     public int size()
 28     { return theSize; }
 29     public boolean isEmpty()
 30     { return size() == 0; }
 31 
 32     public boolean add(AnyType x)
 33     { add(size(), x); return true; }
 34     public void add(int idx, AnyType x)
 35     { addBefore(getNode(idx, 0, size() - 1), x);}
 36     public AnyType get(int idx)
 37     { return getNode(idx).data; }
 38     public AnyType set(int idx, AnyType newVal)
 39     {
 40         Node<AnyType> p = getNode(idx);
 41         AnyType oldVal = p.data;
 42         p.data = newVal;
 43         return oldVal;
 44     }
 45     public AnyType remove(int idx)
 46     { return remove(getNode(idx)); }
 47 
 48     private void addBefore(Node<AnyType>p, AnyType x)
 49     {
 50         Node<AnyType> newNode = new Node<>(x, p.prev, p);
 51         newNode.prev.next = newNode;
 52         p.prev = newNode;
 53         theSize++;
 54         modCount++;
 55     }
 56     private AnyType remove(Node<AnyType> p)
 57     {
 58         p.next.prev = p.prev;
 59         p.prev.next = p.next;
 60         theSize--;
 61         modCount++;
 62 
 63         return p.data;
 64     }
 65     private Node<AnyType> getNode(int idx)
 66     { return getNode(idx, 0, size() - 1); }
 67     private Node<AnyType> getNode(int idx, int lower, int upper)
 68     {
 69         Node<AnyType>p;
 70 
 71         if (idx < lower || idx > upper)
 72             throw new IndexOutOfBoundsException();
 73 
 74         if (idx < (lower + upper) / 2)
 75         {
 76             p = beginMarker.next;
 77             for (int i = 0; i < idx; i++)
 78                 p = p.next;
 79         }
 80         else
 81         {
 82             p = endMarker;
 83             for (int i = size(); i > idx; i++)
 84                 p = p.prev;
 85         }
 86 
 87         return p;
 88     }
 89 
 90     public java.util.Iterator<AnyType>iterator()
 91     { return new LinkedListIterator(); }
 92     private class LinkedListIterator implements java.util.Iterator<AnyType> {
 93         private Node<AnyType> current = beginMarker.next;
 94         private int expectedModCount = modCount;
 95         private boolean okToRemove = false;
 96 
 97         public boolean hasNext() {
 98             return current != endMarker;
 99         }
100 
101         public AnyType next() {
102             if (modCount != expectedModCount)
103                 throw new java.util.ConcurrentModificationException();
104             if (!hasNext())
105                 throw new java.util.NoSuchElementException();
106 
107             AnyType nextItem = current.data;
108             current = current.next;
109             okToRemove = true;
110             return nextItem;
111         }
112         
113         public void remove()
114         {
115             if (modCount != expectedModCount)
116                 throw new java.util.ConcurrentModificationException();
117             if (!okToRemove)
118                 throw new IllegalStateException();
119             
120             MyLinkedList.this.remove(current.prev);
121             expectedModCount++;
122             okToRemove = false;
123         }
124     }
125 
126     public int theSize;
127     public int modCount = 0;
128     public Node<AnyType> beginMarker;
129     public Node<AnyType> endMarker;
130 }