转载请注明原文地址：

   Java中常用的List子类主要有：ArrayList、LinkedList、Vector。

   一：ArrayList

   ArrayList实现了List接口，实现了一系列的add()/get()/clear()/remove()等接口中的方法。其底层其实是一个数组，通过对数组上一系列操作的封装来实现list的各种功能的。

package java.util;public class ArrayList
     
       extends AbstractList
      
               implements List
       
        , RandomAccess, Cloneable, java.io.Serializable{    // 序列版本号    private static final long serialVersionUID = 8683452581122892189L;    // 保存ArrayList中数据的数组    private transient Object[] elementData;    // ArrayList中实际数据的数量    private int size;    // ArrayList带容量大小的构造函数。    public ArrayList(int initialCapacity) {        super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);        // 新建一个数组        this.elementData = new Object[initialCapacity];    }    // ArrayList构造函数。默认容量是10。    public ArrayList() {        this(10);    }    // 创建一个包含collection的ArrayList    public ArrayList(Collection
         c) {        elementData = c.toArray();        size = elementData.length;        // c.toArray might (incorrectly) not return Object[] (see 6260652)        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, size, Object[].class);    }    // 将当前容量值设为 =实际元素个数    public void trimToSize() {        modCount++;        int oldCapacity = elementData.length;        if (size < oldCapacity) {            elementData = Arrays.copyOf(elementData, size);        }    }    // 确定ArrarList的容量。    // 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”    public void ensureCapacity(int minCapacity) {        // 将“修改统计数”+1        modCount++;        int oldCapacity = elementData.length;        // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”        if (minCapacity > oldCapacity) {            Object oldData[] = elementData;            int newCapacity = (oldCapacity * 3)/2 + 1;            if (newCapacity < minCapacity)                newCapacity = minCapacity;            elementData = Arrays.copyOf(elementData, newCapacity);        }    }    // 添加元素e    public boolean add(E e) {        // 确定ArrayList的容量大小        ensureCapacity(size + 1);  // Increments modCount!!        // 添加e到ArrayList中        elementData[size++] = e;        return true;    }    // 返回ArrayList的实际大小    public int size() {        return size;    }    // 返回ArrayList是否包含Object(o)    public boolean contains(Object o) {        return indexOf(o) >= 0;    }    // 返回ArrayList是否为空    public boolean isEmpty() {        return size == 0;    }    // 正向查找，返回元素的索引值    public int indexOf(Object o) {        if (o == null) {            for (int i = 0; i < size; i++)            if (elementData[i]==null)                return i;            } else {                for (int i = 0; i < size; i++)                if (o.equals(elementData[i]))                    return i;            }            return -1;        }        // 反向查找，返回元素的索引值        public int lastIndexOf(Object o) {        if (o == null) {            for (int i = size-1; i >= 0; i--)            if (elementData[i]==null)                return i;        } else {            for (int i = size-1; i >= 0; i--)            if (o.equals(elementData[i]))                return i;        }        return -1;    }    // 反向查找(从数组末尾向开始查找)，返回元素(o)的索引值    public int lastIndexOf(Object o) {        if (o == null) {            for (int i = size-1; i >= 0; i--)            if (elementData[i]==null)                return i;        } else {            for (int i = size-1; i >= 0; i--)            if (o.equals(elementData[i]))                return i;        }        return -1;    }     // 返回ArrayList的Object数组    public Object[] toArray() {        return Arrays.copyOf(elementData, size);    }    // 返回ArrayList的模板数组。所谓模板数组，即可以将T设为任意的数据类型    public 
        
          T[] toArray(T[] a) {        // 若数组a的大小 < ArrayList的元素个数；        // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中        if (a.length < size)            return (T[]) Arrays.copyOf(elementData, size, a.getClass());        // 若数组a的大小 >= ArrayList的元素个数；        // 则将ArrayList的全部元素都拷贝到数组a中。        System.arraycopy(elementData, 0, a, 0, size);        if (a.length > size)            a[size] = null;        return a;    }    // 获取index位置的元素值    public E get(int index) {        RangeCheck(index);        return (E) elementData[index];    }    // 设置index位置的值为element    public E set(int index, E element) {        RangeCheck(index);        E oldValue = (E) elementData[index];        elementData[index] = element;        return oldValue;    }    // 将e添加到ArrayList中    public boolean add(E e) {        ensureCapacity(size + 1);  // Increments modCount!!        elementData[size++] = e;        return true;    }    // 将e添加到ArrayList的指定位置    public void add(int index, E element) {        if (index > size || index < 0)            throw new IndexOutOfBoundsException(            "Index: "+index+", Size: "+size);        ensureCapacity(size+1);  // Increments modCount!!        System.arraycopy(elementData, index, elementData, index + 1,             size - index);        elementData[index] = element;        size++;    }    // 删除ArrayList指定位置的元素    public E remove(int index) {        RangeCheck(index);        modCount++;        E oldValue = (E) elementData[index];        int numMoved = size - index - 1;        if (numMoved > 0)            System.arraycopy(elementData, index+1, elementData, index,                 numMoved);        elementData[--size] = null; // Let gc do its work        return oldValue;    }    // 删除ArrayList的指定元素    public boolean remove(Object o) {        if (o == null) {                for (int index = 0; index < size; index++)            if (elementData[index] == null) {                fastRemove(index);                return true;            }        } else {            for (int index = 0; index < size; index++)            if (o.equals(elementData[index])) {                fastRemove(index);                return true;            }        }        return false;    }    // 快速删除第index个元素    private void fastRemove(int index) {        modCount++;        int numMoved = size - index - 1;        // 从"index+1"开始，用后面的元素替换前面的元素。        if (numMoved > 0)            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);        // 将最后一个元素设为null        elementData[--size] = null; // Let gc do its work    }    // 删除元素    public boolean remove(Object o) {        if (o == null) {            for (int index = 0; index < size; index++)            if (elementData[index] == null) {                fastRemove(index);            return true;            }        } else {            // 便利ArrayList，找到“元素o”，则删除，并返回true。            for (int index = 0; index < size; index++)            if (o.equals(elementData[index])) {                fastRemove(index);            return true;            }        }        return false;    }    // 清空ArrayList，将全部的元素设为null    public void clear() {        modCount++;        for (int i = 0; i < size; i++)            elementData[i] = null;        size = 0;    }    // 将集合c追加到ArrayList中    public boolean addAll(Collection
          c) {        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacity(size + numNew);  // Increments modCount        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;        return numNew != 0;    }    // 从index位置开始，将集合c添加到ArrayList    public boolean addAll(int index, Collection
          c) {        if (index > size || index < 0)            throw new IndexOutOfBoundsException(            "Index: " + index + ", Size: " + size);        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacity(size + numNew);  // Increments modCount        int numMoved = size - index;        if (numMoved > 0)            System.arraycopy(elementData, index, elementData, index + numNew,                 numMoved);        System.arraycopy(a, 0, elementData, index, numNew);        size += numNew;        return numNew != 0;    }    // 删除fromIndex到toIndex之间的全部元素。    protected void removeRange(int fromIndex, int toIndex) {    modCount++;    int numMoved = size - toIndex;        System.arraycopy(elementData, toIndex, elementData, fromIndex,                         numMoved);    // Let gc do its work    int newSize = size - (toIndex-fromIndex);    while (size != newSize)        elementData[--size] = null;    }    private void RangeCheck(int index) {    if (index >= size)        throw new IndexOutOfBoundsException(        "Index: "+index+", Size: "+size);    }    // 克隆函数    public Object clone() {        try {            ArrayList
         
           v = (ArrayList
          
           ) super.clone(); // 将当前ArrayList的全部元素拷贝到v中 v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(); } } // java.io.Serializable的写入函数 // 将ArrayList的“容量，所有的元素值”都写入到输出流中 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // 写入“数组的容量” s.writeInt(elementData.length); // 写入“数组的每一个元素” for (int i=0; i
          
         
        
       
      
     

       1：ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。

      2：当ArrayList容量不足以容纳全部元素时，ArrayList扩容：新的容量=“(原始容量x3)/2 + 1”。创建新容量大小的数组并把原数组内容复制过去。

      3：ArrayList的add()/get()/remove()等操作都是对底层的数组进行操作而已。

 

   二：LinkedList

    LinkedList通过另一种方式实现List接口，不仅如此，它还实现了 Queue、Deque接口，使得LinkedList可以作为 栈、队列、双端队列来使用。

    LinkedList底层是一个 双向链表。其对于 List、Queue、Deque接口中的方法都是通过封装在链表上的操作来实现的。  

package com.chy.collection.core;            import java.util.AbstractSequentialList;      import java.util.Collections;      import java.util.ConcurrentModificationException;      import java.util.Deque;      import java.util.Iterator;      import java.util.NoSuchElementException;      import java.util.Queue;      import java.util.Vector;            /**      * LinkedList实际上是通过双向链表去实现的、整个链表是通过Entry实体类来存储数据的      */            public class LinkedList
     
                extends AbstractSequentialList
      
                 implements List
       
        , Deque
        
         , Cloneable, java.io.Serializable      {          //链表的表头、表头不包含任何数据、          //Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。          private transient Entry
         
           header = new Entry
          
           (null, null, null); // LinkedList中元素个数 private transient int size = 0; /** * 构造一个空的LinkedList、只含有表头 */ public LinkedList() { header.next = header.previous = header; } /** * 创建一个包含c的LinkedList、先创建默认空、然后将c中所有元素添加到LinkedList中 */ public LinkedList(Collection
            c) { this(); addAll(c); } /** 获取链表第一个元素、*/ public E getFirst() { if (size==0) throw new NoSuchElementException(); //因其是双向链表、这里的header可视为顺序的第一个不含元素的表头、所以第一个是此header的下一个元素 return header.next.element; } /** 获取链表最后一个元素*/ public E getLast() { if (size==0) throw new NoSuchElementException(); //因其是双向链表、这里的header可视为逆序的第一个不含元素的表头、所以最后一个是此header的上一个元素 return header.previous.element; } /** 删除LinkedList的第一个元素*/ public E removeFirst() { return remove(header.next); } /** 删除LinkedList的最后一个元素*/ public E removeLast() { return remove(header.previous); } /** 将元素e添加到LinkedList的起始位置*/ public void addFirst(E e) { addBefore(e, header.next); } /** 将元素e添加到LinkedList的结束位置*/ public void addLast(E e) { addBefore(e, header); } /** 判断是否包含Object o*/ public boolean contains(Object o) { return indexOf(o) != -1; } /** 返回LinkedList的大小*/ public int size() { return size; } /** 将元素(E)添加到LinkedList中、添加到末尾*/ public boolean add(E e) { addBefore(e, header); return true; } /** 从LinkedList中删除o、如果存在则删除第一查找到的o并返回true、若不存在则返回false*/ public boolean remove(Object o) { if (o==null) { for (Entry
           
             e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry
            
              e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } /** 将c中元素添加到双向链表LinkedList中、从尾部开始添加*/ public boolean addAll(Collection
              c) { return addAll(size, c); } /** 将c中元素添加到双向链表LinkedList中、所有元素添加到index与index+1表示的元素中间*/ public boolean addAll(int index, Collection
              c) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); //将c转换成数组、方便遍历元素和获取元素个数 Object[] a = c.toArray(); int numNew = a.length; if (numNew==0) return false; modCount++; //设置当前要插入节点的下一个节点 Entry
             
               successor = (index==size ? header : entry(index)); //设置当前要插入节点的上一个节点 Entry
              
                predecessor = successor.previous; //将c中元素插入到LinkedList中 for (int i=0; i
               
                 e = new Entry
                
                 ((E)a[i], successor, predecessor); predecessor.next = e; predecessor = e; } successor.previous = predecessor; size += numNew; return true; } /** 删除LinkedList中所有元素*/ public void clear() { Entry
                 
                   e = header.next; while (e != header) { Entry
                  
                    next = e.next; e.next = e.previous = null; e.element = null; e = next; } header.next = header.previous = header; size = 0; modCount++; } // Positional Access Operations /** 获取index处的元素*/ public E get(int index) { return entry(index).element; } /** 设置index处的元素、并将old元素返回*/ public E set(int index, E element) { Entry
                   
                     e = entry(index); E oldVal = e.element; e.element = element; return oldVal; } /** 在index前添加节点，且节点的值为element*/ public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } /** 删除index位置的节点*/ public E remove(int index) { return remove(entry(index)); } /** 获取双向链表LinkedList中指定位置的节点、是LinkedList实现List中通过index操作元素的关键*/ private Entry
                    
                      entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry
                     
                       e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; } // Search Operations /** 查询o所在LinkedList中的位置的索引、从前向后、不存在返回-1*/ public int indexOf(Object o) { int index = 0; if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) return index; index++; } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1; } /** 查询o所在LinkedList中的位置的索引、从后向前、不存在返回-1*/ public int lastIndexOf(Object o) { int index = size; if (o==null) { for (Entry e = header.previous; e != header; e = e.previous) { index--; if (e.element==null) return index; } } else { for (Entry e = header.previous; e != header; e = e.previous) { index--; if (o.equals(e.element)) return index; } } return -1; } // Queue operations. /** 返回第一个节点、若size为0则返回null*/ public E peek() { if (size==0) return null; return getFirst(); } /** 返回第一个节点、若size为0则抛异常NoSuchElementException*/ public E element() { return getFirst(); } /** 删除并返回第一个节点 、若LinkedList的大小为0,则返回null*/ public E poll() { if (size==0) return null; return removeFirst(); } /** 删除第一个元素、若LinkedList的大小为0,则抛异常*/ public E remove() { return removeFirst(); } /** 将e添加双向链表末尾*/ public boolean offer(E e) { return add(e); } // Deque operations /** 将e添加双向链表开头*/ public boolean offerFirst(E e) { addFirst(e); return true; } /** 将e添加双向链表末尾*/ public boolean offerLast(E e) { addLast(e); return true; } /**返回第一个节点、若LinkedList的大小为0,则返回null*/ public E peekFirst() { if (size==0) return null; return getFirst(); } /**返回最后一个节点、 若LinkedList的大小为0,则返回null*/ public E peekLast() { if (size==0) return null; return getLast(); } /** 删除并返回第一个、若LinkedList的大小为0,则返回null*/ public E pollFirst() { if (size==0) return null; return removeFirst(); } /** 删除并返回最后一个、若LinkedList的大小为0,则返回null*/ public E pollLast() { if (size==0) return null; return removeLast(); } /** 将e插入到双向链表开头*/ public void push(E e) { addFirst(e); } /** 删除并返回第一个节点*/ public E pop() { return removeFirst(); } /** 从LinkedList中删除o、如果存在则删除第一查找到的o并返回true、若不存在则返回false*/ public boolean removeFirstOccurrence(Object o) { return remove(o); } /** 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点*/ public boolean removeLastOccurrence(Object o) { if (o==null) { for (Entry
                      
                        e = header.previous; e != header; e = e.previous) { if (e.element==null) { remove(e); return true; } } } else { for (Entry
                       
                         e = header.previous; e != header; e = e.previous) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } /** 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)*/ public ListIterator
                        
                          listIterator(int index) { return new ListItr(index); } private class ListItr implements ListIterator
                         
                           { // 上一次返回的节点 private Entry
                          
                            lastReturned = header; // 下一个节点 private Entry
                           
                             next; // 下一个节点对应的索引值 private int nextIndex; // 期望的改变计数。用来实现fail-fast机制。 private int expectedModCount = modCount; //构造函数、 从index位置开始进行迭代 ListItr(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); /* * 若 “index 小于 ‘双向链表长度的一半’”，则从第一个元素开始往后查找； * 否则，从最后一个元素往前查找。 */ if (index < (size >> 1)) { next = header.next; for (nextIndex=0; nextIndex
                            
                             index; nextIndex--) next = next.previous; } } // 是否存在下一个元素 public boolean hasNext() { return nextIndex != size; } // 获取下一个元素 public E next() { checkForComodification(); if (nextIndex == size) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.element; } // 是否存在上一个元素 public boolean hasPrevious() { return nextIndex != 0; } // 获取上一个元素 public E previous() { if (nextIndex == 0) throw new NoSuchElementException(); lastReturned = next = next.previous; nextIndex--; checkForComodification(); return lastReturned.element; } // 获取下一个元素的索引 public int nextIndex() { return nextIndex; } // 获取上一个元素的索引 public int previousIndex() { return nextIndex-1; } // 删除双向链表中的当前节点 public void remove() { checkForComodification(); Entry
                             
                               lastNext = lastReturned.next; try { LinkedList.this.remove(lastReturned); } catch (NoSuchElementException e) { throw new IllegalStateException(); } if (next==lastReturned) next = lastNext; else nextIndex--; lastReturned = header; expectedModCount++; } // 设置当前节点为e public void set(E e) { if (lastReturned == header) throw new IllegalStateException(); checkForComodification(); lastReturned.element = e; } // 将e添加到当前节点的前面 public void add(E e) { checkForComodification(); lastReturned = header; addBefore(e, next); nextIndex++; expectedModCount++; } // 判断 “modCount和expectedModCount是否相等”，以此来实现fail-fast机制。 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } /** * 内部静态类、是双向链表的节点所对应的数据结构、 * 此数据结构包含三部分：上一节点、下一节点、当前节点值 */ private static class Entry
                              
                                { //当前节点值 E element; //下一节点 Entry
                               
                                 next; //上一节点 Entry
                                
                                  previous; /** * 链表节点构造函数 * @param element 节点值 * @param next 下一节点 * @param previous 上一节点 */ Entry(E element, Entry
                                 
                                   next, Entry
                                  
                                    previous) { this.element = element; this.next = next; this.previous = previous; } } //新建节点、节点值是e、将新建的节点添加到entry之前 private Entry
                                   
                                     addBefore(E e, Entry
                                    
                                      entry) { //觉得难理解的可以先花个几分钟看一下链式结构资料、最好是图片形式的 //新建节点实体 Entry
                                     
                                       newEntry = new Entry
                                      
                                       (e, entry, entry.previous); //将参照节点原来的上一个节点（即插在谁前面的）的下一个节点设置成newEntry newEntry.previous.next = newEntry; //将参照节点（即插在谁前面的）的前一个节点设置成newEntry newEntry.next.previous = newEntry; size++; modCount++; return newEntry; } //将节点从链表中删除、返回被删除的节点的内容 private E remove(Entry
                                       
                                         e) { //如果是表头、抛异常 if (e == header) throw new NoSuchElementException(); E result = e.element; //下面实际上就是、将e拿掉、然后将e的上下两个节点连接起来 e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result; } /** * 反向迭代器 * @since 1.6 */ public Iterator
                                        
                                          descendingIterator() { return new DescendingIterator(); } /** 反向迭代器实现类 */ private class DescendingIterator implements Iterator { final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } /** 返回LinkedList的克隆对象*/ public Object clone() { LinkedList
                                         
                                           clone = null; try { clone = (LinkedList
                                          
                                           ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } // Put clone into "virgin" state clone.header = new Entry
                                           
                                            (null, null, null); clone.header.next = clone.header.previous = clone.header; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Entry
                                            
                                              e = header.next; e != header; e = e.next) clone.add(e.element); return clone; } /** 将LinkedList中的所有元素转换成Object[]中*/ public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Entry
                                             
                                               e = header.next; e != header; e = e.next) result[i++] = e.element; return result; } /** 将LinkedList中的所有元素转换成Object[]中、并且完成类型转换*/ public 
                                              
                                                T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Entry
                                               
                                                 e = header.next; e != header; e = e.next) result[i++] = e.element; if (a.length > size) a[size] = null; return a; } private static final long serialVersionUID = 876323262645176354L; /** 将LinkedList的“容量，所有的元素值”都写入到输出流中 * 1、将LinkedList的容量写入进去 * 2、将LinkedList中的所有元素写入进去 */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Entry e = header.next; e != header; e = e.next) s.writeObject(e.element); } /** * 将写入的LinkedList读取出来 * 1、读取写入的LinkedList的容量 * 2、读取写入的元素 */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Initialize header header = new Entry
                                                
                                                 (null, null, null); header.next = header.previous = header; // Read in all elements in the proper order. for (int i=0; i
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

   三：Vector

   Vector也是在底层通过一个数组来保存数据，通过底层数组的一系列操作来实现List接口的。

  

