Java技术栈.基础篇—详说集合之一

Myth丶恋晨 2022-05-23 03:29 182阅读 0赞

# 一、集合与数组 #

**数组：**（可以存储基本数据类型）是用来存取对象的一种容器，数组的长度固定，不适合在对象数量未知的情况下使用。  
**集合：**（只能存储对象，对象类型可以不一样）集合与数组最大不同：长度可变，可在对象数量未知的情况下使用，使用比较广泛。

# 集合总览 #

![这里写图片描述][70]

**Collection：**接口是集合类的根接口，Java中没有提供这个接口的直接实现类。但是却被继承产生了两个接口：Set和List。Set中不能包含重复的元素。List是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。

**Map：**是Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的，但是都属于集合类的一部分。Map包含了key-value对。Map不能包含重复的key，但是可以包含相同的value。

**Iterator：**所有的集合类，都实现了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法：  
1.hasNext()是否还有下一个元素。  
2.next()返回下一个元素。  
3.remove()删除当前元素。

**Collection接口的共性方法:**  
这里把Collection接口中的共性方法单独拿出来说一下，

//增加  将指定对象存储到容器中  add 方法的参数类型是Object 便于接收任意对象
    1：add()  
    //将指定集合中的元素添加到调用该方法的集合中 
    2：addAll()   
    //删除  将指定的对象从集合中删除 
    3：remove()  
    //将指定集合中的元素删除
    4：removeAll()   
    //修改  清空集合中的所有元素 
    5：clear()  
    / 判断  判断集合是否为空
    6：isEmpty()   
    //判断集合何中是否包含指定对象
    7：contains()   
    //判断集合中是否包含指定集合      
    8：containsAll()   
    //判断两个对象是否相等
    9.equals()
    //返回集合容器的大小    
    10：int size()      
    //集合转换数组
    11： toArray()

# List详解 #

---|List: 有存储顺序, 可重复  
                    ---|ArrayList:  数组实现, 查找快, 增删慢  
                                由于是数组实现, 在增和删的时候会牵扯到数组  
                                                    增容, 以及拷贝元素. 所以慢。数组是可以直接  
                                                    按索引查找, 所以查找时较快  
                    ---|LinkedList: 链表实现, 增删快, 查找慢  
                                由于链表实现, 增加时只要让前一个元素记住自  
                                                   己就可以, 删除时让前一个元素记住后一个元  
                                                   素, 后一个元素记住前一个元素. 这样的增删效  
                                                 率较高但查询时需要一个一个的遍历, 所以效率  
                                                    较低  
                    ---|Vector: 和ArrayList原理相同, 但线程安全, 效率略低  
                                 和ArrayList实现方式相同, 但考虑了线程安全问  
                                                    题, 所以效率略低

List适合顺序存储，允许重复元素存在，List接口的实现类中常用的是ArrayList和LinkedList，这两个类在使用中是有一定不同的。如果查询较多则使用ArrayList，插入删除变更较多则用LinkedList，而若是对线程安全有要求则使用Vector。

**List集合特有方法:**

//指定位置添加元素 
    1：void add(int index, E element)  
    //指定位置添加集合            
    2.boolean addAll(int index, Collection c) 
    //删除指定位置元素    
    3：删除  remove(int index)   
    //修改集合中的元素  返回的是需要替换的集合中的元素
    4：E set(int index, E element)      
    5：获取指定索引的元素    注意： IndexOutOfBoundsException 
    E get(int index) 
    //获取某个元素的索引  找不到返回-1，有多个时返回第一次出现的位置         
    6：int indexOf(Object o)    
    //list允许重复，因此在list中同一个元素可能有多个，此方法返回最后一个
    7：lastIndexOf(Object o) 
    // 求子集合   不包含toIndex
    8： List<E> subList(int fromIndex, int toIndex)

## ArrayList ##

ArrayList就是传说中的动态数组，就是Array的复杂版本，它提供了如下一些好处：  
a.动态的增加和减少元素  
b.实现了Collection和List接口  
c.灵活的设置数组的大小

### 构造器 ###

ArrayList中有三个构造器：

