LinkedList源码浅析

前言

LinkedList使用频率相较ArrayList不高，但也值得探讨一下。适合集合高频次修改时采用。

介绍

与ArrayList不同,LinkedList是对List和Deque接口的双向链表实现。实现所有可选的列表操作，并允许所有元素（包括null）。 所有操作的执行都与双链接列表的预期一样。索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引的为准。

请注意，此实现是不同步的。如果多个线程同时访问一个链表，并且至少有一个线程在结构上修改链表，则必须在外部对其进行同步。（结构修改是添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）这通常通过在自然封装列表的某个对象上进行同步来实现。如果不存在此类对象，则应使用Collections.synchronizedList方法“包装”列表。最好在创建时执行此操作，以防止意外不同步地访问列表：

List list = Collections.synchronizedList(new LinkedList(...));

成员变量

transient int size = 0;

/**
 * 指向第一个节点的指针
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 指向加载节点的指针
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

节点

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

数据结构

双向链表，可以从任一节点向前或者向后遍历。不支持随机访问。

push(E e)

/**
 * 将元素推送到此列表表示的堆栈上。换句话说，在列表的前面插入元素。 此方法相当于addFirst。
 */
public void push(E e) {
    addFirst(e);
}

/**
 * 在此列表的开头插入指定的元素。
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

这里其实就是链表的头插法，新建一个节点指向之前的头节点，之前的头节点向前指向新节点。头指针指向新的节点。

pop()

/**
 * 从该列表表示的堆栈中弹出一个元素。换句话说，删除并返回此列表的第一个元素。 此方法等效于removeFirst（）
 */
public E pop() {
    return removeFirst();
}

/**
 * 从此列表中删除并返回第一个元素。
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

和push相反，pop弹出头节点，头指针指向头节点的下一个节点，下一个节点向前指向null

结尾

这里只是把LinkedList的核心数据结构指出，其他方法也都是对于双向链表的常规操作，读者可自行了解。

关于作者

我叫无涯，一位热爱coding的coder。更多文章在我的个人博客：oneyoung.top 。让我们一起进步。