java的ArrayList(线性表)和LinkedList(双向链表)的深入学习

java的ArrayList和LinkedList的实现原理是完全不一样的，一个是用数组，而另一个则是用节点(Node)。

我们经常说，如果查询多，那就用ArrayList，而如果删除或者添加，那就用LinkedList。为什么要这样子，他们两者之间的区别又是怎样的，而今天我们就要从源码来分析他们

①先看看ArrayList和LinkedList他们的结构

ArrayList：一个Object数组

/**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

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

②他们之间获取元素方法之间的不同，我们来看看get方法

ArrayList：

/**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);//检查索引是否越界

        return elementData(index);
    }

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

从这里我们可以看到，ArrayList通过索引即可从数组里面直接获取，时间复杂度为O(1)

LinkedList：

/**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        checkElementIndex(index);//同样也是检查索引是否大于LinkedList的长度
        return node(index).item;
    }

/**
     * Returns the (non-null) Node at the specified element index.
     */
    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;
        }
    }

因为我们知道的元素只有first和last，所以这里只用了一次二分法，如果index小于size/2，那么就first开始查找，一直从0遍历到index。同理如果index大于size/2，那么就last倒过来查找，一直从size-1遍历到index。时间复杂度为O(n/2)

总结：ArrayList比LinkedList的查找效率要高。

②他们之间获取元素方法之间的不同，我们来看看remove方法

ArrayList：

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        rangeCheck(index);//同样检查索引

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

在这里我要说一下System.arraycopy(src, srcPos, dest, destPos, length)，这是一个复制数组的方法，其中：

src：数据源，也就是将要被复制的数组

srcPos：数据源的某个索引，也就是将从数据源那个所以开始复制

dest：目标源，将要复制到的数组

destPos：目标源的某个索引，也是就是复制从目标源的destPos开始

length：复制的长度，也就是将将数据源的srcPos到srcPos+length复制到目标源的destPos到destPos到destPos+length

这么说，我相信大家上面的那段代码能看懂了

由于System.arraycopy的方法是native的，所以就不贴出来给大家看了，但我个人猜想里面肯定少不了遍历，才能将数组复制，所以我这里给它的时间复杂度是O(n)

LinkedList：

/**
     * Removes the element at the specified position in this list.  Shifts any
     * subsequent elements to the left (subtracts one from their indices).
     * Returns the element that was removed from the list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        checkElementIndex(index);//检查索引是否越界
        return unlink(node(index));
    }

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