| ArrayList.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7
8 package java.util;
9
10 /**
11 * Resizable-array implementation of the <tt>List</tt> interface. Implements
12 * all optional list operations, and permits all elements, including
13 * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
14 * this class provides methods to manipulate the size of the array that is
15 * used internally to store the list. (This class is roughly equivalent to
16 * <tt>Vector</tt>, except that it is unsynchronized.)<p>
17 *
18 * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
19 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
20 * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
21 * that is, adding n elements requires O(n) time. All of the other operations
22 * run in linear time (roughly speaking). The constant factor is low compared
23 * to that for the <tt>LinkedList</tt> implementation.<p>
24 *
25 * Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
26 * the size of the array used to store the elements in the list. It is always
27 * at least as large as the list size. As elements are added to an ArrayList,
28 * its capacity grows automatically. The details of the growth policy are not
29 * specified beyond the fact that adding an element has constant amortized
30 * time cost.<p>
31 *
32 * An application can increase the capacity of an <tt>ArrayList</tt> instance
33 * before adding a large number of elements using the <tt>ensureCapacity</tt>
34 * operation. This may reduce the amount of incremental reallocation.
35 *
36 * <p><strong>Note that this implementation is not synchronized.</strong>
37 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
38 * and at least one of the threads modifies the list structurally, it
39 * <i>must</i> be synchronized externally. (A structural modification is
40 * any operation that adds or deletes one or more elements, or explicitly
41 * resizes the backing array; merely setting the value of an element is not
42 * a structural modification.) This is typically accomplished by
43 * synchronizing on some object that naturally encapsulates the list.
44 *
45 * If no such object exists, the list should be "wrapped" using the
46 * {@link Collections#synchronizedList Collections.synchronizedList}
47 * method. This is best done at creation time, to prevent accidental
48 * unsynchronized access to the list:<pre>
49 * List list = Collections.synchronizedList(new ArrayList(...));</pre>
50 *
51 * <p>The iterators returned by this class's <tt>iterator</tt> and
52 * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
53 * structurally modified at any time after the iterator is created, in any way
54 * except through the iterator's own <tt>remove</tt> or <tt>add</tt> methods,
55 * the iterator will throw a {@link ConcurrentModificationException}. Thus, in
56 * the face of concurrent modification, the iterator fails quickly and cleanly,
57 * rather than risking arbitrary, non-deterministic behavior at an undetermined
58 * time in the future.<p>
59 *
60 * Note that the fail-fast behavior of an iterator cannot be guaranteed
61 * as it is, generally speaking, impossible to make any hard guarantees in the
62 * presence of unsynchronized concurrent modification. Fail-fast iterators
63 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
64 * Therefore, it would be wrong to write a program that depended on this
65 * exception for its correctness: <i>the fail-fast behavior of iterators
66 * should be used only to detect bugs.</i><p>
67 *
68 * This class is a member of the
69 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
70 * Java Collections Framework</a>.
71 *
72 * @author Josh Bloch
73 * @author Neal Gafter
74 * @version %I%, %G%
75 * @see Collection
76 * @see List
77 * @see LinkedList
78 * @see Vector
79 * @since 1.2
80 */
81
82 public class ArrayList<E> extends AbstractList<E>
83 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
84 {
85 private static final long serialVersionUID = 8683452581122892189L;
86
87 /**
88 * The array buffer into which the elements of the ArrayList are stored.
89 * The capacity of the ArrayList is the length of this array buffer.
90 */
91 private transient Object[] elementData;
92
93 /**
94 * The size of the ArrayList (the number of elements it contains).
95 *
96 * @serial
97 */
98 private int size;
99
100 /**
101 * Constructs an empty list with the specified initial capacity.
102 *
103 * @param initialCapacity the initial capacity of the list
104 * @exception IllegalArgumentException if the specified initial capacity
105 * is negative
106 */
107 public ArrayList(int initialCapacity) {
108 super();
109 if (initialCapacity < 0)
110 throw new IllegalArgumentException("Illegal Capacity: "+
111 initialCapacity);
112 this.elementData = new Object[initialCapacity];
113 }
114
115 /**
116 * Constructs an empty list with an initial capacity of ten.
117 */
118 public ArrayList() {
119 this(10);
120 }
121
122 /**
123 * Constructs a list containing the elements of the specified
124 * collection, in the order they are returned by the collection's
125 * iterator.
126 *
127 * @param c the collection whose elements are to be placed into this list
128 * @throws NullPointerException if the specified collection is null
129 */
130 public ArrayList(Collection<? extends E> c) {
131 elementData = c.toArray();
132 size = elementData.length;
133 // c.toArray might (incorrectly) not return Object[] (see 6260652)
134 if (elementData.getClass() != Object[].class)
135 elementData = Arrays.copyOf(elementData, size, Object[].class);
136 }
137
138 /**
139 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
140 * list's current size. An application can use this operation to minimize
141 * the storage of an <tt>ArrayList</tt> instance.
142 */
143 public void trimToSize() {
144 modCount++;
145 int oldCapacity = elementData.length;
146 if (size < oldCapacity) {
147 elementData = Arrays.copyOf(elementData, size);
148 }
149 }
150
151 /**
152 * Increases the capacity of this <tt>ArrayList</tt> instance, if
153 * necessary, to ensure that it can hold at least the number of elements
154 * specified by the minimum capacity argument.
155 *
156 * @param minCapacity the desired minimum capacity
157 */
158 public void ensureCapacity(int minCapacity) {
159 modCount++;
160 int oldCapacity = elementData.length;
161 if (minCapacity > oldCapacity) {
162 Object oldData[] = elementData;
163 int newCapacity = (oldCapacity * 3)/2 + 1;
164 if (newCapacity < minCapacity)
165 newCapacity = minCapacity;
166 // minCapacity is usually close to size, so this is a win:
167 elementData = Arrays.copyOf(elementData, newCapacity);
168 }
169 }
170
171 /**
172 * Returns the number of elements in this list.
173 *
174 * @return the number of elements in this list
175 */
176 public int size() {
177 return size;
178 }
179
180 /**
181 * Returns <tt>true</tt> if this list contains no elements.
182 *
183 * @return <tt>true</tt> if this list contains no elements
184 */
185 public boolean isEmpty() {
186 return size == 0;
187 }
188
189 /**
190 * Returns <tt>true</tt> if this list contains the specified element.
191 * More formally, returns <tt>true</tt> if and only if this list contains
192 * at least one element <tt>e</tt> such that
193 * <tt>(o==null ? e==null : o.equals(e))</tt>.
194 *
195 * @param o element whose presence in this list is to be tested
196 * @return <tt>true</tt> if this list contains the specified element
197 */
198 public boolean contains(Object o) {
199 return indexOf(o) >= 0;
200 }
201
202 /**
203 * Returns the index of the first occurrence of the specified element
204 * in this list, or -1 if this list does not contain the element.
205 * More formally, returns the lowest index <tt>i</tt> such that
206 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
207 * or -1 if there is no such index.
208 */
209 public int indexOf(Object o) {
210 if (o == null) {
211 for (int i = 0; i < size; i++)
212 if (elementData[i]==null)
213 return i;
214 } else {
215 for (int i = 0; i < size; i++)
216 if (o.equals(elementData[i]))
217 return i;
218 }
219 return -1;
220 }
221
222 /**
223 * Returns the index of the last occurrence of the specified element
224 * in this list, or -1 if this list does not contain the element.
225 * More formally, returns the highest index <tt>i</tt> such that
226 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
227 * or -1 if there is no such index.
228 */
229 public int lastIndexOf(Object o) {
230 if (o == null) {
231 for (int i = size-1; i >= 0; i--)
232 if (elementData[i]==null)
233 return i;
234 } else {
235 for (int i = size-1; i >= 0; i--)
236 if (o.equals(elementData[i]))
237 return i;
238 }
239 return -1;
240 }
241
242 /**
243 * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
244 * elements themselves are not copied.)
245 *
246 * @return a clone of this <tt>ArrayList</tt> instance
247 */
248 public Object clone() {
249 try {
250 ArrayList<E> v = (ArrayList<E>) super.clone();
251 v.elementData = Arrays.copyOf(elementData, size);
252 v.modCount = 0;
253 return v;
254 } catch (CloneNotSupportedException e) {
255 // this shouldn't happen, since we are Cloneable
256 throw new InternalError();
257 }
258 }
259
260 /**
261 * Returns an array containing all of the elements in this list
262 * in proper sequence (from first to last element).
263 *
264 * <p>The returned array will be "safe" in that no references to it are
265 * maintained by this list. (In other words, this method must allocate
266 * a new array). The caller is thus free to modify the returned array.
267 *
268 * <p>This method acts as bridge between array-based and collection-based
269 * APIs.
270 *
271 * @return an array containing all of the elements in this list in
272 * proper sequence
273 */
274 public Object[] toArray() {
275 return Arrays.copyOf(elementData, size);
276 }
277
278 /**
279 * Returns an array containing all of the elements in this list in proper
280 * sequence (from first to last element); the runtime type of the returned
281 * array is that of the specified array. If the list fits in the
282 * specified array, it is returned therein. Otherwise, a new array is
283 * allocated with the runtime type of the specified array and the size of
284 * this list.
285 *
286 * <p>If the list fits in the specified array with room to spare
287 * (i.e., the array has more elements than the list), the element in
288 * the array immediately following the end of the collection is set to
289 * <tt>null</tt>. (This is useful in determining the length of the
290 * list <i>only</i> if the caller knows that the list does not contain
291 * any null elements.)
292 *
293 * @param a the array into which the elements of the list are to
294 * be stored, if it is big enough; otherwise, a new array of the
295 * same runtime type is allocated for this purpose.
296 * @return an array containing the elements of the list
297 * @throws ArrayStoreException if the runtime type of the specified array
298 * is not a supertype of the runtime type of every element in
299 * this list
300 * @throws NullPointerException if the specified array is null
301 */
302 public <T> T[] toArray(T[] a) {
303 if (a.length < size)
304 // Make a new array of a's runtime type, but my contents:
305 return (T[]) Arrays.copyOf(elementData, size, a.getClass());
306 System.arraycopy(elementData, 0, a, 0, size);
307 if (a.length > size)
308 a[size] = null;
309 return a;
310 }
311
312 // Positional Access Operations
313
314 /**
315 * Returns the element at the specified position in this list.
316 *
317 * @param index index of the element to return
318 * @return the element at the specified position in this list
319 * @throws IndexOutOfBoundsException {@inheritDoc}
320 */
321 public E get(int index) {
322 RangeCheck(index);
323
324 return (E) elementData[index];
325 }
326
327 /**
328 * Replaces the element at the specified position in this list with
329 * the specified element.
330 *
331 * @param index index of the element to replace
332 * @param element element to be stored at the specified position
333 * @return the element previously at the specified position
334 * @throws IndexOutOfBoundsException {@inheritDoc}
335 */
336 public E set(int index, E element) {
337 RangeCheck(index);
338
339 E oldValue = (E) elementData[index];
340 elementData[index] = element;
341 return oldValue;
342 }
343
344 /**
345 * Appends the specified element to the end of this list.
346 *
347 * @param e element to be appended to this list
348 * @return <tt>true</tt> (as specified by {@link Collection#add})
349 */
350 public boolean add(E e) {
351 ensureCapacity(size + 1); // Increments modCount!!
352 elementData[size++] = e;
353 return true;
354 }
355
356 /**
357 * Inserts the specified element at the specified position in this
358 * list. Shifts the element currently at that position (if any) and
359 * any subsequent elements to the right (adds one to their indices).
360 *
361 * @param index index at which the specified element is to be inserted
362 * @param element element to be inserted
363 * @throws IndexOutOfBoundsException {@inheritDoc}
364 */
365 public void add(int index, E element) {
366 if (index > size || index < 0)
367 throw new IndexOutOfBoundsException(
368 "Index: "+index+", Size: "+size);
369
370 ensureCapacity(size+1); // Increments modCount!!
371 System.arraycopy(elementData, index, elementData, index + 1,
372 size - index);
373 elementData[index] = element;
374 size++;
375 }
376
377 /**
378 * Removes the element at the specified position in this list.
379 * Shifts any subsequent elements to the left (subtracts one from their
380 * indices).
381 *
382 * @param index the index of the element to be removed
383 * @return the element that was removed from the list
384 * @throws IndexOutOfBoundsException {@inheritDoc}
385 */
386 public E remove(int index) {
387 RangeCheck(index);
388
389 modCount++;
390 E oldValue = (E) elementData[index];
391
392 int numMoved = size - index - 1;
393 if (numMoved > 0)
394 System.arraycopy(elementData, index+1, elementData, index,
395 numMoved);
396 elementData[--size] = null; // Let gc do its work
397
398 return oldValue;
399 }
400
401 /**
402 * Removes the first occurrence of the specified element from this list,
403 * if it is present. If the list does not contain the element, it is
404 * unchanged. More formally, removes the element with the lowest index
405 * <tt>i</tt> such that
406 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
407 * (if such an element exists). Returns <tt>true</tt> if this list
408 * contained the specified element (or equivalently, if this list
409 * changed as a result of the call).
410 *
411 * @param o element to be removed from this list, if present
412 * @return <tt>true</tt> if this list contained the specified element
413 */
414 public boolean remove(Object o) {
415 if (o == null) {
416 for (int index = 0; index < size; index++)
417 if (elementData[index] == null) {
418 fastRemove(index);
419 return true;
420 }
421 } else {
422 for (int index = 0; index < size; index++)
423 if (o.equals(elementData[index])) {
424 fastRemove(index);
425 return true;
426 }
427 }
428 return false;
429 }
430
431 /*
432 * Private remove method that skips bounds checking and does not
433 * return the value removed.
434 */
435 private void fastRemove(int index) {
436 modCount++;
437 int numMoved = size - index - 1;
438 if (numMoved > 0)
439 System.arraycopy(elementData, index+1, elementData, index,
440 numMoved);
441 elementData[--size] = null; // Let gc do its work
442 }
443
444 /**
445 * Removes all of the elements from this list. The list will
446 * be empty after this call returns.
447 */
448 public void clear() {
449 modCount++;
450
451 // Let gc do its work
452 for (int i = 0; i < size; i++)
453 elementData[i] = null;
454
455 size = 0;
456 }
457
458 /**
459 * Appends all of the elements in the specified collection to the end of
460 * this list, in the order that they are returned by the
461 * specified collection's Iterator. The behavior of this operation is
462 * undefined if the specified collection is modified while the operation
463 * is in progress. (This implies that the behavior of this call is
464 * undefined if the specified collection is this list, and this
465 * list is nonempty.)
466 *
467 * @param c collection containing elements to be added to this list
468 * @return <tt>true</tt> if this list changed as a result of the call
469 * @throws NullPointerException if the specified collection is null
470 */
471 public boolean addAll(Collection<? extends E> c) {
472 Object[] a = c.toArray();
473 int numNew = a.length;
474 ensureCapacity(size + numNew); // Increments modCount
475 System.arraycopy(a, 0, elementData, size, numNew);
476 size += numNew;
477 return numNew != 0;
478 }
479
480 /**
481 * Inserts all of the elements in the specified collection into this
482 * list, starting at the specified position. Shifts the element
483 * currently at that position (if any) and any subsequent elements to
484 * the right (increases their indices). The new elements will appear
485 * in the list in the order that they are returned by the
486 * specified collection's iterator.
487 *
488 * @param index index at which to insert the first element from the
489 * specified collection
490 * @param c collection containing elements to be added to this list
491 * @return <tt>true</tt> if this list changed as a result of the call
492 * @throws IndexOutOfBoundsException {@inheritDoc}
493 * @throws NullPointerException if the specified collection is null
494 */
495 public boolean addAll(int index, Collection<? extends E> c) {
496 if (index > size || index < 0)
497 throw new IndexOutOfBoundsException(
498 "Index: " + index + ", Size: " + size);
499
500 Object[] a = c.toArray();
501 int numNew = a.length;
502 ensureCapacity(size + numNew); // Increments modCount
503
504 int numMoved = size - index;
505 if (numMoved > 0)
506 System.arraycopy(elementData, index, elementData, index + numNew,
507 numMoved);
508
509 System.arraycopy(a, 0, elementData, index, numNew);
510 size += numNew;
511 return numNew != 0;
512 }
513
514 /**
515 * Removes from this list all of the elements whose index is between
516 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
517 * Shifts any succeeding elements to the left (reduces their index).
518 * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
519 * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
520 *
521 * @param fromIndex index of first element to be removed
522 * @param toIndex index after last element to be removed
523 * @throws IndexOutOfBoundsException if fromIndex or toIndex out of
524 * range (fromIndex < 0 || fromIndex >= size() || toIndex
525 * > size() || toIndex < fromIndex)
526 */
527 protected void removeRange(int fromIndex, int toIndex) {
528 modCount++;
529 int numMoved = size - toIndex;
530 System.arraycopy(elementData, toIndex, elementData, fromIndex,
531 numMoved);
532
533 // Let gc do its work
534 int newSize = size - (toIndex-fromIndex);
535 while (size != newSize)
536 elementData[--size] = null;
537 }
538
539 /**
540 * Checks if the given index is in range. If not, throws an appropriate
541 * runtime exception. This method does *not* check if the index is
542 * negative: It is always used immediately prior to an array access,
543 * which throws an ArrayIndexOutOfBoundsException if index is negative.
544 */
545 private void RangeCheck(int index) {
546 if (index >= size)
547 throw new IndexOutOfBoundsException(
548 "Index: "+index+", Size: "+size);
549 }
550
551 /**
552 * Save the state of the <tt>ArrayList</tt> instance to a stream (that
553 * is, serialize it).
554 *
555 * @serialData The length of the array backing the <tt>ArrayList</tt>
556 * instance is emitted (int), followed by all of its elements
557 * (each an <tt>Object</tt>) in the proper order.
558 */
559 private void writeObject(java.io.ObjectOutputStream s)
560 throws java.io.IOException{
561 // Write out element count, and any hidden stuff
562 int expectedModCount = modCount;
563 s.defaultWriteObject();
564
565 // Write out array length
566 s.writeInt(elementData.length);
567
568 // Write out all elements in the proper order.
569 for (int i=0; i<size; i++)
570 s.writeObject(elementData[i]);
571
572 if (modCount != expectedModCount) {
573 throw new ConcurrentModificationException();
574 }
575
576 }
577
578 /**
579 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
580 * deserialize it).
581 */
582 private void readObject(java.io.ObjectInputStream s)
583 throws java.io.IOException, ClassNotFoundException {
584 // Read in size, and any hidden stuff
585 s.defaultReadObject();
586
587 // Read in array length and allocate array
588 int arrayLength = s.readInt();
589 Object[] a = elementData = new Object[arrayLength];
590
591 // Read in all elements in the proper order.
592 for (int i=0; i<size; i++)
593 a[i] = s.readObject();
594 }
595 }
596