Java中的Collection和Map(二)--List体系

　正如我们在Java中的Collection和Map(一)中所看到的那样，我们经常使用的有ArrayList、LinkedList、Vector、Stack。这里不再累述它们的使用方法，这里主要是说一下他们的底层结构以及使用时机。

 1、ArrayList

　　我们都知道ArrayList是我们经常使用的List集合之一。我们在使用的时候经常通过 new ArrayList() 方法来创建一个ArrayList集合，然后调用它的 add(E e) 方法向集合中存储元素。那么你是否了解当我们使用 new 关键字来创建一ArrayList 集合时底层究竟做了什么事情呢？其实当我们使用new ArrayList()创建集合的时候，底层创建了一个Object类型的数组，初始化长度为0,当我们首次调用 add(E e) 方法的时候，数组长度初始化我10。我们都知道 ArrayList 在一定长度内是没有 限制长度的。既然初始时ArrayList 底层用于存放元素的数组长度为10，那么当我们添加第11 个元素的时候数组角标就会越界。这就牵扯到ArrayList的扩容机制。下面让我们来看一下ArrayList 到底是如何扩容的。

1 2 3 4 5 6 7 8 9 10 11

private void grow(int minCapacity) {        // overflow-conscious code        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + (oldCapacity >> 1);        if (newCapacity - minCapacity < 0)            newCapacity = minCapacity;        if (newCapacity - MAX_ARRAY_SIZE > 0)            newCapacity = hugeCapacity(minCapacity);        // minCapacity is usually close to size, so this is a win:        elementData = Arrays.copyOf(elementData, newCapacity);    }

从上面代码中我们发现 ArrayList 在扩容时候。底层数组长度增加原来的1/2。将原数组中的数据通过Arrays.copyOf 方法拷贝到新数组中，原数组指向新的数组。

综上所述：我们知道了ArrayList底层数据结构其实就是一Object类型的数组。当我们频繁的想ArrayList 中添加元素时ArrayList扩容会影响一定的效率。

2、LinkedList

　　LinkedList 也是我们经常使用的List集合之一。LinkedList 的使用方法和ArrayList的使用方法大致相同。不过LinkedList 多了些自己特有的方法（这源自于LinkedList和ArrayList 底层数据结构的不同）--addFirst(E e)、addLast(E e),下面我们就来看一下LinkedList 底层数据结构。

　　构造方法：

　　public LinkedList() {
　　}

　　当我们通过 new LinkedList() 创建已LinkedList 集合的时候其实就是 new 了一个简单的java 类 ，但当我们使用add(E e) 方法想集合中添加元素时就和ArrayList不同了。

　public void addFirst(E e) {
　　　　linkFirst(e);
　　}

　　public void addLast(E e) {
　　　　linkLast(e);
　　}

　　public boolean add(E e) {
　　　　linkLast(e);
　　　　return true;
　　}

void linkLast(E e) {
　　final Node<E> l = last;
　　final Node<E> newNode = new Node<>(l, e, null);
　　last = newNode;
　　if (l == null)
　　first = newNode;
　　else
　　l.next = newNode;
　　size++;
　　modCount++;
}

private void linkFirst(E e) {
　　final Node<E> f = first;
　　final Node<E> newNode = new Node<>(null, e, f);
　　first = newNode;
　　if (f == null)
　　last = newNode;
　　else
　　f.prev = newNode;
　　size++;
　　modCount++;
}
 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

　　我们从源码中无论是 addFirst、addLast 还是add 方法调用的方法 linkFirst 或者linkLast 方法，而linkLast 又是通过 将一个个Node 结点通过指向的方式将他们连接起来，从中我们可以看出LinkedList 底层是一种自定义的数据结构---链表，在add(E e) 方法的时候不会牵扯到扩容问题。

3、ArrayList和LinkedList  比较

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2. 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
3. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据还有增加数据时候会牵扯到扩容 (这里只是理论上分析，事实上也不一定，ArrayList在末尾插入和删除数据的话，速度反而比LinkedList要快)。
4. 随机查找指定节点的操作get，ArrayList速度要快于LinkedList.

4、Vector

　　Vector底层也是采用数组结构来实现的。整体来说和ArrayList差不多。但还存在不同之处：

1. Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe)，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此,ArrayList的性能比Vector好。
2. 当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%的大小，这样,ArrayList就有利于节约内存空间。