package java.util;public class Vector
     
          extends AbstractList
      
           implements List
       
        , RandomAccess, Cloneable, java.io.Serializable{    // 保存Vector中数据的数组    protected Object[] elementData;    // 实际数据的数量    protected int elementCount;    // 容量增长系数    protected int capacityIncrement;    // Vector的序列版本号    private static final long serialVersionUID = -2767605614048989439L;    // Vector构造函数。默认容量是10。    public Vector() {        this(10);    }    // 指定Vector容量大小的构造函数    public Vector(int initialCapacity) {        this(initialCapacity, 0);    }    // 指定Vector"容量大小"和"增长系数"的构造函数    public Vector(int initialCapacity, int capacityIncrement) {        super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);        // 新建一个数组，数组容量是initialCapacity        this.elementData = new Object[initialCapacity];        // 设置容量增长系数        this.capacityIncrement = capacityIncrement;    }    // 指定集合的Vector构造函数。    public Vector(Collection
         c) {        // 获取“集合(c)”的数组，并将其赋值给elementData        elementData = c.toArray();        // 设置数组长度        elementCount = elementData.length;        // c.toArray might (incorrectly) not return Object[] (see 6260652)        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);    }    // 将数组Vector的全部元素都拷贝到数组anArray中    public synchronized void copyInto(Object[] anArray) {        System.arraycopy(elementData, 0, anArray, 0, elementCount);    }    // 将当前容量值设为 =实际元素个数    public synchronized void trimToSize() {        modCount++;        int oldCapacity = elementData.length;        if (elementCount < oldCapacity) {            elementData = Arrays.copyOf(elementData, elementCount);        }    }    // 确认“Vector容量”的帮助函数    private void ensureCapacityHelper(int minCapacity) {        int oldCapacity = elementData.length;        // 当Vector的容量不足以容纳当前的全部元素，增加容量大小。        // 若 容量增量系数>0(即capacityIncrement>0)，则将容量增大当capacityIncrement        // 否则，将容量增大一倍。        if (minCapacity > oldCapacity) {            Object[] oldData = elementData;            int newCapacity = (capacityIncrement > 0) ?                (oldCapacity + capacityIncrement) : (oldCapacity * 2);            if (newCapacity < minCapacity) {                newCapacity = minCapacity;            }            elementData = Arrays.copyOf(elementData, newCapacity);        }    }    // 确定Vector的容量。    public synchronized void ensureCapacity(int minCapacity) {        // 将Vector的改变统计数+1        modCount++;        ensureCapacityHelper(minCapacity);    }    // 设置容量值为 newSize    public synchronized void setSize(int newSize) {        modCount++;        if (newSize > elementCount) {            // 若 "newSize 大于 Vector容量"，则调整Vector的大小。            ensureCapacityHelper(newSize);        } else {            // 若 "newSize 小于/等于 Vector容量"，则将newSize位置开始的元素都设置为null            for (int i = newSize ; i < elementCount ; i++) {                elementData[i] = null;            }        }        elementCount = newSize;    }    // 返回“Vector的总的容量”    public synchronized int capacity() {        return elementData.length;    }    // 返回“Vector的实际大小”，即Vector中元素个数    public synchronized int size() {        return elementCount;    }    // 判断Vector是否为空    public synchronized boolean isEmpty() {        return elementCount == 0;    }    // 返回“Vector中全部元素对应的Enumeration”    public Enumeration
        
          elements() {        // 通过匿名类实现Enumeration        return new Enumeration
         
          () {            int count = 0;            // 是否存在下一个元素            public boolean hasMoreElements() {                return count < elementCount;            }            // 获取下一个元素            public E nextElement() {                synchronized (Vector.this) {                    if (count < elementCount) {                        return (E)elementData[count++];                    }                }                throw new NoSuchElementException("Vector Enumeration");            }        };    }    // 返回Vector中是否包含对象(o)    public boolean contains(Object o) {        return indexOf(o, 0) >= 0;    }    // 从index位置开始向后查找元素(o)。    // 若找到，则返回元素的索引值；否则，返回-1    public synchronized int indexOf(Object o, int index) {        if (o == null) {            // 若查找元素为null，则正向找出null元素，并返回它对应的序号            for (int i = index ; i < elementCount ; i++)            if (elementData[i]==null)                return i;        } else {            // 若查找元素不为null，则正向找出该元素，并返回它对应的序号            for (int i = index ; i < elementCount ; i++)            if (o.equals(elementData[i]))                return i;        }        return -1;    }    // 查找并返回元素(o)在Vector中的索引值    public int indexOf(Object o) {        return indexOf(o, 0);    }    // 从后向前查找元素(o)。并返回元素的索引    public synchronized int lastIndexOf(Object o) {        return lastIndexOf(o, elementCount-1);    }    // 从后向前查找元素(o)。开始位置是从前向后的第index个数；    // 若找到，则返回元素的“索引值”；否则，返回-1。    public synchronized int lastIndexOf(Object o, int index) {        if (index >= elementCount)            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);        if (o == null) {            // 若查找元素为null，则反向找出null元素，并返回它对应的序号            for (int i = index; i >= 0; i--)            if (elementData[i]==null)                return i;        } else {            // 若查找元素不为null，则反向找出该元素，并返回它对应的序号            for (int i = index; i >= 0; i--)            if (o.equals(elementData[i]))                return i;        }        return -1;    }    // 返回Vector中index位置的元素。    // 若index月结，则抛出异常    public synchronized E elementAt(int index) {        if (index >= elementCount) {            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);        }        return (E)elementData[index];    }    // 获取Vector中的第一个元素。    // 若失败，则抛出异常！    public synchronized E firstElement() {        if (elementCount == 0) {            throw new NoSuchElementException();        }        return (E)elementData[0];    }    // 获取Vector中的最后一个元素。    // 若失败，则抛出异常！    public synchronized E lastElement() {        if (elementCount == 0) {            throw new NoSuchElementException();        }        return (E)elementData[elementCount - 1];    }    // 设置index位置的元素值为obj    public synchronized void setElementAt(E obj, int index) {        if (index >= elementCount) {            throw new ArrayIndexOutOfBoundsException(index + " >= " +                                 elementCount);        }        elementData[index] = obj;    }    // 删除index位置的元素    public synchronized void removeElementAt(int index) {        modCount++;        if (index >= elementCount) {            throw new ArrayIndexOutOfBoundsException(index + " >= " +                                 elementCount);        } else if (index < 0) {            throw new ArrayIndexOutOfBoundsException(index);        }        int j = elementCount - index - 1;        if (j > 0) {            System.arraycopy(elementData, index + 1, elementData, index, j);        }        elementCount--;        elementData[elementCount] = null; /* to let gc do its work */    }    // 在index位置处插入元素(obj)    public synchronized void insertElementAt(E obj, int index) {        modCount++;        if (index > elementCount) {            throw new ArrayIndexOutOfBoundsException(index                                 + " > " + elementCount);        }        ensureCapacityHelper(elementCount + 1);        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);        elementData[index] = obj;        elementCount++;    }    // 将“元素obj”添加到Vector末尾    public synchronized void addElement(E obj) {        modCount++;        ensureCapacityHelper(elementCount + 1);        elementData[elementCount++] = obj;    }    // 在Vector中查找并删除元素obj。    // 成功的话，返回true；否则，返回false。    public synchronized boolean removeElement(Object obj) {        modCount++;        int i = indexOf(obj);        if (i >= 0) {            removeElementAt(i);            return true;        }        return false;    }    // 删除Vector中的全部元素    public synchronized void removeAllElements() {        modCount++;        // 将Vector中的全部元素设为null        for (int i = 0; i < elementCount; i++)            elementData[i] = null;        elementCount = 0;    }    // 克隆函数    public synchronized Object clone() {        try {            Vector
          
            v = (Vector
           
            ) super.clone(); // 将当前Vector的全部元素拷贝到v中 v.elementData = Arrays.copyOf(elementData, elementCount); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(); } } // 返回Object数组 public synchronized Object[] toArray() { return Arrays.copyOf(elementData, elementCount); } // 返回Vector的模板数组。所谓模板数组，即可以将T设为任意的数据类型 public synchronized 
            
              T[] toArray(T[] a) { // 若数组a的大小 < Vector的元素个数； // 则新建一个T[]数组，数组大小是“Vector的元素个数”，并将“Vector”全部拷贝到新数组中 if (a.length < elementCount) return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass()); // 若数组a的大小 >= Vector的元素个数； // 则将Vector的全部元素都拷贝到数组a中。 System.arraycopy(elementData, 0, a, 0, elementCount); if (a.length > elementCount) a[elementCount] = null; return a; } // 获取index位置的元素 public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return (E)elementData[index]; } // 设置index位置的值为element。并返回index位置的原始值 public synchronized E set(int index, E element) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); Object oldValue = elementData[index]; elementData[index] = element; return (E)oldValue; } // 将“元素e”添加到Vector最后。 public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } // 删除Vector中的元素o public boolean remove(Object o) { return removeElement(o); } // 在index位置添加元素element public void add(int index, E element) { insertElementAt(element, index); } // 删除index位置的元素，并返回index位置的原始值 public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); Object oldValue = elementData[index]; int numMoved = elementCount - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--elementCount] = null; // Let gc do its work return (E)oldValue; } // 清空Vector public void clear() { removeAllElements(); } // 返回Vector是否包含集合c public synchronized boolean containsAll(Collection
              c) { return super.containsAll(c); } // 将集合c添加到Vector中 public synchronized boolean addAll(Collection
              c) { modCount++; Object[] a = c.toArray(); int numNew = a.length; ensureCapacityHelper(elementCount + numNew); // 将集合c的全部元素拷贝到数组elementData中 System.arraycopy(a, 0, elementData, elementCount, numNew); elementCount += numNew; return numNew != 0; } // 删除集合c的全部元素 public synchronized boolean removeAll(Collection
              c) { return super.removeAll(c); } // 删除“非集合c中的元素” public synchronized boolean retainAll(Collection
              c) { return super.retainAll(c); } // 从index位置开始，将集合c添加到Vector中 public synchronized boolean addAll(int index, Collection
              c) { modCount++; if (index < 0 || index > elementCount) throw new ArrayIndexOutOfBoundsException(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityHelper(elementCount + numNew); int numMoved = elementCount - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); elementCount += numNew; return numNew != 0; } // 返回两个对象是否相等 public synchronized boolean equals(Object o) { return super.equals(o); } // 计算哈希值 public synchronized int hashCode() { return super.hashCode(); } // 调用父类的toString() public synchronized String toString() { return super.toString(); } // 获取Vector中fromIndex(包括)到toIndex(不包括)的子集 public synchronized List
             
               subList(int fromIndex, int toIndex) { return Collections.synchronizedList(super.subList(fromIndex, toIndex), this); } // 删除Vector中fromIndex到toIndex的元素 protected synchronized void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = elementCount - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // Let gc do its work int newElementCount = elementCount - (toIndex-fromIndex); while (elementCount != newElementCount) elementData[--elementCount] = null; } // java.io.Serializable的写入函数 private synchronized void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { s.defaultWriteObject(); }}
             
            
           
          
         
        
       
      
     

    同ArrayList一样，Vector底层数组容量不足时会扩容，然后把原有内容复制过去。

 

    四：三者比较

    1：访问：ArrayList和Vector都实现了RandomAccess接口，提供了随机访问功能，查询O（1）;LinkedList是链表，查询O（n）;

    2：增删：ArrayList和Vector底层是数组，增删容易引起大量的内存操作，效率较慢；LinkedList是链表实现，增加和删除较快；

    3：线程安全性：Vector是线程安全的，观察上面源码可以发现，大部分的方法都用了syncrhoized关键字修饰。所以，如果是单线程下使用，可以用Arrayist，如果是多线程操作的list，则可以用vector来保证线程安全。

    4：ArrayList每次扩容增加50%，Vector扩容增加一倍。