LinkedList 深度解析：核心原理与实践

LinkedList 深度面试指南：核心原理与实践

一、底层数据结构与特性

1. 核心数据结构

// JDK 17 源码片段
private static class Node<E> {
   
   
    E item;         // 存储的数据元素
    Node<E> next;   // 指向下一个节点
    Node<E> prev;   // 指向前一个节点
}

transient Node<E> first; // 链表头节点
transient Node<E> last;  // 链表尾节点
transient int size = 0;  // 元素数量

2. 关键特性

二、核心操作机制解析

1. 添加元素机制

头部添加：

public void addFirst(E e) {
   
   
    linkFirst(e);
}

// 将元素e作为新的头节点插入到链表的最前面
private void linkFirst(E e) {
   
   
    // 保存当前第一个节点的引用f
    final Node<E> f = first;
    // 创建新节点newNode，其前驱为null，后继指向原第一个节点f
    final Node<E> newNode = new Node<>(null, e, f);
    // 将first指针指向新节点
    first = newNode;
    if (f == null)
        // last也指向新节点
        last = newNode;
    else
        // 否则将原第一个节点的prev指向新节点
        f.prev = newNode;
    // 链表大小加1，修改计数器加1
    size++;
    modCount++;
}

尾部添加：

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

2. 删除元素机制

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

E unlink(Node<E> x) {
   
   
    final E element = x.item