//默认的构造器，将会以默认（16）的大小来初始化内部的数组 
    public ArrayList(); 
    //用一个Collection对象来构造，并将该集合的元素添加到ArrayList
    public ArrayList(Collection); 
    //用指定的大小来初始化内部的数组 
    public ArrayList(int);

### ArrayList的同步 ###

IsSynchronized属性和ArrayList.Synchronized方法用于实现ArrayList的同步。  
IsSynchronized属性标识当前的ArrayList实例是否支持线程同步，而ArrayList.Synchronized静态方法则会返回一个ArrayList的线程同步的封装。

如果使用非线程同步的实例，那么在多线程访问的时候，需要自己手动调用lock来保持线程同步，例如：

//当ArrayList为非线程包装的时候，SyncRoot属性其实就是它自己，但是为了满
    //足Collection的SyncRoot定义，这里还是使用SyncRoot来保持源代码的规范性 
    ArrayList list = new ArrayList(); 
    lock( list.SyncRoot ) 
    { 
    list.Add( “Add a Item” ); 
    }

如果使用ArrayList.Synchronized方法返回的实例，那么就不用考虑线程同步的问题，这个实例本身就是线程安全的，实际上ArrayList内部实现了一个保证线程同步的内部类，ArrayList.Synchronized返回的就是这个类的实例，它里面的每个属性都是用了lock关键字来保证线程同步。

### Count属性和Capacity属性 ###

Count属性是目前ArrayList包含的元素的数量，这个属性是只读的。  
Capacity属性是目前ArrayList能够包含的最大数量，可以手动的设置这个属性，但是当设置为小于Count值的时候会引发一个异常。

### TrimSize方法 ###

这个方法用于将ArrayList固定到实际元素的大小，当动态数组元素确定不在添加的时候，可以调用这个方法来释放空余的内存。

### ArrayList与数组转换 ###

例1：

ArrayList List = new ArrayList(); 
    List.Add(1); 
    List.Add(2); 
    List.Add(3);
    Int32[] values = (Int32[])List.ToArray(typeof(Int32));

例2：

ArrayList List = new ArrayList(); 
    List.Add(1); 
    List.Add(2); 
    List.Add(3);
    Int32[] values = new Int32[List.Count]; 
    List.CopyTo(values);

上面介绍了两种从ArrayList转换到数组的方法  
例3：

ArrayList List = new ArrayList(); 
    List.Add( “string” ); 
    List.Add( 1 ); 
    //往数组中添加不同类型的元素
    object[] values = List.ToArray(typeof(object)); //正确 
    string[] values = (string[])List.ToArray(typeof(string)); //错误

和数组不一样，因为ArrayList可以转换为Object数组，所以往ArrayList里面添加不同类型的元素是不会出错的，但是当调用ArrayList.ToArray方法的时候，要么传递所有元素都可以正确转型的类型或者Object类型，否则将会抛出无法转型的异常。

### ArrayList的使用建议 ###

**（1）ArrayList是Array的复杂版本**  
ArrayList内部封装了一个Object类型的数组，从一般的意义来说，它和数组没有本质的差别，甚至于ArrayList的许多方法，如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。  
**（2）内部的Object类型的影响**  
对于一般的引用类型来说，这部分的影响不是很大，但是对于值类型来说，往ArrayList里面添加和修改元素，都会引起装箱和拆箱的操作，频繁的操作可能会影响一部分效率。  
但是恰恰对于大多数人，多数的应用都是使用值类型的数组。  
消除这个影响是没有办法的，除非你不用它，否则就要承担一部分的效率损失，不过这部分的损失不会很大。  
**（3）数组扩容**  
这是对ArrayList效率影响比较大的一个因素。  
每当执行Add、AddRange、Insert、InsertRange等添加元素的方法，都会检查内部数组的容量是否足够，如果不够，它就会以当前容量的两倍来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。  
例1：比如，一个可能有200个元素的数据动态添加到一个以默认16个元素大小创建的ArrayList中，将会经过：  
16\*2\*2\*2\*2 = 256  
四次的扩容才会满足最终的要求，那么如果一开始就以：

