ArrayList and LinkedList

ArrayList读快， LinkedList写快。

Read:

ArrayList维护了index， 所以快. get(int index)的复杂度为O(1)
LinkedList实现了双向链表， 需要遍历 get(int index)的复杂度为O(n)

ArrayList:

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

        return elementData(index);
    }

@SuppressWarnings("unchecked")
    E elementData(int index) {
        //arraylist 的get直接返回数组的index
        return (E) elementData[index];
    }

LinkedList:

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

//需要遍历
Node<E> node(int index) {
        // assert isElementIndex(index);

        // 二分法查找， 小于一半， 则从头查， 反之尾部
        if (index < (size >> 1)) {
            Node<E> x = first;
         //for循环遍历，不能直接取index，因为是链表
            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;
        }
    }

//链表节点
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;
        }
    }

write (add/delete)

ArrayList的write复杂度为O(n) , 主要是移位扩容引起.

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

LinkedList的write复杂度为O(1)

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

直接add一个明确的reference时可以看到LinkedList因为维护了好多辅助元素， 比如双向链表， 以及first last， 所以如果直接add元素的时候， 直接找到last元素插到屁股后面就可以了。

如果add by index的话复杂度就是O(i), 因为需要遍历.

delete操作类似。

arraylist 和 linkedlist共同点

• both implement List interface
• insert后的display order相同
• 非同步安全的， 需要显式调用Collections.synchronizedList
• iterator属于 fail-fast (迭代器创建后有元素被修改会报错)

各自使用场景

arraylist优点是读取快， linkedlist写入快。
所以如果是读多写少(比如缓存)， 用arraylist.
如果是写多读少(比如当作临时的小型DB存储)

关于内存

LinkedList相比ArrayList需要维护更多的内容， 内存会多一些。
对于ArrayList有一个背后默认扩容的检查操作， 如果预先能知道size最好构造函数里指定size， 这样可以减少resize的次数。 arraylist动态扩容其实是怕一开始占用的内存过多。我们知道需要多少就没有这个问题了。