Java-集合类 List篇

List作为一个集合类的接口，我们实际使用中通常是使用其实现类，常用的实现类有ArrayList、Vector、LinkedList，以及Vector的子类Stack。

List 因为是基于基于数组或链表存储，所以它是有序的、允许空、且可重复。

先来看下它的继承、实现关系：

最高接口为Iterable，该接口中只有一个方法为iterator()，查看下JDK源码，该方法返回一个Iterator类型的接口。那么为什么不直接继承Iterator接口呢？

 1 /*
 2  * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
 3  * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 4  *
 5  *
 6  *
 7  *
 8  *
 9  *
10  *
11  *
12  *
13  *
14  *
15  *
16  *
17  *
18  *
19  *
20  *
21  *
22  *
23  *
24  */
25 
26 package java.lang;
27 
28 import java.util.Iterator;
29 
30 /**
31  * Implementing this interface allows an object to be the target of
32  * the "foreach" statement.
33  *
34  * @param <T> the type of elements returned by the iterator
35  *
36  * @since 1.5
37  */
38 public interface Iterable<T> {
39 
40     /**
41      * Returns an iterator over a set of elements of type T.
42      *
43      * @return an Iterator.
44      */
45     Iterator<T> iterator();
46 }

我们看下 Iterator的源码：

/*
 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

/**
 * An iterator over a collection.  {@code Iterator} takes the place of
 * {@link Enumeration} in the Java Collections Framework.  Iterators
 * differ from enumerations in two ways:
 *
 * <ul>
 *      <li> Iterators allow the caller to remove elements from the
 *           underlying collection during the iteration with well-defined
 *           semantics.
 *      <li> Method names have been improved.
 * </ul>
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <E> the type of elements returned by this iterator
 *
 * @author  Josh Bloch
 * @see Collection
 * @see ListIterator
 * @see Iterable
 * @since 1.2
 */
public interface Iterator<E> {
    /**
     * Returns {@code true} if the iteration has more elements.
     * (In other words, returns {@code true} if {@link #next} would
     * return an element rather than throwing an exception.)
     *
     * @return {@code true} if the iteration has more elements
     */
    boolean hasNext();

    /**
     * Returns the next element in the iteration.
     *
     * @return the next element in the iteration
     * @throws NoSuchElementException if the iteration has no more elements
     */
    E next();

    /**
     * Removes from the underlying collection the last element returned
     * by this iterator (optional operation).  This method can be called
     * only once per call to {@link #next}.  The behavior of an iterator
     * is unspecified if the underlying collection is modified while the
     * iteration is in progress in any way other than by calling this
     * method.
     *
     * @throws UnsupportedOperationException if the {@code remove}
     *         operation is not supported by this iterator
     *
     * @throws IllegalStateException if the {@code next} method has not
     *         yet been called, or the {@code remove} method has already
     *         been called after the last call to the {@code next}
     *         method
     */
    void remove();
}

View Code

其主要方法 hasNext() 、next ()方法，当我们集合在传递过程中，是无法预知它的当前迭代位置的，所以hasNext和next（）方法将失效，而继承Iterable接口则可以返回一个迭代器，每次都是从头开始计数，且多个迭代器之间不干扰！

我们再来看下AbstractList抽象类:

  1 /*
  2  * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
  3  * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  4  *
  5  *
  6  *
  7  *
  8  *
  9  *
 10  *
 11  *
 12  *
 13  *
 14  *
 15  *
 16  *
 17  *
 18  *
 19  *
 20  *
 21  *
 22  *
 23  *
 24  */
 25 
 26 package java.util;
 27 
 28 /**
 29  * This class provides a skeletal implementation of the {@link List}
 30  * interface to minimize the effort required to implement this interface
 31  * backed by a "random access" data store (such as an array).  For sequential
 32  * access data (such as a linked list), {@link AbstractSequentialList} should
 33  * be used in preference to this class.
 34  *
 35  * <p>To implement an unmodifiable list, the programmer needs only to extend
 36  * this class and provide implementations for the {@link #get(int)} and
 37  * {@link List#size() size()} methods.
 38  *
 39  * <p>To implement a modifiable list, the programmer must additionally
 40  * override the {@link #set(int, Object) set(int, E)} method (which otherwise
 41  * throws an {@code UnsupportedOperationException}).  If the list is
 42  * variable-size the programmer must additionally override the
 43  * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods.
 44  *
 45  * <p>The programmer should generally provide a void (no argument) and collection
 46  * constructor, as per the recommendation in the {@link Collection} interface
 47  * specification.
 48  *
 49  * <p>Unlike the other abstract collection implementations, the programmer does
 50  * <i>not</i> have to provide an iterator implementation; the iterator and
 51  * list iterator are implemented by this class, on top of the "random access"
 52  * methods:
 53  * {@link #get(int)},
 54  * {@link #set(int, Object) set(int, E)},
 55  * {@link #add(int, Object) add(int, E)} and
 56  * {@link #remove(int)}.
 57  *
 58  * <p>The documentation for each non-abstract method in this class describes its
 59  * implementation in detail.  Each of these methods may be overridden if the
 60  * collection being implemented admits a more efficient implementation.
 61  *
 62  * <p>This class is a member of the
 63  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 64  * Java Collections Framework</a>.
 65  *
 66  * @author  Josh Bloch
 67  * @author  Neal Gafter
 68  * @since 1.2
 69  */
 70 
 71 public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
 72     /**
 73      * Sole constructor.  (For invocation by subclass constructors, typically
 74      * implicit.)
 75      */
 76     protected AbstractList() {
 77     }
 78 
 79     /**
 80      * Appends the specified element to the end of this list (optional
 81      * operation).
 82      *
 83      * <p>Lists that support this operation may place limitations on what
 84      * elements may be added to this list.  In particular, some
 85      * lists will refuse to add null elements, and others will impose
 86      * restrictions on the type of elements that may be added.  List
 87      * classes should clearly specify in their documentation any restrictions
 88      * on what elements may be added.
 89      *
 90      * <p>This implementation calls {@code add(size(), e)}.
 91      *
 92      * <p>Note that this implementation throws an
 93      * {@code UnsupportedOperationException} unless
 94      * {@link #add(int, Object) add(int, E)} is overridden.
 95      *
 96      * @param e element to be appended to this list
 97      * @return {@code true} (as specified by {@link Collection#add})
 98      * @throws UnsupportedOperationException if the {@code add} operation
 99      *         is not supported by this list
100      * @throws ClassCastException if the class of the specified element
101      *         prevents it from being added to this list
102      * @throws NullPointerException if the specified element is null and this
103      *         list does not permit null elements
104      * @throws IllegalArgumentException if some property of this element
105      *         prevents it from being added to this list
106      */
107     public boolean add(E e) {
108         add(size(), e);
109         return true;
110     }
111 
112     /**
113      * {@inheritDoc}
114      *
115      * @throws IndexOutOfBoundsException {@inheritDoc}
116      */
117     abstract public E get(int index);
118 
119     /**
120      * {@inheritDoc}
121      *
122      * <p>This implementation always throws an
123      * {@code UnsupportedOperationException}.
124      *
125      * @throws UnsupportedOperationException {@inheritDoc}
126      * @throws ClassCastException            {@inheritDoc}
127      * @throws NullPointerException          {@inheritDoc}
128      * @throws IllegalArgumentException      {@inheritDoc}
129      * @throws IndexOutOfBoundsException     {@inheritDoc}
130      */
131     public E set(int index, E element) {
132         throw new UnsupportedOperationException();
133     }
134 
135     /**
136      * {@inheritDoc}
137      *
138      * <p>This implementation always throws an
139      * {@code UnsupportedOperationException}.
140      *
141      * @throws UnsupportedOperationException {@inheritDoc}
142      * @throws ClassCastException            {@inheritDoc}
143      * @throws NullPointerException          {@inheritDoc}
144      * @throws IllegalArgumentException      {@inheritDoc}
145      * @throws IndexOutOfBoundsException     {@inheritDoc}
146      */
147     public void add(int index, E element) {
148         throw new UnsupportedOperationException();
149     }
150 
151     /**
152      * {@inheritDoc}
153      *
154      * <p>This implementation always throws an
155      * {@code UnsupportedOperationException}.
156      *
157      * @throws UnsupportedOperationException {@inheritDoc}
158      * @throws IndexOutOfBoundsException     {@inheritDoc}
159      */
160     public E remove(int index) {
161         throw new UnsupportedOperationException();
162     }
163 
164 
165     // Search Operations
166 
167     /**
168      * {@inheritDoc}
169      *
170      * <p>This implementation first gets a list iterator (with
171      * {@code listIterator()}).  Then, it iterates over the list until the
172      * specified element is found or the end of the list is reached.
173      *
174      * @throws ClassCastException   {@inheritDoc}
175      * @throws NullPointerException {@inheritDoc}
176      */
177     public int indexOf(Object o) {
178         ListIterator<E> it = listIterator();
179         if (o==null) {
180             while (it.hasNext())
181                 if (it.next()==null)
182                     return it.previousIndex();
183         } else {
184             while (it.hasNext())
185                 if (o.equals(it.next()))
186                     return it.previousIndex();
187         }
188         return -1;
189     }
190 
191     /**
192      * {@inheritDoc}
193      *
194      * <p>This implementation first gets a list iterator that points to the end
195      * of the list (with {@code listIterator(size())}).  Then, it iterates
196      * backwards over the list until the specified element is found, or the
197      * beginning of the list is reached.
198      *
199      * @throws ClassCastException   {@inheritDoc}
200      * @throws NullPointerException {@inheritDoc}
201      */
202     public int lastIndexOf(Object o) {
203         ListIterator<E> it = listIterator(size());
204         if (o==null) {
205             while (it.hasPrevious())
206                 if (it.previous()==null)
207                     return it.nextIndex();
208         } else {
209             while (it.hasPrevious())
210                 if (o.equals(it.previous()))
211                     return it.nextIndex();
212         }
213         return -1;
214     }
215 
216 
217     // Bulk Operations
218 
219     /**
220      * Removes all of the elements from this list (optional operation).
221      * The list will be empty after this call returns.
222      *
223      * <p>This implementation calls {@code removeRange(0, size())}.
224      *
225      * <p>Note that this implementation throws an
226      * {@code UnsupportedOperationException} unless {@code remove(int
227      * index)} or {@code removeRange(int fromIndex, int toIndex)} is
228      * overridden.
229      *
230      * @throws UnsupportedOperationException if the {@code clear} operation
231      *         is not supported by this list
232      */
233     public void clear() {
234         removeRange(0, size());
235     }
236 
237     /**
238      * {@inheritDoc}
239      *
240      * <p>This implementation gets an iterator over the specified collection
241      * and iterates over it, inserting the elements obtained from the
242      * iterator into this list at the appropriate position, one at a time,
243      * using {@code add(int, E)}.
244      * Many implementations will override this method for efficiency.
245      *
246      * <p>Note that this implementation throws an
247      * {@code UnsupportedOperationException} unless
248      * {@link #add(int, Object) add(int, E)} is overridden.
249      *
250      * @throws UnsupportedOperationException {@inheritDoc}
251      * @throws ClassCastException            {@inheritDoc}
252      * @throws NullPointerException          {@inheritDoc}
253      * @throws IllegalArgumentException      {@inheritDoc}
254      * @throws IndexOutOfBoundsException     {@inheritDoc}
255      */
256     public boolean addAll(int index, Collection<? extends E> c) {
257         rangeCheckForAdd(index);
258         boolean modified = false;
259         for (E e : c) {
260             add(index++, e);
261             modified = true;
262         }
263         return modified;
264     }
265 
266 
267     // Iterators
268 
269     /**
270      * Returns an iterator over the elements in this list in proper sequence.
271      *
272      * <p>This implementation returns a straightforward implementation of the
273      * iterator interface, relying on the backing list's {@code size()},
274      * {@code get(int)}, and {@code remove(int)} methods.
275      *
276      * <p>Note that the iterator returned by this method will throw an
277      * {@link UnsupportedOperationException} in response to its
278      * {@code remove} method unless the list's {@code remove(int)} method is
279      * overridden.
280      *
281      * <p>This implementation can be made to throw runtime exceptions in the
282      * face of concurrent modification, as described in the specification
283      * for the (protected) {@link #modCount} field.
284      *
285      * @return an iterator over the elements in this list in proper sequence
286      */
287     public Iterator<E> iterator() {
288         return new Itr();
289     }
290 
291     /**
292      * {@inheritDoc}
293      *
294      * <p>This implementation returns {@code listIterator(0)}.
295      *
296      * @see #listIterator(int)
297      */
298     public ListIterator<E> listIterator() {
299         return listIterator(0);
300     }
301 
302     /**
303      * {@inheritDoc}
304      *
305      * <p>This implementation returns a straightforward implementation of the
306      * {@code ListIterator} interface that extends the implementation of the
307      * {@code Iterator} interface returned by the {@code iterator()} method.
308      * The {@code ListIterator} implementation relies on the backing list's
309      * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
310      * and {@code remove(int)} methods.
311      *
312      * <p>Note that the list iterator returned by this implementation will
313      * throw an {@link UnsupportedOperationException} in response to its
314      * {@code remove}, {@code set} and {@code add} methods unless the
315      * list's {@code remove(int)}, {@code set(int, E)}, and
316      * {@code add(int, E)} methods are overridden.
317      *
318      * <p>This implementation can be made to throw runtime exceptions in the
319      * face of concurrent modification, as described in the specification for
320      * the (protected) {@link #modCount} field.
321      *
322      * @throws IndexOutOfBoundsException {@inheritDoc}
323      */
324     public ListIterator<E> listIterator(final int index) {
325         rangeCheckForAdd(index);
326 
327         return new ListItr(index);
328     }
329 
330     private class Itr implements Iterator<E> {
331         /**
332          * Index of element to be returned by subsequent call to next.
333          */
334         int cursor = 0;
335 
336         /**
337          * Index of element returned by most recent call to next or
338          * previous.  Reset to -1 if this element is deleted by a call
339          * to remove.
340          */
341         int lastRet = -1;
342 
343         /**
344          * The modCount value that the iterator believes that the backing
345          * List should have.  If this expectation is violated, the iterator
346          * has detected concurrent modification.
347          */
348         int expectedModCount = modCount;
349 
350         public boolean hasNext() {
351             return cursor != size();
352         }
353 
354         public E next() {
355             checkForComodification();
356             try {
357                 int i = cursor;
358                 E next = get(i);
359                 lastRet = i;
360                 cursor = i + 1;
361                 return next;
362             } catch (IndexOutOfBoundsException e) {
363                 checkForComodification();
364                 throw new NoSuchElementException();
365             }
366         }
367 
368         public void remove() {
369             if (lastRet < 0)
370                 throw new IllegalStateException();
371             checkForComodification();
372 
373             try {
374                 AbstractList.this.remove(lastRet);
375                 if (lastRet < cursor)
376                     cursor--;
377                 lastRet = -1;
378                 expectedModCount = modCount;
379             } catch (IndexOutOfBoundsException e) {
380                 throw new ConcurrentModificationException();
381             }
382         }
383 
384         final void checkForComodification() {
385             if (modCount != expectedModCount)
386                 throw new ConcurrentModificationException();
387         }
388     }
389 
390     private class ListItr extends Itr implements ListIterator<E> {
391         ListItr(int index) {
392             cursor = index;
393         }
394 
395         public boolean hasPrevious() {
396             return cursor != 0;
397         }
398 
399         public E previous() {
400             checkForComodification();
401             try {
402                 int i = cursor - 1;
403                 E previous = get(i);
404                 lastRet = cursor = i;
405                 return previous;
406             } catch (IndexOutOfBoundsException e) {
407                 checkForComodification();
408                 throw new NoSuchElementException();
409             }
410         }
411 
412         public int nextIndex() {
413             return cursor;
414         }
415 
416         public int previousIndex() {
417             return cursor-1;
418         }
419 
420         public void set(E e) {
421             if (lastRet < 0)
422                 throw new IllegalStateException();
423             checkForComodification();
424 
425             try {
426                 AbstractList.this.set(lastRet, e);
427                 expectedModCount = modCount;
428             } catch (IndexOutOfBoundsException ex) {
429                 throw new ConcurrentModificationException();
430             }
431         }
432 
433         public void add(E e) {
434             checkForComodification();
435 
436             try {
437                 int i = cursor;
438                 AbstractList.this.add(i, e);
439                 lastRet = -1;
440                 cursor = i + 1;
441                 expectedModCount = modCount;
442             } catch (IndexOutOfBoundsException ex) {
443                 throw new ConcurrentModificationException();
444             }
445         }
446     }
447 
448     /**
449      * {@inheritDoc}
450      *
451      * <p>This implementation returns a list that subclasses
452      * {@code AbstractList}.  The subclass stores, in private fields, the
453      * offset of the subList within the backing list, the size of the subList
454      * (which can change over its lifetime), and the expected
455      * {@code modCount} value of the backing list.  There are two variants
456      * of the subclass, one of which implements {@code RandomAccess}.
457      * If this list implements {@code RandomAccess} the returned list will
458      * be an instance of the subclass that implements {@code RandomAccess}.
459      *
460      * <p>The subclass's {@code set(int, E)}, {@code get(int)},
461      * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
462      * Collection)} and {@code removeRange(int, int)} methods all
463      * delegate to the corresponding methods on the backing abstract list,
464      * after bounds-checking the index and adjusting for the offset.  The
465      * {@code addAll(Collection c)} method merely returns {@code addAll(size,
466      * c)}.
467      *
468      * <p>The {@code listIterator(int)} method returns a "wrapper object"
469      * over a list iterator on the backing list, which is created with the
470      * corresponding method on the backing list.  The {@code iterator} method
471      * merely returns {@code listIterator()}, and the {@code size} method
472      * merely returns the subclass's {@code size} field.
473      *
474      * <p>All methods first check to see if the actual {@code modCount} of
475      * the backing list is equal to its expected value, and throw a
476      * {@code ConcurrentModificationException} if it is not.
477      *
478      * @throws IndexOutOfBoundsException if an endpoint index value is out of range
479      *         {@code (fromIndex < 0 || toIndex > size)}
480      * @throws IllegalArgumentException if the endpoint indices are out of order
481      *         {@code (fromIndex > toIndex)}
482      */
483     public List<E> subList(int fromIndex, int toIndex) {
484         return (this instanceof RandomAccess ?
485                 new RandomAccessSubList<>(this, fromIndex, toIndex) :
486                 new SubList<>(this, fromIndex, toIndex));
487     }
488 
489     // Comparison and hashing
490 
491     /**
492      * Compares the specified object with this list for equality.  Returns
493      * {@code true} if and only if the specified object is also a list, both
494      * lists have the same size, and all corresponding pairs of elements in
495      * the two lists are <i>equal</i>.  (Two elements {@code e1} and
496      * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
497      * e1.equals(e2))}.)  In other words, two lists are defined to be
498      * equal if they contain the same elements in the same order.<p>
499      *
500      * This implementation first checks if the specified object is this
501      * list. If so, it returns {@code true}; if not, it checks if the
502      * specified object is a list. If not, it returns {@code false}; if so,
503      * it iterates over both lists, comparing corresponding pairs of elements.
504      * If any comparison returns {@code false}, this method returns
505      * {@code false}.  If either iterator runs out of elements before the
506      * other it returns {@code false} (as the lists are of unequal length);
507      * otherwise it returns {@code true} when the iterations complete.
508      *
509      * @param o the object to be compared for equality with this list
510      * @return {@code true} if the specified object is equal to this list
511      */
512     public boolean equals(Object o) {
513         if (o == this)
514             return true;
515         if (!(o instanceof List))
516             return false;
517 
518         ListIterator<E> e1 = listIterator();
519         ListIterator e2 = ((List) o).listIterator();
520         while (e1.hasNext() && e2.hasNext()) {
521             E o1 = e1.next();
522             Object o2 = e2.next();
523             if (!(o1==null ? o2==null : o1.equals(o2)))
524                 return false;
525         }
526         return !(e1.hasNext() || e2.hasNext());
527     }
528 
529     /**
530      * Returns the hash code value for this list.
531      *
532      * <p>This implementation uses exactly the code that is used to define the
533      * list hash function in the documentation for the {@link List#hashCode}
534      * method.
535      *
536      * @return the hash code value for this list
537      */
538     public int hashCode() {
539         int hashCode = 1;
540         for (E e : this)
541             hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
542         return hashCode;
543     }
544 
545     /**
546      * Removes from this list all of the elements whose index is between
547      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
548      * Shifts any succeeding elements to the left (reduces their index).
549      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
550      * (If {@code toIndex==fromIndex}, this operation has no effect.)
551      *
552      * <p>This method is called by the {@code clear} operation on this list
553      * and its subLists.  Overriding this method to take advantage of
554      * the internals of the list implementation can <i>substantially</i>
555      * improve the performance of the {@code clear} operation on this list
556      * and its subLists.
557      *
558      * <p>This implementation gets a list iterator positioned before
559      * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
560      * followed by {@code ListIterator.remove} until the entire range has
561      * been removed.  <b>Note: if {@code ListIterator.remove} requires linear
562      * time, this implementation requires quadratic time.</b>
563      *
564      * @param fromIndex index of first element to be removed
565      * @param toIndex index after last element to be removed
566      */
567     protected void removeRange(int fromIndex, int toIndex) {
568         ListIterator<E> it = listIterator(fromIndex);
569         for (int i=0, n=toIndex-fromIndex; i<n; i++) {
570             it.next();
571             it.remove();
572         }
573     }
574 
575     /**
576      * The number of times this list has been <i>structurally modified</i>.
577      * Structural modifications are those that change the size of the
578      * list, or otherwise perturb it in such a fashion that iterations in
579      * progress may yield incorrect results.
580      *
581      * <p>This field is used by the iterator and list iterator implementation
582      * returned by the {@code iterator} and {@code listIterator} methods.
583      * If the value of this field changes unexpectedly, the iterator (or list
584      * iterator) will throw a {@code ConcurrentModificationException} in
585      * response to the {@code next}, {@code remove}, {@code previous},
586      * {@code set} or {@code add} operations.  This provides
587      * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
588      * the face of concurrent modification during iteration.
589      *
590      * <p><b>Use of this field by subclasses is optional.</b> If a subclass
591      * wishes to provide fail-fast iterators (and list iterators), then it
592      * merely has to increment this field in its {@code add(int, E)} and
593      * {@code remove(int)} methods (and any other methods that it overrides
594      * that result in structural modifications to the list).  A single call to
595      * {@code add(int, E)} or {@code remove(int)} must add no more than
596      * one to this field, or the iterators (and list iterators) will throw
597      * bogus {@code ConcurrentModificationExceptions}.  If an implementation
598      * does not wish to provide fail-fast iterators, this field may be
599      * ignored.
600      */
601     protected transient int modCount = 0;
602 
603     private void rangeCheckForAdd(int index) {
604         if (index < 0 || index > size())
605             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
606     }
607 
608     private String outOfBoundsMsg(int index) {
609         return "Index: "+index+", Size: "+size();
610     }
611 }
612 
613 class SubList<E> extends AbstractList<E> {
614     private final AbstractList<E> l;
615     private final int offset;
616     private int size;
617 
618     SubList(AbstractList<E> list, int fromIndex, int toIndex) {
619         if (fromIndex < 0)
620             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
621         if (toIndex > list.size())
622             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
623         if (fromIndex > toIndex)
624             throw new IllegalArgumentException("fromIndex(" + fromIndex +
625                                                ") > toIndex(" + toIndex + ")");
626         l = list;
627         offset = fromIndex;
628         size = toIndex - fromIndex;
629         this.modCount = l.modCount;
630     }
631 
632     public E set(int index, E element) {
633         rangeCheck(index);
634         checkForComodification();
635         return l.set(index+offset, element);
636     }
637 
638     public E get(int index) {
639         rangeCheck(index);
640         checkForComodification();
641         return l.get(index+offset);
642     }
643 
644     public int size() {
645         checkForComodification();
646         return size;
647     }
648 
649     public void add(int index, E element) {
650         rangeCheckForAdd(index);
651         checkForComodification();
652         l.add(index+offset, element);
653         this.modCount = l.modCount;
654         size++;
655     }
656 
657     public E remove(int index) {
658         rangeCheck(index);
659         checkForComodification();
660         E result = l.remove(index+offset);
661         this.modCount = l.modCount;
662         size--;
663         return result;
664     }
665 
666     protected void removeRange(int fromIndex, int toIndex) {
667         checkForComodification();
668         l.removeRange(fromIndex+offset, toIndex+offset);
669         this.modCount = l.modCount;
670         size -= (toIndex-fromIndex);
671     }
672 
673     public boolean addAll(Collection<? extends E> c) {
674         return addAll(size, c);
675     }
676 
677     public boolean addAll(int index, Collection<? extends E> c) {
678         rangeCheckForAdd(index);
679         int cSize = c.size();
680         if (cSize==0)
681             return false;
682 
683         checkForComodification();
684         l.addAll(offset+index, c);
685         this.modCount = l.modCount;
686         size += cSize;
687         return true;
688     }
689 
690     public Iterator<E> iterator() {
691         return listIterator();
692     }
693 
694     public ListIterator<E> listIterator(final int index) {
695         checkForComodification();
696         rangeCheckForAdd(index);
697 
698         return new ListIterator<E>() {
699             private final ListIterator<E> i = l.listIterator(index+offset);
700 
701             public boolean hasNext() {
702                 return nextIndex() < size;
703             }
704 
705             public E next() {
706                 if (hasNext())
707                     return i.next();
708                 else
709                     throw new NoSuchElementException();
710             }
711 
712             public boolean hasPrevious() {
713                 return previousIndex() >= 0;
714             }
715 
716             public E previous() {
717                 if (hasPrevious())
718                     return i.previous();
719                 else
720                     throw new NoSuchElementException();
721             }
722 
723             public int nextIndex() {
724                 return i.nextIndex() - offset;
725             }
726 
727             public int previousIndex() {
728                 return i.previousIndex() - offset;
729             }
730 
731             public void remove() {
732                 i.remove();
733                 SubList.this.modCount = l.modCount;
734                 size--;
735             }
736 
737             public void set(E e) {
738                 i.set(e);
739             }
740 
741             public void add(E e) {
742                 i.add(e);
743                 SubList.this.modCount = l.modCount;
744                 size++;
745             }
746         };
747     }
748 
749     public List<E> subList(int fromIndex, int toIndex) {
750         return new SubList<>(this, fromIndex, toIndex);
751     }
752 
753     private void rangeCheck(int index) {
754         if (index < 0 || index >= size)
755             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
756     }
757 
758     private void rangeCheckForAdd(int index) {
759         if (index < 0 || index > size)
760             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
761     }
762 
763     private String outOfBoundsMsg(int index) {
764         return "Index: "+index+", Size: "+size;
765     }
766 
767     private void checkForComodification() {
768         if (this.modCount != l.modCount)
769             throw new ConcurrentModificationException();
770     }
771 }
772 
773 class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
774     RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
775         super(list, fromIndex, toIndex);
776     }
777 
778     public List<E> subList(int fromIndex, int toIndex) {
779         return new RandomAccessSubList<>(this, fromIndex, toIndex);
780     }
781 }

