四十、List集合

1. List是collection接口的子类
2. List有三个实现类 ArrayList、LinkedList、Vector
3. 三个实现类相同点
   1. 都是存储有序的 可重复的数据
4. 三个实现类不同点
   1. ArrayList 效率高 是线程不安全的 底层使用Object[]存储
   2. LinkedList 对于需要频繁插入、删除操作 使用LinkedList效率比ArrayList效率高; 底层使用双向链表存储
   3. Vertor 是List接口的古老实现类 线程安全的 效率低 底层使用Object[]存储
5. ArrayList 有序的 可重复

一、ArrayList源码分析

1. 默认构造器

   // 创建一个默认大小的空参数组实例
   public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2. 底层存储数据的成员变量

   // 存储ArrayList元素的缓冲区域 当添加第一个元素时elementData将扩容为
   // private static final int DEFAULT_CAPACITY = 10 
   transient Object[] elementData

3. 添加以及扩容

   // 进入添加方法
   public void add(int index, E element) {
        rangeCheckForAdd(index);
        // 进入判断当前容量是否超出
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

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

   二、LinkedList源码分析 双向链表存储

4. 底层每个元素都是Node

5. Node元素记录自己上一个元素 元素本身 自己下一个元素

6. 删除或添加操作时 修改元素记录的上一个元素或下一个元素记录

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

    // 形参为要删除的数据
    E unlink(Node<E> x) {
        // 记录要删除的数据本身
        final E element = x.item;
        // 获取要删除的数据下一个数据
        final Node<E> next = x.next;
        // 获取要删除的数据上一个数据
        final Node<E> prev = x.prev;
        // 如果删除的元素上一个元素为空
        if (prev == null) {
            // first指向第一个节点的指针 null
            first = next;
        } else {
            //被删除元素的上一个元素中的下一个元素指向被删除元素的下一个元素
            prev.next = next;
            // 被删除元素的上一个记录设置为null
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }