简介

LinkedList 底层是基于双向链表实现的，内部有三个属性：size 用来存储元素个数，first 指向链表头节点，last 指向链表尾节点。

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    // 元素个数
    transient int size = 0;

    // 头节点
    transient Node<E> first;

    // 尾节点
    transient Node<E> last;
}

头尾节点都是由 Node 节点组成，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;
    }
}

类图架构

«interface»

Collection<E>

+add(E e) : boolean

+remove(Object o) : boolean

+contains(Object o) : boolean

+size() : int

+isEmpty() : boolean

«interface»

List<E>

+get(int index) : E

+add(int index, E e) : void

+remove(int index) : E

+indexOf(Object o) : int

«interface»

Deque<E>

+addFirst(E e) : void

+addLast(E e) : void

+removeFirst() : E

+removeLast() : E

+peekFirst() : E

+peekLast() : E

«abstract»

AbstractSequentialList<E>

LinkedList<E>

-transient int size

-transient Node<E> first

-transient Node<E> last

-static class Node

+LinkedList()

+add(E e) : boolean

+add(int index, E e) : void

+get(int index) : E

+remove(int index) : E

+addFirst(E e) : void

+addLast(E e) : void

+removeFirst() : E

+removeLast() : E

-node(int index) : Node

-linkLast(E e) : void

-linkFirst(E e) : void

-unlink(Node x) : E

LinkedList 实现了 List 接口，提供了集合操作的常用方法，当然也包含随机访问的方法，只不过没有像 ArrayList 那样实现 RandomAccess 接口，LinkedList 提供的随机访问方法时间复杂度不是常量级别的。

LinkedList 还实现了 Deque 接口，Deque 是 double ended queue 的缩写，读音是 /dek/，读错就尴尬了。
Deque 是双端队列，可以在头尾进行插入和删除操作，兼具栈和队列的性质。

Deque 提供了大量增删查方法，目的是区分不同语义：对于添加操作，addFirst() 在队列满时会抛出异常，而 offerFirst() 则返回 false；对于删除和查询，以 poll/peek 开头的方法在元素不存在时返回 null，而以 remove/get/element 开头的方法则会抛出异常。

常用方法分类如下：

操作类型	头部操作（抛出异常）	头部操作（返回特殊值）	尾部操作（抛出异常）	尾部操作（返回特殊值）
添加	addFirst(e)、push(e)	offerFirst(e)	addLast(e)、add(e)	offerLast(e)、offer(e)
删除	removeFirst()、remove()、pop()	pollFirst()、poll()	removeLast()	pollLast()
查询	getFirst()、element()	peekFirst()、peek()	getLast()	peekLast()

核心工作原理

add(e) 尾部添加

addFirst(e) 头部添加

add(index,e) 任意位置

是

否

remove 删除

removeFirst

removeLast

remove(index)

remove(Object)

找到

未找到

get(index)

getFirst/getLast

初始化: first=null, last=null, size=0

添加元素?

linkLast: 新节点prev指向原last\nlast更新为新节点\n原last.next指向新节点\nsize++ modCount++

linkFirst: 新节点next指向原first\nfirst更新为新节点\n原first.prev指向新节点\nsize++ modCount++

index == size?

node(index): 按index与size/2比较\n决定从头或尾遍历

linkBefore: 在目标节点前插入新节点\n修改前后节点指针\nsize++ modCount++

按位置还是按值?

unlinkFirst: 断开头节点引用\nitem和next置null\nsize-- modCount++

unlinkLast: 断开尾节点引用\nitem和prev置null\nsize-- modCount++

node(index) 定位节点

unlink: 断开前后节点引用\nitem/prev/next置null\nsize-- modCount++

从头/尾遍历查找equals

返回false

查询元素?

node(index) 定位节点

返回 node.item

直接返回 first.item / last.item

初始化

LinkedList 只有一个构造方法——无参构造，并不能像 ArrayList 那样指定初始容量。

List<Integer> list = new LinkedList<>();

构造方法的底层实现也是一个空方法，没有做任何操作：

