LinkedList、ArrayList

https://mp.weixin.qq.com/s/g2wy5orYf2r8qo7lg15_Fg
https://github.com/crossoverJie/Java-Interview/blob/master/MD/HashMap.md
https://www.cnblogs.com/skywang12345/p/3308900.html

LinkedList

LinkedList 是一个双向列表：

我们看一下它的 添加、查找 实现方式：

add：

//添加一个元素，直接添加到列表末尾
public boolean add(E e) {
    linkLast(e);
    return true;
}

//添加一个元素，并指定添加到的位置：index
public void add(int index, E element) {
    linkBefore(element, node(index));
}

//根据 index 查找 node，并返回
Node<E> node(int index) {
    //加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

//创建一个 Node，把 e 包含进去，并前后结成链
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
}

元素添加到 LinkedList 末尾

get：

public E get(int index) {
        //直接调用 node() 方法，上面有代码。
    return node(index).item;
}

ArrayList

add 和 get 方法：

//确认ArrayList的容量，若容量不够，则增加容量

public boolean add(E e) {
    int minCapacity = size + 1; //minCapacity 为 add 之后的长度
    
    //如果需要的长度 大于 数组的长度
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
            
    elementData[size++] = e;
    return true;
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
        
    //对数组长度扩容一倍，并相加，也就是扩大为原来的3倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

public void add(int index, E element) {
    grow(size + 1);
    
    //把 size - index 长度的数据 整体往后移一格（通过复制），腾出 index 这个位置给 element
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
                     
    elementData[index] = element;
    size++;
}

public E get(int index) {
    return (E) elementData[index];
}

ArrayList 和 LinkedList 总结：

LinkedList中插入元素快（二分法遍历），ArrayList插入元素慢（需要复制）。
LinkedList中查找元素慢（二分法遍历），ArrayList查找元素块（直接返回数组 索引下的值）

ArrayList 和 Vector 的区别

Vector 和 ArrayList 大体一样，只不过 Vector 的每个方法都加了 synchronized 关键字，下面是区别：

1. 线程安全性不一样
   ArrayList是非线程安全；
   而Vector是线程安全的，它的函数都是synchronized的，即都是支持同步的。
   ArrayList适用于单线程，Vector适用于多线程。

2. 对序列化支持不同
   ArrayList支持序列化，而Vector不支持；即ArrayList有实现java.io.Serializable接口，而Vector没有实现该接口。

3. 构造函数个数不同
   ArrayList有3个构造函数，而Vector有4个构造函数。Vector除了包括和ArrayList类似的3个构造函数之外，另外的一个构造函数可以指定容量增加系数。

public Vector(int initialCapacity, int capacityIncrement) {
    super();

    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

//看一下 Vector 中对 capacityIncrement  的使用
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    
    //此处和 ArrayList 处理的不一致，ArrayList 是对 oldCapacity 扩大一倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);

    elementData = Arrays.copyOf(elementData, newCapacity);
}