ArrayList List = new ArrayList( 210 );

的方式创建ArrayList，不仅会减少4次数组创建和Copy的操作，还会减少内存使用。

例2：  
预计有30个元素而创建了一个ArrayList：

ArrayList List = new ArrayList(30);

在执行过程中，加入了31个元素，那么数组会扩充到60个元素的大小，而这时候不会有新的元素再增加进来，而且有没有调用TrimSize方法，那么就有1次扩容的操作，并且浪费了29个元素大小的空间。如果这时候，用：

ArrayList List = new ArrayList(40);

那么一切都解决了。  
所以说，正确的预估可能的元素，并且在适当的时候调用TrimSize方法是提高ArrayList使用效率的重要途径。

### 效率损失 ###

频繁的调用IndexOf、Contains等方法（Sort、BinarySearch等方法经过优化，不在此列）会引起的效率损失  
首先，我们要明确一点，ArrayList是动态数组，它不支持通过Key或者Value快速访问的算法，所以实际上调用IndexOf、Contains等方法是执行的简单的循环来查找元素，所以频繁的调用此类方法并不比你自己写循环并且稍作优化来的快，如果有这方面的要求，建议使用Hashtable或SortedList等键值对的集合。

### 优缺点 ###

ArrayList类实现了List接口，由ArrayList类实现的List集合采用数组结构保存对象。数组结构的优点是便于对集合进行快速的随机访问，如果经常需要根据索引位置访问集合中的对象，使用由ArrayList类效率较好。  
数组结构的缺点是向指定索引位置插入对象和删除指定索引位置对象的速度较慢，如果经常需要向List集合的指定索引位置插入对象，或者是删除List集合的指定索引位置的对象，使用由ArrayList类实现的List集合的效率则较低，并且插入或删除对象的索引位置越小效率越低，原因是当向指定的索引位置插入对象时，会同时将指定索引位置及之后的所有对象相应的向后移动一位。当删除指定索引位置的对象时，会同时将指定索引位置之后的所有对象相应的向前移动一位。如果在指定的索引位置之后有大量的对象，将严重影响对集合的操作效率。  
**源码解析**

<span style="font-family:Microsoft YaHei;">package java.util;
    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, 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<? extends E> 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> 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<? extends E> 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<? extends E> 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<E> v = (ArrayList<E>) 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<size; i++)
                s.writeObject(elementData[i]);
        if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
        // java.io.Serializable的读取函数：根据写入方式读出
        // 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            // Read in size, and any hidden stuff
            s.defaultReadObject();
            // 从输入流中读取ArrayList的“容量”
            int arrayLength = s.readInt();
            Object[] a = elementData = new Object[arrayLength];
            // 从输入流中将“所有的元素值”读出
            for (int i=0; i<size; i++)
                a[i] = s.readObject();
        }
    }
    </span>

## LinkedList ##

### 简介 ###

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。  
LinkedList 实现 List 接口，能对它进行队列操作。  
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。  
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。  
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。  
LinkedList 是非同步的。

**构造函数**

// 默认构造函数
    LinkedList()
    
    // 创建一个LinkedList，包括Collection中的全部元素。
    LinkedList(Collection<? extends E> collection)

**LinkedList中的API**

LinkedList的API
    boolean       add(E object)
    void          add(int location, E object)
    boolean       addAll(Collection<? extends E> collection)
    boolean       addAll(int location, Collection<? extends E> collection)
    void          addFirst(E object)
    void          addLast(E object)
    void          clear()
    Object        clone()
    boolean       contains(Object object)
    Iterator<E>   descendingIterator()
    E             element()
    E             get(int location)
    E             getFirst()
    E             getLast()
    int           indexOf(Object object)
    int           lastIndexOf(Object object)
    ListIterator<E>     listIterator(int location)
    boolean       offer(E o)
    boolean       offerFirst(E e)
    boolean       offerLast(E e)
    E             peek()
    E             peekFirst()
    E             peekLast()
    E             poll()
    E             pollFirst()
    E             pollLast()
    E             pop()
    void          push(E e)
    E             remove()
    E             remove(int location)
    boolean       remove(Object object)
    E             removeFirst()
    boolean       removeFirstOccurrence(Object o)
    E             removeLast()
    boolean       removeLastOccurrence(Object o)
    E             set(int location, E object)
    int           size()
    <T> T[]       toArray(T[] contents)
    Object[]     toArray()

