JAVA List之AarrayList、LinkedList、Vector、Stack详细介绍

一、List常用的实现

List的常见的容器有 ArrayList、LinkedList、Vector、Stack，下面对 每个实现类的特点和实现进行分析。

二、AarrayList

1） 概述

是底层用数组来实现的存储容器，线程是不安全的。

2） 特点

a. 底层实现是通过数组 b. 查询效率高、增删效率低 c. 线程是不安全的 d. 元素是有序的，可以包含重复元素

3） 问答

Q: 大家肯定会有这么一个疑问，既然是数组实现的话，那么数组长度是固定的，Arralist是怎么实现动态扩容的？ A: 通过观察源码分析是其实是通过数组的拷贝来实现的，ArrayList 内部会维护一个 Object[] 对象，并默认初始值为10，当超过这个值的时候，会通过拷贝旧的数组，来实现动态扩容。下面是具体实现的源码。

private void grow(int minCapacity) { int oldCapacity = elementData.length; // >> 1 右移操作 相当于 n/2 新数组的长度 为 旧数组的长度 + 旧数组长度/2 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 拷贝旧的数组 elementData = Arrays.copyOf(elementData, newCapacity); }

三、LinkedList

1） 概述

是底层用双向链表实现的存储容器，线程是不安全的，实现了Deque 和 List接口。

2） 特点

a.底层实现是双向链表，这代表增删效率高。 b.实现了 Deque 接口, 提供了对两端元素操作的方法，意味着可以当做 FIFO (先进先出) 队列 、LIFO（后进先出）栈使用。 c.线程是不安全的。 d.元素是有序的，可以包含重复元素

3）问答

Q: 都说是双向链表结构，那么到底他内部是怎么维护这个结构的呢？ A: Linked内部创建了一个维护 Node 元素，这个元素 记录了当前元素的上一个元素和下一个元素。

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; } }

LinkedList 在内部维护了 first 首元素 和 last 尾元素，所以可以在内部方法中获得 首元素和尾元素。

transient Node<E> first; transient Node<E> last;

在 调用add 方法的时候，尾元素添加为当前元素的的上一个元素 ，并设置上一个元素的下一元素为当前元素

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++; }

四、Vector

1）概述

底层是数组结构，但是线程相对安全的容器。

2）特点

a. 底层是通过数组实现 b. 线程是相对安全的 c. 是有有序的,可以重复 d.实现了RandmoAccess接口，即提供了随机访问功能

3）问答

(1) Q：vector是怎么保证线程安全的呢 A：vector 在add 、remove上都加了 synchronzied 关键字来保证线程安全。但是这个安全是相对安全，下面这个例子有会体现vector线程不安全的的情况

public static void main(String[] args) { Vector vector = new Vector(); for (int i = 0; i < 2; i++) { new Thread(()->{ int count=0; while(count<10){ vector.add(count); System.out.println("当前线程："+Thread.currentThread().getName()+"，vector大小："+vector.size()); count++; } }).start(); } }

打印结果，会出现大小的相同的情况，这是为什么呢，因为size和add方法是线程安全的，但是当两者结合会出现线程不安全的情况，比如 A、B线程 同时调用add ,然后size方法，可能出现 A add 完成后，B获得锁 ，执行 add 和size 方法，再 A线程 执行 size 方法 ，这时候就会导致线程不安全。

当前线程：Thread-1，vector大小：2 当前线程：Thread-0，vector大小：2

五、Stack

1） 概述

继承Vector，代表底层是数组的容器，但是他具有先进后出（FILO） 的特性

2）特点

a. 底层是数组 b. 具有先进后出（FILO）的特点，与栈相似。 c. 线程是相对安全的。

3）常用 API

boolean empty() // 判断栈是否为空 synchronized E peek() // 返回栈顶元素，不执行删除操作 synchronized E pop() //返回栈顶元素，并将其从栈中删除 E push(E object) // 将元素存入栈顶 synchronized int search(Object o) // 查找“元素o”在栈中的位置：由栈底向栈顶方向数

4) 源码分析

（1）push 方法与 ArrayList和 Vector 相似，都是通过grow 实现动态扩容。

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); }

（2）pop 方法，是调用peek方法 返回当前数组下标最后的元素，然后将数组最后一位 置空。

public synchronized void removeElementAt(int index) { modCount++; if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } // elementCount 是当前数组大小 int j = elementCount - index - 1; // 如果当前移除对象索引不是最后一位,则进行数组拷贝,当指定移除元素时会进入判断 if (j > 0) { // 从指定元素位置开始拷贝后面元素 比如 1 2 3 4 5 指定元素为3 则替换成 1 2 4 5 5 System.arraycopy(elementData, index + 1, elementData, index, j); } elementCount--; // 将数组最后一位 置空 elementData[elementCount] = null; /* to let gc do its work */ }

六、总结

最后总结下List各个实现类的特点 （1）保证线程相对安全的：Vector、Stack （2）底层实现是数组的：ArrayList 、Vector、Stack，底层实现是双向链表的：LinkedList （3）查询速度快：ArrayList、Vector、Stack ，增删速度快 LinkedList （4）Vector可以当作 队列和栈使用，Stack可以当作栈使用