1 2 3 4 5 6 7 8 9 10 11

//Vector扩容方法：<br>private void grow(int minCapacity) {        // overflow-conscious code        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?                                         capacityIncrement : oldCapacity);        if (newCapacity - minCapacity < 0)            newCapacity = minCapacity;        if (newCapacity - MAX_ARRAY_SIZE > 0)            newCapacity = hugeCapacity(minCapacity);        elementData = Arrays.copyOf(elementData, newCapacity);    }

5、Stack（栈）

　　它是Vector的子类。Stack(栈)的特性是先进后出。

　　Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。

　　首次创建堆栈时，它不包含项。

　　直接Stack()创建一个空栈

　　方法摘要：

　　 方法摘要

boolean	empty()            测试堆栈是否为空。
E	peek()            查看堆栈顶部的对象，但不从堆栈中移除它。
E	pop()            移除堆栈顶部的对象，并作为此函数的值返回该对象。
E	push(E item)            把项压入堆栈顶部。
int	search(Object o)            返回对象在堆栈中的位置，以 1 为基数。

　　我们再来看下Stack 的源码：

　　

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

public class Stack<E> extends Vector<E> {     /**      * Creates an empty Stack.      */     public Stack() {     }       /**      * Pushes an item onto the top of this stack. This has exactly      * the same effect as:      * <blockquote><pre>      * addElement(item)</pre></blockquote>      *      * @param   item   the item to be pushed onto this stack.      * @return  the <code>item</code> argument.      * @see     java.util.Vector#addElement      */     public E push(E item) {         addElement(item);           return item;     }       /**      * Removes the object at the top of this stack and returns that      * object as the value of this function.      *      * @return  The object at the top of this stack (the last item      *          of the <tt>Vector</tt> object).      * @throws  EmptyStackException  if this stack is empty.      */     public synchronized E pop() {         E       obj;         int     len = size();           obj = peek();         removeElementAt(len - 1);           return obj;     }       /**      * Looks at the object at the top of this stack without removing it      * from the stack.      *      * @return  the object at the top of this stack (the last item      *          of the <tt>Vector</tt> object).      * @throws  EmptyStackException  if this stack is empty.      */     public synchronized E peek() {         int     len = size();           if (len == 0)             throw new EmptyStackException();         return elementAt(len - 1);     }       /**      * Tests if this stack is empty.      *      * @return  <code>true</code> if and only if this stack contains      *          no items; <code>false</code> otherwise.      */     public boolean empty() {         return size() == 0;     }       /**      * Returns the 1-based position where an object is on this stack.      * If the object <tt>o</tt> occurs as an item in this stack, this      * method returns the distance from the top of the stack of the      * occurrence nearest the top of the stack; the topmost item on the      * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>      * method is used to compare <tt>o</tt> to the      * items in this stack.      *      * @param   o   the desired object.      * @return  the 1-based position from the top of the stack where      *          the object is located; the return value <code>-1</code>      *          indicates that the object is not on the stack.      */     public synchronized int search(Object o) {         int i = lastIndexOf(o);           if (i >= 0) {             return size() - i;         }         return -1;     }       /** use serialVersionUID from JDK 1.0.2 for interoperability */     private static final long serialVersionUID = 1224463164541339165L; }

1. 通过peek()方法注释The object at the top of this stack (the last item of the Vector object，可以发现数组（Vector）的最后一位即为Stack的栈顶
2. pop、peek以及search方法本身进行了同步
3. push方法调用了父类的addElement方法
4. empty方法调用了父类的size方法
5. Vector类为线程安全类

　　综上，Stack类为线程安全类

　　Stack并不要求其中保存数据的唯一性，当Stack中有多个相同的item时，调用search方法，只返回与查找对象equal并且离栈顶最近的item与栈顶间距离。