**AbstractSequentialList简介**  
LinkedList是AbstractSequentialList的子类。  
AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些方法，这些方法都是支持随机访问List的，LinkedList是双向链表，继承于AbstractSequentialList，也可以通过上述方法随机访问LinkedList的元素。

此外，若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法。

### LinkedList数据结构 ###

java.lang.Object
       ↳     java.util.AbstractCollection<E>
             ↳     java.util.AbstractList<E>
                   ↳     java.util.AbstractSequentialList<E>
                         ↳     java.util.LinkedList<E>
    
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
        }

![这里写图片描述][70 1]

LinkedList的本质是双向链表。  
(1) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。  
(2) LinkedList包含两个重要的成员：header 和 size。  
　　header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。 size是双向链表中节点的个数。

### 源码解析 ###

为了更了解LinkedList的原理，下面对LinkedList源码代码作出分析。  
在阅读源码之前，我们先对LinkedList的整体实现进行大致说明：  
LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。  
LinkedList也实现了List接口，也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”。LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？  
实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若后者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。  
这就是“双线链表和索引值联系起来”的方法。

接下来开始阅读源码，只要理解双向链表，那么LinkedList的源码很容易理解的。

package java.util;
    
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        // 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。
        private transient Entry<E> header = new Entry<E>(null, null, null);
    
        // LinkedList中元素个数
        private transient int size = 0;
    
        // 默认构造函数：创建一个空的链表
        public LinkedList() {
            header.next = header.previous = header;
        }
    
        // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
    
        // 获取LinkedList的第一个元素
        public E getFirst() {
            if (size==0)
                throw new NoSuchElementException();
    
            // 链表的表头header中不包含数据。
            // 这里返回header所指下一个节点所包含的数据。
            return header.next.element;
        }
    
        // 获取LinkedList的最后一个元素
        public E getLast()  {
            if (size==0)
                throw new NoSuchElementException();
    
            // 由于LinkedList是双向链表；而表头header不包含数据。
            // 因而，这里返回表头header的前一个节点所包含的数据。
            return header.previous.element;
        }
    
        // 删除LinkedList的第一个元素
        public E removeFirst() {
            return remove(header.next);
        }
    
        // 删除LinkedList的最后一个元素
        public E removeLast() {
            return remove(header.previous);
        }
    
        // 将元素添加到LinkedList的起始位置
        public void addFirst(E e) {
            addBefore(e, header.next);
        }
    
        // 将元素添加到LinkedList的结束位置
        public void addLast(E e) {
            addBefore(e, header);
        }
    
        // 判断LinkedList是否包含元素(o)
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }
    
        // 返回LinkedList的大小
        public int size() {
            return size;
        }
    
        // 将元素(E)添加到LinkedList中
        public boolean add(E e) {
            // 将节点(节点数据是e)添加到表头(header)之前。
            // 即，将节点添加到双向链表的末端。
            addBefore(e, header);
            return true;
        }
    
        // 从LinkedList中删除元素(o)
        // 从链表开始查找，如存在元素(o)则删除该元素并返回true；
        // 否则，返回false。
        public boolean remove(Object o) {
            if (o==null) {
                // 若o为null的删除情况
                for (Entry<E> e = header.next; e != header; e = e.next) {
                    if (e.element==null) {
                        remove(e);
                        return true;
                    }
                }
            } else {
                // 若o不为null的删除情况
                for (Entry<E> e = header.next; e != header; e = e.next) {
                    if (o.equals(e.element)) {
                        remove(e);
                        return true;
                    }
                }
            }
            return false;
        }
    
        // 将“集合(c)”添加到LinkedList中。
        // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。
        public boolean addAll(Collection<? extends E> c) {
            return addAll(size, c);
        }
    
        // 从双向链表的index开始，将“集合(c)”添加到双向链表中。
        public boolean addAll(int index, Collection<? extends E> c) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Object[] a = c.toArray();
            // 获取集合的长度
            int numNew = a.length;
            if (numNew==0)
                return false;
            modCount++;
    
            // 设置“当前要插入节点的后一个节点”
            Entry<E> successor = (index==size ? header : entry(index));
            // 设置“当前要插入节点的前一个节点”
            Entry<E> predecessor = successor.previous;
            // 将集合(c)全部插入双向链表中
            for (int i=0; i<numNew; i++) {
                Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
                predecessor.next = e;
                predecessor = e;
            }
            successor.previous = predecessor;
    
            // 调整LinkedList的实际大小
            size += numNew;
            return true;
        }
    
        // 清空双向链表
        public void clear() {
            Entry<E> e = header.next;
            // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作：
            // (01) 设置前一个节点为null 
            // (02) 设置当前节点的内容为null 
            // (03) 设置后一个节点为“新的当前节点”
            while (e != header) {
                Entry<E> next = e.next;
                e.next = e.previous = null;
                e.element = null;
                e = next;
            }
            header.next = header.previous = header;
            // 设置大小为0
            size = 0;
            modCount++;
        }
    
        // 返回LinkedList指定位置的元素
        public E get(int index) {
            return entry(index).element;
        }
    
        // 设置index位置对应的节点的值为element
        public E set(int index, E element) {
            Entry<E> 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));
        }
    
        // 获取双向链表中指定位置的节点
        private Entry<E> entry(int index) {
            if (index < 0 || index >= size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Entry<E> e = header;
            // 获取index处的节点。
            // 若index < 双向链表长度的1/2,则从前先后查找;
            // 否则，从后向前查找。
            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;
        }
    
        // 从前向后查找，返回“值为对象(o)的节点对应的索引”
        // 不存在就返回-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)的节点对应的索引”
        // 不存在就返回-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;
        }
    
        // 返回第一个节点
        // 若LinkedList的大小为0,则返回null
        public E peek() {
            if (size==0)
                return null;
            return getFirst();
        }
    
        // 返回第一个节点
        // 若LinkedList的大小为0,则抛出异常
        public E element() {
            return getFirst();
        }
    
        // 删除并返回第一个节点
        // 若LinkedList的大小为0,则返回null
        public E poll() {
            if (size==0)
                return null;
            return removeFirst();
        }
    
        // 将e添加双向链表末尾
        public boolean offer(E e) {
            return add(e);
        }
    
        // 将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)的节点，则删除该节点
        public boolean removeFirstOccurrence(Object o) {
            return remove(o);
        }
    
        // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点
        // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
        public boolean removeLastOccurrence(Object o) {
            if (o==null) {
                for (Entry<E> e = header.previous; e != header; e = e.previous) {
                    if (e.element==null) {
                        remove(e);
                        return true;
                    }
                }
            } else {
                for (Entry<E> e = header.previous; e != header; e = e.previous) {
                    if (o.equals(e.element)) {
                        remove(e);
                        return true;
                    }
                }
            }
            return false;
        }
    
        // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)
        public ListIterator<E> listIterator(int index) {
            return new ListItr(index);
        }
    
        // List迭代器
        private class ListItr implements ListIterator<E> {
            // 上一次返回的节点
            private Entry<E> lastReturned = header;
            // 下一个节点
            private Entry<E> next;
            // 下一个节点对应的索引值
            private int nextIndex;
            // 期望的改变计数。用来实现fail-fast机制。
            private int expectedModCount = modCount;
    
            // 构造函数。
            // 从index位置开始进行迭代
            ListItr(int index) {
                // 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.next;
                } else {
                    next = header;
                    for (nextIndex=size; 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.next;
                nextIndex++;
                return lastReturned.element;
            }
    
            // 是否存在上一个元素
            public boolean hasPrevious() {
                // 通过元素索引是否等于0，来判断是否达到开头。
                return nextIndex != 0;
            }
    
            // 获取上一个元素
            public E previous() {
                if (nextIndex == 0)
                throw new NoSuchElementException();
    
                // next指向链表的上一个元素
                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<E> 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();
            }
        }
    
        // 双向链表的节点所对应的数据结构。
        // 包含3部分：上一节点，下一节点，当前节点值。
        private static class Entry<E> {
            // 当前节点所包含的值
            E element;
            // 下一个节点
            Entry<E> next;
            // 上一个节点
            Entry<E> previous;
    
            /**
             * 链表节点的构造函数。
             * 参数说明：
             *   element  —— 节点所包含的数据
             *   next      —— 下一个节点
             *   previous —— 上一个节点
             */
            Entry(E element, Entry<E> next, Entry<E> previous) {
                this.element = element;
                this.next = next;
                this.previous = previous;
            }
        }
    
        // 将节点(节点数据是e)添加到entry节点之前。
        private Entry<E> addBefore(E e, Entry<E> entry) {
            // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e
            Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
            newEntry.previous.next = newEntry;
            newEntry.next.previous = newEntry;
            // 修改LinkedList大小
            size++;
            // 修改LinkedList的修改统计数：用来实现fail-fast机制。
            modCount++;
            return newEntry;
        }
    
        // 将节点从链表中删除
        private E remove(Entry<E> e) {
            if (e == header)
                throw new NoSuchElementException();
    
            E result = e.element;
            e.previous.next = e.next;
            e.next.previous = e.previous;
            e.next = e.previous = null;
            e.element = null;
            size--;
            modCount++;
            return result;
        }
    
        // 反向迭代器
        public Iterator<E> 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的Object[]数组
        public Object[] toArray() {
        // 新建Object[]数组
        Object[] result = new Object[size];
            int i = 0;
            // 将链表中所有节点的数据都添加到Object[]数组中
            for (Entry<E> e = header.next; e != header; e = e.next)
                result[i++] = e.element;
        return result;
        }
    
        // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
        public <T> T[] toArray(T[] a) {
            // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
            // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
            if (a.length < size)
                a = (T[])java.lang.reflect.Array.newInstance(
                                    a.getClass().getComponentType(), size);
            // 将链表中所有节点的数据都添加到数组a中
            int i = 0;
            Object[] result = a;
            for (Entry<E> e = header.next; e != header; e = e.next)
                result[i++] = e.element;
    
            if (a.length > size)
                a[size] = null;
    
            return a;
        }
    
    
        // 克隆函数。返回LinkedList的克隆对象。
        public Object clone() {
            LinkedList<E> clone = null;
            // 克隆一个LinkedList克隆对象
            try {
                clone = (LinkedList<E>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
    
            // 新建LinkedList表头节点
            clone.header = new Entry<E>(null, null, null);
            clone.header.next = clone.header.previous = clone.header;
            clone.size = 0;
            clone.modCount = 0;
    
            // 将链表中所有节点的数据都添加到克隆对象中
            for (Entry<E> e = header.next; e != header; e = e.next)
                clone.add(e.element);
    
            return clone;
        }
    
        // java.io.Serializable的写入函数
        // 将LinkedList的“容量，所有的元素值”都写入到输出流中
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            // Write out any hidden serialization magic
            s.defaultWriteObject();
    
            // 写入“容量”
            s.writeInt(size);
    
            // 将链表中所有节点的数据都写入到输出流中
            for (Entry e = header.next; e != header; e = e.next)
                s.writeObject(e.element);
        }
    
        // java.io.Serializable的读取函数：根据写入方式反向读出
        // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            // Read in any hidden serialization magic
            s.defaultReadObject();
    
            // 从输入流中读取“容量”
            int size = s.readInt();
    
            // 新建链表表头节点
            header = new Entry<E>(null, null, null);
            header.next = header.previous = header;
    
            // 从输入流中将“所有的元素值”并逐个添加到链表中
            for (int i=0; i<size; i++)
                addBefore((E)s.readObject(), header);
        }
    
    }