View Code

AbstractList 实现了List<E>接口，但是他的子类如ArrayList 、Vector 也实现了List<E>，是因为equals(Object o) hashCode()等公用方法的具体实现

此类提供 List 接口的骨干实现，从而最大限度地减少了实现由“随机访问”数据存储（如数组）支持的接口所需的工作。对于连续的访问数据（如链表），应优先使用AbstractSequentialList，如LinkedList则继承自AbstractSequentialList而非此类。

还有个较奇怪的点，

public void add(int index, E element), public E remove(int index) ,public E set(int index, E element)

三个方法均抛出UnsupportedOperationException异常。为什么呢？

因为这三个不是公用方法了，必须由具体继承该抽象类的子类去覆写这三个方法！

接下来比较下三个最常用的实现类ArrayList、Vector、LinkedList异同

1.ArrayList是基于数组格式存储，寻址空间是连续的。而LinkedList是基于链表结构存储数据，物理空间是不连续的。当进行查找或定位某一元素时，LinkedList需要移动其结点指针，ArrayList的速率要比LinkedList更快。

进行删除、插入操作时，若是链表结构，只需打开其结点，重新指向下一结点即可完成操作，而数组的插入，需保证其寻址空间的连续性，故需将其插入位置后的元素进行移动。所以进行插入、删除操作时，LinkedList的速率要比ArrayList快。

