一起做做JAVA面试题--ArrayList、LinkedLis

ArrayList、LinkedList 和 Vector源码解析

ArrayList查看源码

//初始容量
private static final int DEFAULT_CAPACITY = 10;
//数据存储(不可序列化的数组)
private transient Object[] elementData;
//当前容量
private int size;

ArrayList add()方法

private void grow(int minCapacity) {
        //获取原有数组长度
        int oldCapacity = elementData.length;
        //长度增加1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果长度扩展后小于当前所需容量则取当前所需容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果扩容已至最大Integer.MAX_VALUE - 8则依据当前长度判断取Integer.MAX_VALUE - 8还是取Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //数组复制将数组扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList remove()方法

   public E remove(int index) {
        //校验长度
        rangeCheck(index);
        //AbstractList变量 表示修改次数
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        //数组移动
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

ArrayList get()方法

    public E get(int index) {
        rangeCheck(index);

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

综上得出结论：==ArrayList底层为动态数组，扩容规则为1.5倍。ArrayList可快速的get(i),但是add和remove涉及System.arraycopy()数组复制，性能变差==
LinkedList查看源码

//链表头
transient Node<E> first;
//链表尾
transient Node<E> last;
//链表数据结构
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 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++;
    }

LinkedList remove()方法

//从表头开始遍历，查出数据与删除数据一致的节点
//删除节点 简单理解：将当前节点的上一个节点的下一个节点置成当前节点的下一个节点即可 
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

LinkedList get()方法

//根据下标判断是从链表头还是从链表尾开始查找
    Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

综上得出结论：
==1、add()和remove() LinkedList的只涉及一个节点的操作，比ArrayList的数组移动效率高
2、get()方法ArrayList数组下标获取比LinkedList效率高==

Vector 和ArrayList一致，只不过在方法前加synchronized形成同步线性安全