总结一下：  
(1) LinkedList 实际上是通过双向链表去实现的。  
它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点的值，上一个节点，下一个节点。  
(2) 从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。  
(3) LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。  
(4) LinkedList实现了java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。  
(5) 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

第一个元素（头部）                 最后一个元素（尾部）
            抛出异常        特殊值            抛出异常        特殊值
    插入    addFirst(e)    offerFirst(e)    addLast(e)        offerLast(e)
    移除    removeFirst()  pollFirst()      removeLast()    pollLast()
    检查    getFirst()     peekFirst()      getLast()        peekLast()

**LinkedList可以作为FIFO(先进先出)的队列，作为FIFO的队列时，下表的方法等价：**

队列方法       等效方法
    add(e)        addLast(e)
    offer(e)      offerLast(e)
    remove()      removeFirst()
    poll()        pollFirst()
    element()     getFirst()
    peek()        peekFirst()

**LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：**

栈方法        等效方法
    push(e)      addFirst(e)
    pop()        removeFirst()
    peek()       peekFirst()

### LinkedList的遍历方式 ###

LinkedList支持多种遍历方式，建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。  
**（1）通过迭代器遍历。即通过Iterator去遍历。**

for(Iterator iter = list.iterator(); iter.hasNext();)
        iter.next();

