ArrayList源码分析详解编程语言

1 public class ArrayList<E> extends AbstractList<E> 
2         implements List<E>, RandomAccess, Cloneable, java.io.Serializable

1     /** 
2      * 定义ArrayList内部保存数据用的数组。 
3      */ 
4     private transient Object[] elementData; 
5  
6     /** 
7      * 定义ArrayList的实际包含数据的长度。 
8      */ 
9     private int size;

 1     /** 
 2      * 根据传入的initialCapacity来定义一个数组。如果initialCapacity小于0，则抛出IllegalArgument异常。 
 3      */ 
 4     public ArrayList(int initialCapacity) { 
 5     super(); 
 6         if (initialCapacity < 0) 
 7             throw new IllegalArgumentException("Illegal Capacity: "+ 
 8                                                initialCapacity); 
 9     this.elementData = new Object[initialCapacity]; 
10     } 
11  
12     /** 
13      * 默认创建一个长度为10的Object类型数组。 
14      */ 
15     public ArrayList() { 
16     this(10); 
17     } 
18      
19      /** 
20      * 根据传入的集合来初始化。如果传入的集合的toArray()方法返回的不是Object[]类型的，则利用Arrays.copyOf来转为Object[]类型 
21      */ 
22     public ArrayList(Collection<? extends E> c) { 
23     elementData = c.toArray(); 
24     size = elementData.length; 
25     // c.toArray might (incorrectly) not return Object[] (see 6260652) 
26     if (elementData.getClass() != Object[].class) 
27         elementData = Arrays.copyOf(elementData, size, Object[].class); 
28     }

 1     /** 
 2      * 此方法将数组elementData中没有用来存储数据的内存释放出来，减少占用的内存空间。 
 3      * 使得list的size和capacity大小一样。 
 4      */ 
 5     public void trimToSize() { 
 6     modCount++; 
 7     int oldCapacity = elementData.length; 
 8     if (size < oldCapacity) { 
 9             elementData = Arrays.copyOf(elementData, size); 
10     } 
11     }

 1     /** 
 2      * 数组扩容用的方法。如果传入的minCapacity还没有以前的容量大，则什么都不做；如果比以前的容量大，那也不一定就按照minCapacity的大小来扩容。 
 3      * 首先，将以前的容量扩大到1.5倍再加上1，如果扩大后的容量比minCapacity小，则容量最终还是扩大到minCapacity，否则就扩大到以前的1.5倍加上1的大小。 
 4      * 也就是说，扩容至少扩大到以前的1.5倍再加上1。 
 5      */ 
 6     public void ensureCapacity(int minCapacity) { 
 7     modCount++; 
 8     int oldCapacity = elementData.length; 
 9     if (minCapacity > oldCapacity) { 
10         Object oldData[] = elementData; 
11         int newCapacity = (oldCapacity * 3)/2 + 1; 
12             if (newCapacity < minCapacity) 
13         newCapacity = minCapacity; 
14             // minCapacity is usually close to size, so this is a win: 
15             elementData = Arrays.copyOf(elementData, newCapacity); 
16     } 
17     }

 1     /** 
 2      * 返回list的大小，注意不是数组的容量大小。 
 3      */ 
 4     public int size() { 
 5     return size; 
 6     } 
 7  
 8     /** 
 9      * 根据list的大小是否为0来判断list是否为空 
10      */ 
11     public boolean isEmpty() { 
12     return size == 0; 
13     }

 1     /** 
 2      * 从数组下标0开始查找o，找到的话就返回其下标，如果没有找到，则返回-1。 
 3      */ 
 4     public int indexOf(Object o) { 
 5     if (o == null) { 
 6         for (int i = 0; i < size; i++) 
 7         if (elementData[i]==null) 
 8             return i; 
 9     } else { 
10         for (int i = 0; i < size; i++) 
11         if (o.equals(elementData[i])) 
12             return i; 
13     } 
14     return -1; 
15     } 
16  
17     /** 
18      * 从数组最后一位开始向前查找o，找到的话返回其下标，否则返回-1。 
19      */ 
20     public int lastIndexOf(Object o) { 
21     if (o == null) { 
22         for (int i = size-1; i >= 0; i--) 
23         if (elementData[i]==null) 
24             return i; 
25     } else { 
26         for (int i = size-1; i >= 0; i--) 
27         if (o.equals(elementData[i])) 
28             return i; 
29     } 
30     return -1; 
31     }

1     /** 
2      * 调用indexOf方法来判断o是否存在于list中。 
3      */ 
4     public boolean contains(Object o) { 
5     return indexOf(o) >= 0; 
6     }

 1     /** 
 2      * 此方法为浅层复制，不是深层复制 
 3      */ 
 4     public Object clone() { 
 5     try { 
 6         ArrayList<E> v = (ArrayList<E>) super.clone(); 
 7         v.elementData = Arrays.copyOf(elementData, size); 
 8         v.modCount = 0; 
 9         return v; 
10     } catch (CloneNotSupportedException e) { 
11         // this shouldn't happen, since we are Cloneable 
12         throw new InternalError(); 
13     } 
14     }

 1     /** 
 2      * 将list转为数组，注意是重新创建了一个长度相同（为size）的数组，与list内部的数组不是同一个 
 3      */ 
 4     public Object[] toArray() { 
 5         return Arrays.copyOf(elementData, size); 
 6     } 
 7  
 8     /** 
 9      * 将list转为数组，数组的类型由传入的参数a决定。 
10      * 如果a的长度小于list的长度，则从list的第一个元素开始直至填满a； 
11      * 如果a的长度大于list的长度，则把list的元素全部填入a后，将a[a.length]设为null。 
12      */ 
13     public <T> T[] toArray(T[] a) { 
14         if (a.length < size) 
15             // Make a new array of a's runtime type, but my contents: 
16             return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 
17     System.arraycopy(elementData, 0, a, 0, size); 
18         if (a.length > size) 
19             a[size] = null; 
20         return a; 
21     }

 1     /** 
 2      * 此方法为判断index是否超出list的长度size，注意不是list的容量。 
 3      * 如果超出，则抛出IndexOutOfBounds异常。 
 4      * list的很多方法都会先调用此方法来做判断。 
 5      */ 
 6     private void RangeCheck(int index) { 
 7     if (index >= size) 
 8         throw new IndexOutOfBoundsException( 
 9         "Index: "+index+", Size: "+size); 
10     }

  1     /** 
  2      * 首先调用RangeCheck方法判断index合法性，然后直接返回数组对应下标的值。 
  3      */ 
  4     public E get(int index) { 
  5     RangeCheck(index); 
  6  
  7     return (E) elementData[index]; 
  8     } 
  9  
 10     /** 
 11      * 首先调用RangeCheck方法判断index的合法性，然后定义一个变量oldValue指向数组对应下标的值， 
 12      * 再将此下标的值换为传入的参数element，最后返回旧的值oldValue。 
 13      */ 
 14     public E set(int index, E element) { 
 15     RangeCheck(index); 
 16  
 17     E oldValue = (E) elementData[index]; 
 18     elementData[index] = element; 
 19     return oldValue; 
 20     } 
 21  
 22     /** 
 23      * 此方法为往list的下标为size的地方添加元素e。 
 24      * 首先对数组进行扩容，然后将数组下标为size的元素赋为e。 
 25      */ 
 26     public boolean add(E e) { 
 27     ensureCapacity(size + 1);  // Increments modCount!! 
 28     elementData[size++] = e;   // 这种写法一举两得，既赋了值，又把size加了1，可以省下一行代码。 
 29     return true; 
 30     } 
 31  
 32     /** 
 33      * 此方法为在指定下标处添加元素。 
 34      * 首先判断传入的index是否合法，注意index可以等于size，这时应该相当于前面的add(E e)方法。 
 35      * 然后也是先把数组扩容，接着通过System的arraycopy方法把数组从下表index开始到size-1处的元素整体往后移一位。 
 36      */ 
 37     public void add(int index, E element) { 
 38     if (index > size || index < 0) 
 39         throw new IndexOutOfBoundsException( 
 40         "Index: "+index+", Size: "+size); 
 41  
 42     ensureCapacity(size+1);  // Increments modCount!! 
 43     System.arraycopy(elementData, index, elementData, index + 1, 
 44              size - index); 
 45     elementData[index] = element; 
 46     size++; 
 47     } 
 48  
 49     /** 
 50      * 此方法为删除指定下标处的元素。 
 51      * 首先判断index的合法性。然后定义一个变量oldValue获取数组指定下标处的元素。 
 52      * 然后定义numMoved变量获取（size - index - 1）的值，如果为0，则表示index为list的最后一个元素的下标，那么就木有必要再进行数组元素的移动了。 
 53      * 否则index不是最后一个元素的下标，那么把数组里的下标为index+1的元素开始到最后一个元素全部往前移动一位。 
 54      * 再将list的最后一位赋值为null，同时将size减少1。 
 55      * 最后返回oldValue，即被删除的元素。 
 56      */ 
 57     public E remove(int index) { 
 58     RangeCheck(index); 
 59  
 60     modCount++; 
 61     E oldValue = (E) elementData[index]; 
 62  
 63     int numMoved = size - index - 1; 
 64     if (numMoved > 0) 
 65         System.arraycopy(elementData, index+1, elementData, index, 
 66                  numMoved); 
 67     elementData[--size] = null; // Let gc do its work 
 68  
 69     return oldValue; 
 70     } 
 71  
 72     /** 
 73      * 删除数组里第一个值为o的元素。 
 74      * 先判断o是否为null，如果是null，则遍历数组，发现null的话，删除null，并返回true； 
 75      * 如果不是null，则遍历数组，调用o的equals方法一次和数组元素进行比较，如果为true则删除此元素并返回true。 
 76      */ 
 77     public boolean remove(Object o) { 
 78     if (o == null) { 
 79             for (int index = 0; index < size; index++) 
 80         if (elementData[index] == null) { 
 81             fastRemove(index); 
 82             return true; 
 83         } 
 84     } else { 
 85         for (int index = 0; index < size; index++) 
 86         if (o.equals(elementData[index])) { 
 87             fastRemove(index); 
 88             return true; 
 89         } 
 90         } 
 91     return false; 
 92     } 
 93  
 94     /* 
 95      * 私有的删除方法，与remove方法有两点区别：①不会返回被删除的元素；②不会调用RangeCheck方法进行check。 
 96      */ 
 97     private void fastRemove(int index) { 
 98         modCount++; 
 99         int numMoved = size - index - 1; 
100         if (numMoved > 0) 
101             System.arraycopy(elementData, index+1, elementData, index, 
102                              numMoved); 
103         elementData[--size] = null; // Let gc do its work 
104     } 
105  
106     /** 
107      * 此方法是清空list，遍历数组，将里面所有的元素都赋值为null。同时，size也赋值为0。 
108      */ 
109     public void clear() { 
110     modCount++; 
111  
112     // Let gc do its work 
113     for (int i = 0; i < size; i++) 
114         elementData[i] = null; 
115  
116     size = 0; 
117     } 
118  
119     /** 
120      * Appends all of the elements in the specified collection to the end of 
121      * this list, in the order that they are returned by the 
122      * specified collection's Iterator.  The behavior of this operation is 
123      * undefined if the specified collection is modified while the operation 
124      * is in progress.  (This implies that the behavior of this call is 
125      * undefined if the specified collection is this list, and this 
126      * list is nonempty.) 
127      * 
128      * @param c collection containing elements to be added to this list 
129      * @return <tt>true</tt> if this list changed as a result of the call 
130      * @throws NullPointerException if the specified collection is null 
131      */ 
132     public boolean addAll(Collection<? extends E> c) { 
133     Object[] a = c.toArray(); 
134         int numNew = a.length; 
135     ensureCapacity(size + numNew);  // Increments modCount 
136         System.arraycopy(a, 0, elementData, size, numNew); 
137         size += numNew; 
138     return numNew != 0; 
139     } 
140  
141     /** 
142      * 把此方法传入的集合c依次从list的下标index开始添加，同时把原先下标index往后的所有元素再往后移动c.size()位。 
143      */ 
144     public boolean addAll(int index, Collection<? extends E> c) { 
145     if (index > size || index < 0) 
146         throw new IndexOutOfBoundsException( 
147         "Index: " + index + ", Size: " + size); 
148  
149     Object[] a = c.toArray(); 
150     int numNew = a.length; 
151     ensureCapacity(size + numNew);  // Increments modCount 
152  
153     int numMoved = size - index; 
154     if (numMoved > 0) 
155         System.arraycopy(elementData, index, elementData, index + numNew, 
156                  numMoved); 
157  
158         System.arraycopy(a, 0, elementData, index, numNew); 
159     size += numNew; 
160     return numNew != 0; 
161     } 
162  
163     /** 
164      * 删除下标从fromIndex到toIndex-1的元素。 
165      * 首先将下标从toIndex到size-1的元素全部向前移动size-toIndex位， 
166      * 然后将list的后toIndex-fromIndex位的元素的值赋为null。 
167      */ 
168     protected void removeRange(int fromIndex, int toIndex) { 
169     modCount++; 
170     int numMoved = size - toIndex; 
171         System.arraycopy(elementData, toIndex, elementData, fromIndex, 
172                          numMoved); 
173  
174     // Let gc do its work 
175     int newSize = size - (toIndex-fromIndex); 
176     while (size != newSize) 
177         elementData[--size] = null; 
178     }

 1     /** 
 2      * 序列化时，先执行defaultWriteObject()方法；然后再把数组的长度也写入流中，最后分别把数组中的每个元素都写到流中。 
 3      */ 
 4     private void writeObject(java.io.ObjectOutputStream s) 
 5         throws java.io.IOException{ 
 6     // Write out element count, and any hidden stuff 
 7     int expectedModCount = modCount; 
 8     s.defaultWriteObject(); 
 9  
10         // Write out array length 
11         s.writeInt(elementData.length); 
12  
13     // Write out all elements in the proper order. 
14     for (int i=0; i<size; i++) 
15             s.writeObject(elementData[i]); 
16  
17     if (modCount != expectedModCount) { 
18             throw new ConcurrentModificationException(); 
19         } 
20  
21     } 
22  
23     /** 
24      * 从流中读取元素，先调用defaultReadObject()方法，然后依次读取数组长度，接着是数组当中的每个元素信息。 
25      * 和writeObject的写入顺序一样。 
26      */ 
27     private void readObject(java.io.ObjectInputStream s) 
28         throws java.io.IOException, ClassNotFoundException { 
29     // Read in size, and any hidden stuff 
30     s.defaultReadObject(); 
31  
32         // Read in array length and allocate array 
33         int arrayLength = s.readInt(); 
34         Object[] a = elementData = new Object[arrayLength]; 
35  
36     // Read in all elements in the proper order. 
37     for (int i=0; i<size; i++) 
38             a[i] = s.readObject(); 
39     }