浅析LinkedList

写在前面

本文所看的源码是在idea里面查看的，一些代码和Java的源码可能有所不同……但是思想应该是一致的。
上一篇浅析ArrayList简要的了解了一下ArrayList是如何实现的，ArrayList内部是用一个Object数组对象来作为容器盛放各个对象的。而LinkedList则不然，其内部实现就类似于数据结构中的双向链表。只不过在Java中可能你不能直接使用“指针”，所以得通过Java的“引用”来实现这个双向链表。那么今天也让我们通过几个比较经典的方法来看一下其内部实现。

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

很经典的一个数据结构……（笑）

考虑到了代码的兼容性加入了泛型，这些都是可以暂时不看的，对我们了解其实现没什么大的影响。

这个类内部一个next一个prev分别代表了当前节点的前驱和后继，大白话就是这节点的前一个元素和后一个元素，item是保存的值。

add()

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

向链表的尾部插入一个值，那么继续看看linkLast(e)是怎么实现的

/**
 * Links e as last element.
 */
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内部有一个指向尾部的引用，所以插入尾部实现起来十分简单。先将尾节点引用指向新节点，之后判断一下头节点是否为空，如果是空的话，那么说明这个链表还没有节点，那么将第一个节点的引用指向这个节点，如果非空的话就将新的节点插入到最后一个节点的后面。

get()

/**
 * 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);
    return node(index).item;
}

这个方法会返回一个特定位置的node所存储的值。代码很少一共就两行，先看第一行的代码是个啥：

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * Tells if the argument is the index of an existing element.
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

通过两个方法我们可以看出这个方法会检查你所给的index是否在这个链表内，如果不是会抛出索引越界的异常。

接下来看看第二行代码是如何实现的：

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

可以看出这个方法还是对这个索引进行了简单的计算，如果这个索引大于链表的尺寸的一半那么他会从尾部开始遍历直到找到这个index对应的node。反之他会从这个链表的头部开始遍历。毕竟双向链表，从哪都行~