**（2）通过快速随机访问遍历LinkedList**

int size = list.size();
    for (int i=0; i<size; i++) {
        list.get(i);        
    }

**（3）通过另外一种for循环来遍历LinkedList**

for (Integer integ:list) ;

**（4）通过pollFirst()来遍历LinkedList**

while(list.pollFirst() != null) ;

**（5）通过pollLast()来遍历LinkedList**

while(list.pollLast() != null);

**（6）通过removeFirst()来遍历LinkedList**

try {
        while(list.removeFirst() != null);
    } catch (NoSuchElementException e) {
    }

**（7）通过removeLast()来遍历LinkedList**

try {
        while(list.removeLast() != null);
    } catch (NoSuchElementException e) {
    }

## Vector ##

### 简介 ###

Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。  
Vector 继承了AbstractList，实现了List；所以，它是一个队列，支持相关的添加、删除、修改、遍历等功能。  
Vector 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在Vector中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。  
Vector 实现了Cloneable接口，即实现clone()函数。它能被克隆。

**和ArrayList不同，Vector中的操作是线程安全的。**

### Vector的构造函数 ###

//Vector共有4个构造函数
    // 默认构造函数
    Vector()
    // capacity是Vector的默认容量大小。当由于增加数据导致容量增加时，每次容量会增加一倍。
    Vector(int capacity)
    // capacity是Vector的默认容量大小，capacityIncrement是每次Vector容量增加时的增量值。
    Vector(int capacity, int capacityIncrement)
    // 创建一个包含collection的Vector
    Vector(Collection<? extends E> collection)

