数组链表和List部分理解总结 数组链表区别优缺点

数组访问快的原因：

数组在内存中的空间是连续的，因而可以直接通过数组的首地址 计算出 需要访问的位置，直接拿到元素或对象引用

链表 增删快原因：

这是相较于数组而言的，对于数组而言，元素的新增 删除 可能会伴随后面的元素向前移动的问题，而数组上的位置移动，是需要一个个复制过去。而链表的新增删除，在不考虑元素定位的情况下，只需要修改最多三个节点（包含元素本身）的引用指向而已。

链表随机访问慢的原因：

相较于数组的定位，链表就需要根据需要访问的位置 从前或从后 数元素，直到数到对应的索引为止，也就是数组的是计算而链表的是遍历，所以链表访问慢

数组 浪费内存空间解释：

1.数组需要预先初始化一段连续的内存空间等待使用，而一般情况下数组都不会恰好放满，即有一段内存空间是未使用的，

2.数组的扩容，实际是先申请更大的内存空间，再将现有的元素复制过去，原来的这个就不用了，变成了需要gc的垃圾

数组和链表的遍历

数组和链表的遍历理论上一样快，但实际上数组快

因为CPU处理时，CPU缓存会把一片连续的内存空间读入，如果是数组那就有部分或全部数据都读取到cpu缓存中，供cpu使用，而对于链表， 因为节点都是在堆中分散存在，所以cpu只能读取内存，所以数组的遍历会快

ArrayList

新增时检查扩容流程

1.传入新增后目标长度，

判断当前数组 如果是初始化状态（长度0），则返回默认大小10 和新增后目标长度 较大的那个

否则 返回新增后目标长度

2.上步 返回的长度 和 数组实际长度 比对，不够 则扩容

3.扩容 为 当前容量1.5倍（所以第二部会尽量 做到在没初始化 时 初始化 一个 大一点的，不然 如果从0个 开始 加 容量变化为0->1>2>3>4>6）

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

根据1.5倍得到容量后，会再检查，如果还小于目标容量，则 取目标容量。所以能从0>1>2

SubList

sublist具备list的所有功能，但 谨慎使用，因为操纵sublist时，实际还是操作的list，

List<String> list = new ArrayList<String>(0);
list.add("a");

// 使用构造器创建一个包含list的列表list1
List<String> list1 = new ArrayList<String>(list);
// 使用subList生成与list相同的列表list2
List<String> list2 = list.subList(0, list.size());
list2.add("b");

System.out.println(list.equals(list1));   //false
System.out.println(list.equals(list2));   //true

因为 list和list1比较的时候，list已经变了，因为list2的add操作，实际就是操作的list。

Arraylist的 sublist函数

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

sublist的add函数

public void add(int index, E e) {
    rangeCheckForAdd(index);
    checkForComodification();
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
    this.size++;
}

所以sublist的add就是调用parent.add,而parent实际就是 生成他的Arraylist

LinkedList

基于链表

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

在定位节点时，会根据定位的位置 和 链表大小比对，不过半 则 从头查，过半 从尾部查。

以下为定位位置节点的实现：

   Node<E> node(int index) {
        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;
        }
    }

Vector

Vector和ArrayList一样也是基于数组实现的，自动扩容，部分方法 加了同步锁synchronized。

有意思的点 是其中有种构造方法 可以传入 每次扩容 的大小，默认这个值为0（此时扩容为两倍，当然也有对于扩容后容量和期望容量的比对，防止容量不足的请， 和arraylist一样）

以下为构造函数和扩容函数

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
      //如果设置了capacityIncrement，则每次新增capacityIncrement
      //否则以2倍扩容
        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);
    }