一、ArrayList解析

首先我们来讲解的是ArrayList集合，它是我们用的非常多的一个集合

首先我们来讲解的是ArrayList集合，它是我们用的非常多的一个集合

首先我们来看一下ArrayList的属性

DEFAULT_CAPACITY是初始化容量

EMPTY_ELEMENTDATA是指定该ArrayList的容量为0时，返回空数组

DEFAULTCAPACITY_EMPTY_ELEMENTDATA它与上面的区别是，该数组是默认返回的，而后者是在用户指定的容量为0时返回。

elementData保存添加ArrayList的元素

size是ArrayList的实际大小

根据上面我们可以发现，Array List底层其实就是一个数组，ArrayList有扩容这个概念，正因为它扩容，所以可以实现动态增长。

1.2 构造方法

我们来看看构造方法来印证我们上面说的对不对：

 如果指定了容量，那么数组就初始化成对应的容量，否则返回的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA

1.3 Add方法

add方法可以说是ArrayList比较重要的方法了，我们来总览一下

 1.3.1 add(E e)

步骤：

　　检查是否需要扩容

　　插入元素

首先，我们来看这个方法

1  public boolean add(E e) {
2         ensureCapacityInternal(size + 1);  // Increments modCount!!
3         elementData[size++] = e;
4         return true;
5     }

该方法很短，我们可以根据方法名就猜到他是干什么的

　　确认list容量，尝试容量加1，看看有无必要

　　添加元素

接下来我们来看看这个容量即1是否满足我们的需求

 我们看ensureExplicitCapacity，如果要的最小容量比数组长度要大，就调用grow来扩容

接下来我们来看看grow是怎么实现的

 相当于扩容1.5倍

进去看copyOf方法

 到目前为止，我们就可以知道add的基本实现了

首先去检查一下数组的容量是否足够

　　扩容到原来的1.5倍

　　第一次扩容后，如果容量还是小于minCapacity就将容量扩充到minCapacity

　　足够：直接添加

　　不足够：扩容

1.3.2 add(int index,E element)

步骤

　　检查角标

　　空间检查，如果有需要进行扩容

　　插入元素

我们来看看插入的实现

 我们可以发现，与扩容相关ArrayList的add方法底层其实都是arraycopy来实现的

看到arraycopy，我们可以发现该方法是由C/C++来编写的，并不是由Java实现的

1.4 get方法

　　检查角标

　　返回元素

 1   // 检查角标
 2    private void rangeCheck(int index) {
 3         if (index >= size)
 4             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 5     }
 6 
 7     // 返回元素
 8     E elementData(int index) {
 9         return (E) elementData[index];
10     }

1.5 set方法

步骤

　　检查角标

　　替代元素

　　返回旧值

 1.6 remove方法

步骤

　　检查角标

　　删除元素

　　计算需要移动的个数并移动

　　设置为null，让gc回收

 numMoved是指需要向左移动的个数

1.7细节再说明

ArrayList是基于动态数组实现的，在增删的时候需要数组的拷贝复制

ArrayList的默认初始化容量是10，每次扩容的时候增加先前容量的一半，也就是1.5倍

删除元素时不会减少容量，若希望减少容量则调用trimToSize()

它不是线程安全的，可以存放null值

二、Vector与ArrayList的区别

Vector是jdk1.2的类了，比较老旧的一个集合类。

Vector底层也是数组，与ArrayList最大的区别就是：同步（线程安全）

Vector是同步的，我们可以从方法上就看得出来

有synchronized关键字

在要求非同步的情况下，我们一半都是使用ArrayList来代替Vector

如果想要ArrayList实现同步，则可以使用Collections工具类的方法

1 List list = Collections.synchronizedList(new ArrayList(...));

就可以实现同步了。

还有另一个区别

ArrayList在底层数组不够用时，在原来的基础上扩展0.5倍，Vector是扩展1倍

三、LinkedList解析

LinkedList底层是双向链表，从结构上看到了LinkedList实现了Deque接口，所以我们可以操作LinkedList像操作队列和栈一样

 ListedList变量就这几个

3.1  构造方法

LinkedList构造方法有两个

 3.2 add方法

add方法实际上就是往链表最后添加元素

 1 public boolean add(E e) {
 2         linkLast(e);
 3         return true;
 4     }
 5 
 6     void linkLast(E e) {
 7         final Node<E> l = last;
 8         final Node<E> newNode = new Node<>(l, e, null);
 9         last = newNode;
10         if (l == null)
11             first = newNode;
12         else
13             l.next = newNode;
14         size++;
15         modCount++;
16     }

3.3 remove方法

 实际上就下面图的操作

3.4 get方法

可以看到get方法实现就两段代码

1   public E get(int index) {
2         checkElementIndex(index);
3         return node(index).item;
4     }

我们进去看一下具体怎么实现的

下标要是小于长度的一半就从头遍历，否则从未遍历

3.5 set方法

set方法和get方法其实差不多，根据下标来判断是从头遍历还是从尾遍历

1 public E set(int index, E element) {
2         checkElementIndex(index);
3         Node<E> x = node(index);
4         E oldVal = x.item;
5         x.item = element;
6         return oldVal;
7     }

四、总结

ArrayList

底层是数组实现，默认容量是10，每次扩容增加原先容量的一半，增删的时候，需要数组拷贝复制，native方法由c/c++实现

LinkedList

　　底层是双向链表（双向链表方便往前遍历）

Vector：底层是数组，现在很少用基本上被ArrayList替代，原因有两个

　　Vector所有方法都是同步的，有性能损失

　　Vector初始length是10，超过length时以100%比例增长，相比ArrayList消耗更多内存。

总的来说，增删多用linkedlist，查找多用ArrayList