### Vector的API ###

package java.util;
    
    public class Vector<E>
        extends AbstractList<E>
        implements List<E>, 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<? extends E> 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<E> elements() {
            // 通过匿名类实现Enumeration
            return new Enumeration<E>() {
                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<E> v = (Vector<E>) 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> 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<? extends E> 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<? extends E> 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<E> 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();
        }
    }

### Vector继承关系 ###

java.lang.Object
       ↳     java.util.AbstractCollection<E>
             ↳     java.util.AbstractList<E>
                   ↳     java.util.Vector<E>
    
    public class Vector<E>
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        }

![继承关系图][70 2]

Vector的数据结构和ArrayList差不多，它包含了3个成员变量：elementData , elementCount， capacityIncrement。

(1) elementData 是”Object\[\]类型的数组”，它保存了添加到Vector中的元素。elementData是个动态数组，如果初始化Vector时，没指定动态数组的>大小，则使用默认大小10。随着Vector中元素的增加，Vector的容量也会动态增长，capacityIncrement是与容量增长相关的增长系数，具体的增长方式，请参考源码分析中的ensureCapacity()函数。

(2) elementCount 是动态数组的实际大小。

(3) capacityIncrement 是动态数组的增长系数。如果在创建Vector时，指定了capacityIncrement的大小；则，每次当Vector中动态数组容量增加时，增加的大小都是capacityIncrement。

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

