Java LinkedList的实现原理图文详解

首先，我们来了解一下Java LinkedList的基本特性。LinkedList是Java中实现链表数据结构的一种方式，它实现了List、Deque、Queue接口。LinkedList内部以链表的形式存储元素，每个节点都包含上一个节点的引用和下一个节点的引用。因此可以方便的在链表的任意位置进行添加、删除操作，但是随机访问某个元素的效率会比较低。

LinkedList类主要包含了以下几个成员变量：

transient int size = 0; // 链表大小，该变量用transient修饰，表示不会被进行序列化
transient Node<E> first; // 链表首节点
transient Node<E> last; // 链表尾节点

同时它还包括了一个内部类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;
    }
}

接下来，我们可以看一下LinkedList的一些基本操作的实现过程。

1、添加元素

对于向链表尾部添加元素的操作，我们只需要将新元素添加到链表末尾节点的后面即可。

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

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

对于向链表中间位置添加元素的操作，我们需要将新元素插入到相应位置，并修改相应节点的前后节点的引用。

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size) {
        linkLast(element);
    } else {
        linkBefore(element, node(index));
    }
}

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

2、删除元素

对于删除尾部元素的操作，我们只需要将尾部节点的前一个节点作为新的尾部节点即可。

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null;
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    return element;
}

对于删除中间节点的操作，我们需要找到对应节点，修改上下节点的引用即可。

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

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

通过以上基本操作可以看出，LinkedList主要是以双向链表的形式存储数据，因此可以方便的进行添加、删除等操作。但是由于需要遍历链表才能访问某个元素，因此不适用于随机访问与修改。

示例一：

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);

以上示例添加了1、2、3、4四个元素到链表中。

示例二：

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(1, 5);

以上示例在第二个元素的位置插入了5这个元素。