public LinkedList() {
}

这意味着 LinkedList 创建时不会预先分配任何节点，所有节点都是在添加元素时才动态创建。

💡 核心提示：LinkedList 的无参构造是真正的"零成本"初始化——它不分配任何内存。这与 ArrayList 不同（ArrayList 无参构造也只是赋值空数组引用，同样零分配）。但 LinkedList 每次 add 都要 new Node()，意味着每次添加都是一次独立的堆分配，在大量元素场景下，这会导致内存碎片化，且每个节点的 GC 追踪开销更大。

添加元素

添加元素的方法根据位置区分，共有三种：在头部添加、在尾部添加、在任意位置添加。

方法含义	不返回值	返回布尔值
在头部添加	addFirst(e)、push(e)	offerFirst(e)
在尾部添加	addLast(e)	add(e)、offer(e)、offerLast(e)
在任意位置添加	add(index, e)	-

先看一下使用最多的 add(e) 方法底层实现：

// 添加元素
public boolean add(E e) {
    // 在末尾添加元素
    linkLast(e);
    return true;
}

// 在末尾添加元素
void linkLast(E e) {
    // 1. 获取尾节点
    final Node<E> l = last;
    // 2. 初始化新节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 3. 追加到末尾
    last = newNode;
    if (l == null) {
        first = newNode;
    } else {
        l.next = newNode;
    }
    size++;
    modCount++;
}

linkLast 的核心逻辑：保存原尾节点 → 创建新节点（前驱指向原尾节点） → 更新 last 指针 → 如果链表为空则同时设置 first → 否则将原尾节点的 next 指向新节点。

再看一个从头部添加元素的 push()：

// 添加元素
public void push(E e) {
    // 在头部添加元素
    addFirst(e);
}

// 在头部添加元素
public void addFirst(E e) {
    linkFirst(e);
}

// 在头部添加元素，底层私有实现
private void linkFirst(E e) {
    // 1. 获取头节点
    final Node<E> f = first;
    // 2. 初始化新节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 3. 追加到头部
    first = newNode;
    if (f == null) {
        last = newNode;
    } else {
        f.prev = newNode;
    }
    size++;
    modCount++;
}

linkFirst 与 linkLast 逻辑对称：保存原头节点 → 创建新节点（后继指向原头节点） → 更新 first 指针 → 如果链表为空则同时设置 last → 否则将原头节点的 prev 指向新节点。

最后看在任意位置添加的 add(index, e) 底层实现：

// 在下标index位置添加元素
public void add(int index, E element) {
    // 检查下标是否越界
    checkPositionIndex(index);

    // 如果index等于链表长度，则添加到末尾
    if (index == size) {
        linkLast(element);
    } else {
        // 添加到指定位置前面（先找到index位置的元素）
        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++;
    modCount++;
}

这里调用了 checkPositionIndex 进行越界检查（允许 index == size，因为可以在末尾追加）：

// 检查位置下标是否越界
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index)) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

// 判断位置下标是否合法
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

add(index, e) 内部还依赖了 node(index) 方法来定位节点，这个方法在查询部分详细分析。

查询元素

查询元素的方法按位置区分，共有三种：查询头节点、查询尾节点、查询任意位置元素。

方法含义	如果不存在则返回null	如果不存在则抛异常
查询头部	peek()、peekFirst()	getFirst()、element()
查询尾部	peekLast()	getLast()
查询任意位置	-	get(index)

看一下从头查询的 element() 方法的底层实现：

// 查询元素
public E element() {
    return getFirst();
}

// 获取第一个元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null) {
        throw new NoSuchElementException();
    }
    return f.item;
}

再看一个查询尾节点的 getLast() 方法的底层实现：

// 获取最后一个元素
public E getLast() {
    final Node<E> l = last;
    if (l == null) {
        throw new NoSuchElementException();
    }
    return l.item;
}

头尾查询都是 O(1) 时间复杂度，因为直接访问 first 和 last 指针。

再看一个查询任意位置的方法 get(index) 的底层实现：