2.LinkedList 还实现了 Queue 接口,该接口比List提供了更多的方法,包括 offer(),peek(),poll()等.
注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。

3.Vector与ArrayList都是基于数组来实现的，不同的是它实现了线程同步，即同一时刻，只允许一个线程对集合进行读写，但是实现同步需要很高的开销，因此它的访问速率比ArrayList慢。

4.Stack为继承自Vector的后进先出的堆栈模型。

Stack(类)

Stack 为堆栈模型，遵循后进先出（Last in First Out）。主要方法:

E push(E item)

把项压入堆栈顶部。

E pop()

移除堆栈顶部的对象，并作为此函数的值返回该对象。

E peek()

查看堆栈顶部的对象，但不从堆栈中移除它。

boolean empty()

测试堆栈是否为空。

int search(Object o)

返回对象在堆栈中的位置，以 1 为基数。

其中数组的最后一位元素即为栈顶元素，search方法返回的是离栈顶最近的item与栈顶之间的距离！

源码如下：

  1 /*
  2  * Copyright (c) 1994, 2010, Oracle and/or its affiliates. All rights reserved.
  3  * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  4  *
  5  *
  6  *
  7  *
  8  *
  9  *
 10  *
 11  *
 12  *
 13  *
 14  *
 15  *
 16  *
 17  *
 18  *
 19  *
 20  *
 21  *
 22  *
 23  *
 24  */
 25 
 26 package java.util;
 27 
 28 /**
 29  * The <code>Stack</code> class represents a last-in-first-out
 30  * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 31  * operations that allow a vector to be treated as a stack. The usual
 32  * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 33  * method to <tt>peek</tt> at the top item on the stack, a method to test
 34  * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 35  * the stack for an item and discover how far it is from the top.
 36  * <p>
 37  * When a stack is first created, it contains no items.
 38  *
 39  * <p>A more complete and consistent set of LIFO stack operations is
 40  * provided by the {@link Deque} interface and its implementations, which
 41  * should be used in preference to this class.  For example:
 42  * <pre>   {@code
 43  *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 44  *
 45  * @author  Jonathan Payne
 46  * @since   JDK1.0
 47  */
 48 public
 49 class Stack<E> extends Vector<E> {
 50     /**
 51      * Creates an empty Stack.
 52      */
 53     public Stack() {
 54     }
 55 
 56     /**
 57      * Pushes an item onto the top of this stack. This has exactly
 58      * the same effect as:
 59      * <blockquote><pre>
 60      * addElement(item)</pre></blockquote>
 61      *
 62      * @param   item   the item to be pushed onto this stack.
 63      * @return  the <code>item</code> argument.
 64      * @see     java.util.Vector#addElement
 65      */
 66     public E push(E item) {
 67         addElement(item);
 68 
 69         return item;
 70     }
 71 
 72     /**
 73      * Removes the object at the top of this stack and returns that
 74      * object as the value of this function.
 75      *
 76      * @return  The object at the top of this stack (the last item
 77      *          of the <tt>Vector</tt> object).
 78      * @throws  EmptyStackException  if this stack is empty.
 79      */
 80     public synchronized E pop() {
 81         E       obj;
 82         int     len = size();
 83 
 84         obj = peek();
 85         removeElementAt(len - 1);
 86 
 87         return obj;
 88     }
 89 
 90     /**
 91      * Looks at the object at the top of this stack without removing it
 92      * from the stack.
 93      *
 94      * @return  the object at the top of this stack (the last item
 95      *          of the <tt>Vector</tt> object).
 96      * @throws  EmptyStackException  if this stack is empty.
 97      */
 98     public synchronized E peek() {
 99         int     len = size();
100 
101         if (len == 0)
102             throw new EmptyStackException();
103         return elementAt(len - 1);
104     }
105 
106     /**
107      * Tests if this stack is empty.
108      *
109      * @return  <code>true</code> if and only if this stack contains
110      *          no items; <code>false</code> otherwise.
111      */
112     public boolean empty() {
113         return size() == 0;
114     }
115 
116     /**
117      * Returns the 1-based position where an object is on this stack.
118      * If the object <tt>o</tt> occurs as an item in this stack, this
119      * method returns the distance from the top of the stack of the
120      * occurrence nearest the top of the stack; the topmost item on the
121      * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
122      * method is used to compare <tt>o</tt> to the
123      * items in this stack.
124      *
125      * @param   o   the desired object.
126      * @return  the 1-based position from the top of the stack where
127      *          the object is located; the return value <code>-1</code>
128      *          indicates that the object is not on the stack.
129      */
130     public synchronized int search(Object o) {
131         int i = lastIndexOf(o);
132 
133         if (i >= 0) {
134             return size() - i;
135         }
136         return -1;
137     }
138 
139     /** use serialVersionUID from JDK 1.0.2 for interoperability */
140     private static final long serialVersionUID = 1224463164541339165L;
141 }

View Code

我们可以看到push(E item)实际上是调用父类Vector的addElement方法，empty()调用的是父类的Size（）方法。

因为水平有限，可能不足和不够严谨之处，欢迎批评雅正~~

爱程序网

Tags：[db:关键字]