Java LinkedList实现原理

Java LinkedList实现原理，我们先来看LinkedList的内部组成，然后分析它的一些主要方法的实现，代码基于Java 7。

内部组成

我们知道，ArrayList内部是数组，元素在内存是连续存放的，但LinkedList不是。LinkedList直译就是链表，确切地说，它的内部实现是双向链表，每个元素在内存都是单独存放的，元素之间通过链接连在一起，类似于小朋友之间手拉手一样。

为了表示链接关系，需要一个节点的概念。节点包括实际的元素，但同时有两个链接，分别指向前一个节点（前驱）和后一个节点（后继）。节点是一个内部类，具体定义为：

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

Node类表示节点，item指向实际的元素，next指向后一个节点，prev指向前一个节点。

LinkedList内部组成就是如下三个实例变量：

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

我们暂时忽略transient关键字，size表示链表长度，默认为0, first指向头节点，last指向尾节点，初始值都为null。

LinkedList的所有public方法内部操作的都是这三个实例变量，具体是怎么操作的？链接关系是如何维护的？我们看一些主要的方法，先来看add方法。

add方法

add方法的代码为：

public boolean add(E e) {
    linkLast(e);
    return true;
}

主要就是调用了linkLast，它的代码为：

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

代码的基本步骤如下。

1）创建一个新的节点newNode。l和last指向原来的尾节点，如果原来链表为空，则为null。代码为：

Node<E> newNode = new Node<>(l, e, null);

2）修改尾节点last，指向新的最后节点newNode。代码为：

last = newNode;

3）修改前节点的后向链接，如果原来链表为空，则让头节点指向新节点，否则让前一个节点的next指向新节点。代码为：

if(l == null)
    first = newNode;
else
    l.next = newNode;

4）增加链表大小。代码为：

size++

modCount++的目的与ArrayList是一样的，记录修改次数，便于迭代中间检测结构性变化。

我们通过一些图示来进行介绍。比如，代码为：

List<String> list = new LinkedList<String>();
list.add("a");
list.add("b");

执行完第一行后，内部结构如图所示。

添加完“a”后，内部结构如图所示。

添加完“b”后，内部结构如图所示。

可以看出，与ArrayList不同，Linked-List的内存是按需分配的，不需要预先分配多余的内存，添加元素只需分配新元素的空间，然后调节几个链接即可。

根据索引访问元素get

添加了元素，如何根据索引访问元素呢？我们看下get方法的代码：

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

checkElementIndex检查索引位置的有效性，如果无效，则抛出异常，代码为：

private void checkElementIndex(int index) {
    if(! isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

如果index有效，则调用node方法查找对应的节点，其item属性就指向实际元素内容，node方法的代码为：

Node<E> node(int 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;
    }
}

size>>1等于size/2，如果索引位置在前半部分（index<(size>>1)），则从头节点开始查找，否则，从尾节点开始查找。可以看出，与ArrayList明显不同，ArrayList中数组元素连续存放，可以根据索引直接定位，而在LinkedList中，则必须从头或尾顺着链接查找，效率比较低。

根据内容查找元素

我们看下indexOf的代码：

public int indexOf(Object o) {
    int index = 0;
    if(o == null) {
        for(Node<E> x = first; x ! = null; x = x.next) {
            if(x.item == null)
                return index;
            index++;
        }
    } else {
        for(Node<E> x = first; x ! = null; x = x.next) {
            if(o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

代码也很简单，从头节点顺着链接往后找，如果要找的是null，则找第一个item为null的节点，否则使用equals方法进行比较。

插入元素

add是在尾部添加元素，如果在头部或中间插入元素呢？可以使用如下方法：

public void add(int index, E element)

它的代码是：

public void add(int index, E element) {
    checkPositionIndex(index);
    if(index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

如果index为size，添加到最后面，一般情况，是插入到index对应节点的前面，调用方法为linkBefore，它的代码为：

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if(pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

参数succ表示后继节点，变量pred表示前驱节点，目标是在pred和succ中间插入一个节点。插入步骤是：
1）新建一个节点newNode，前驱为pred，后继为succ。代码为：

Node<E> newNode = new Node<>(pred, e, succ);

2）让后继的前驱指向新节点。代码为：

succ.prev = newNode;

3）让前驱的后继指向新节点，如果前驱为空，那么修改头节点指向新节点。代码为：

if (pred == null)
    first = newNode;
else
    pred.next = newNode;

4）增加长度。
我们通过图示来进行介绍。还是上面的例子，比如，添加一个元素：

list.add(1, "c");

内存结构如图所示。

可以看出，在中间插入元素，LinkedList只需按需分配内存，修改前驱和后继节点的链接，而ArrayList则可能需要分配很多额外空间，且移动所有后续元素。

删除元素

我们再来看删除元素，代码为：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

通过node方法找到节点后，调用了unlink方法，代码为：

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

删除x节点，基本思路就是让x的前驱和后继直接链接起来，next是x的后继，prev是x的前驱，具体分为两步。
1）让x的前驱的后继指向x的后继。如果x没有前驱，说明删除的是头节点，则修改头节点指向x的后继。
2）让x的后继的前驱指向x的前驱。如果x没有后继，说明删除的是尾节点，则修改尾节点指向x的前驱。

通过图示进行说明。还是上面的例子，如果删除一个元素：

list.remove(1);

内存结构如图所示。

酷客教程相关文章：

• Java LinkedList
• Java ArrayList迭代
• Java ArrayList
• Java 泛型与数组