(5) 当Vector容量不足以容纳全部元素时，Vector的容量会增加。若容量增加系数 >0，则将容量的值增加“容量增加系数”；否则，将容量大小增加一倍。

(6) Vector的克隆函数，即是将全部元素克隆到一个数组中。

### 遍历方式 ###

**通过Iterator去遍历**

for(Iterator iter = vec.iterator(); iter.hasNext();)
        iter.next();

**通过索引值去遍历**

Integer value = null;
    int size = vec.size();
    for (int i=0; i<size; i++) {
        value = (Integer)vec.get(i);        
    }

**for循环**

Integer value = null;
    for (Integer integ:vec) {
        value = integ;
    }

**Enumeration遍历**

Integer value = null;
    Enumeration enu = vec.elements();
    while (enu.hasMoreElements()) {
        value = (Integer)enu.nextElement();
    }

总结：遍历Vector，使用索引的随机访问方式最快，使用迭代器最慢。

## Stack ##

### 简介 ###

Stack是栈。它的特性是：先进后出(FILO, First In Last Out)。  
java工具包中的Stack是继承于Vector(矢量队列)的，由于Vector是通过数组实现的，这就意味着，Stack也是通过数组实现的，而非链表。当然，我们也可以将LinkedList当作栈来使用！已经详细介绍过Vector的数据结构，这里就不再对Stack的数据结构进行说明了。

### 继承关系 ###

java.lang.Object
    ↳     java.util.AbstractCollection<E>
       ↳     java.util.AbstractList<E>
           ↳     java.util.Vector<E>
               ↳     java.util.Stack<E>
    
    public class Stack<E> extends Vector<E> {
        }

![这里写图片描述][70 3]

### 构造函数 ###

只有一个默认的而构造函数

Stack()

### Stack源码解析 ###

package java.util;
    
    public
    class Stack<E> extends Vector<E> {
        // 版本ID。这个用于版本升级控制，这里不须理会！
        private static final long serialVersionUID = 1224463164541339165L;
    
        // 构造函数
        public Stack() {
        }
    
        // push函数：将元素存入栈顶
        public E push(E item) {
            // 将元素存入栈顶。
            // addElement()的实现在Vector.java中
            addElement(item);
    
            return item;
        }
    
        // pop函数：返回栈顶元素，并将其从栈中删除
        public synchronized E pop() {
            E    obj;
            int    len = size();
    
            obj = peek();
            // 删除栈顶元素，removeElementAt()的实现在Vector.java中
            removeElementAt(len - 1);
    
            return obj;
        }
    
        // peek函数：返回栈顶元素，不执行删除操作
        public synchronized E peek() {
            int    len = size();
    
            if (len == 0)
                throw new EmptyStackException();
            // 返回栈顶元素，elementAt()具体实现在Vector.java中
            return elementAt(len - 1);
        }
    
        // 栈是否为空
        public boolean empty() {
            return size() == 0;
        }
    
        // 查找“元素o”在栈中的位置：由栈底向栈顶方向数
        public synchronized int search(Object o) {
            // 获取元素索引，elementAt()具体实现在Vector.java中
            int i = lastIndexOf(o);
    
            if (i >= 0) {
                return size() - i;
            }
            return -1;
        }
    }

(1) Stack实际上也是通过数组去实现的。  
执行push时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。  
执行peek时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。  
执行pop时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。  
(2) Stack继承于Vector，意味着Vector拥有的属性和功能，Stack都拥有。  
[参考1][1]  
[参考2][2]

[70]: /images/20220523/a32e75c16f3a4fdab6944cb5aa10292c.png
[70 1]: /images/20220523/a6856adff29b46719fe72172016539a4.png
[70 2]: /images/20220523/690e29a8ad074d6b94aeca9459b39ad5.png
[70 3]: /images/20220523/a7a42fc00de54c63b3c99adc1ce19089.png
[1]: https://www.cnblogs.com/leeplogs/p/5891861.html
[2]: https://www.cnblogs.com/skywang12345/p/3308807.html