一句话定位

LinkedList 是 Java 中基于「双向链表」实现的 List 接口实现类，专为高频插入/删除设计，牺牲随机访问性能，换取极致的结构性修改效率。

---

🔹 底层原理（一句话说清）

• 每个元素封装为一个 Node 节点，含：
  ✅ item（当前数据）
  ✅ next（指向后继节点）
  ✅ prev（指向前驱节点）
• 维护 first（头节点）和 last（尾节点）两个引用 → 头尾操作均为 O(1)
• ❌ 无数组、无容量、无扩容机制 → 插入多少，就新建多少节点，零拷贝、零移动、零浪费

---

✅ 为什么适合「频繁插入/删除」？

场景	原因	示例
头/尾增删	直接修改 first/last 引用 + 断开/链接节点	addFirst(), removeLast() → 稳定 O(1)
中间插入（如 add(5, e)）	不需移动其他元素，只需修改前后节点的 next/prev 指针	对比 ArrayList：无需 System.arraycopy 挪动几十/几百个元素
大量连续插入	每次只分配一个 Node 对象，无扩容抖动	电商秒杀中批量入队订单 ID，毫秒级无压力

💡 本质优势：链表的“结构性修改”与数据规模无关，只与操作位置相关。

---

❌ 为什么怕「随机访问」？

操作	问题	性能
get(10) / get(1000)	必须从 first 或 last 出发遍历查找（JDK 优化：自动选近端）	O(n) —— 平均需遍历 n/4 个节点
set(50, e)	先 get(50) 找节点，再改 item	同样 O(n)
对比 ArrayList	ArrayList.get(i) = 内存地址计算（base + i * 8），CPU 缓存友好	O(1)，快上百倍

⚠️ 面试高频陷阱：别再说“LinkedList 查找慢是因为要遍历”，要强调 “没有索引寻址能力，必须线性扫描”。

ArrayList vs LinkedList —— 场景决策树（实用版）

你的需求	推荐选择	原因
✅ 主要遍历 / 随机读取（如 for (int i=0; i<list.size(); i++) list.get(i)）	ArrayList	连续内存 + O(1) 访问 + CPU 缓存命中率高
✅ 高频头/尾插入删除（如消息队列、栈、LRU 缓存）	LinkedList	天然支持 addFirst/removeLast 等 O(1) 操作
✅ 需要当作 Queue（队列）或 Deque（双端队列） 使用	LinkedList（实现 Queue & Deque 接口）	offer()/poll()/peek()、push()/pop() 全部原生支持
✅ 数据量大 + 内存敏感（如百万级日志缓存）	ArrayList	内存占用 ≈ n × 4/8 字节；LinkedList ≈ n × (8+8+16) = n×32 字节（对象头+2引用+数据）
✅ 多线程读写	都不行！ → 改用 CopyOnWriteArrayList（读多写少）或 ConcurrentLinkedQueue（高并发队列）	二者均非线程安全，modCount 机制仅防 fail-fast，不保并发正确性

---

💡 面试加分点（可直接背诵）

“LinkedList 的本质价值不在 List 接口，而在于它同时实现了 Deque 接口——它是 JDK 中唯一一个既支持 List 语义、又原生支持双端队列操作的标准集合。所以与其说它是‘链表版 List’，不如说它是‘带 List 接口的高性能 Deque’。”

add()方法的源码

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

add(index, element)方法的源码

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

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

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

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        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++;
    }

addFirst()方法的源码

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

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

addLast()方法的源码

    public void addLast(E e) {
        linkLast(e);
    }

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

LinkedList可以作为一个队列来使用

offer() == add()，就是在队列尾部入队，将一个元素插入队列尾部，offerFirst()，offerLast()

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

poll()，从队列头部出队

    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(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;
    }

peek()，获取队列头部的元素，但是头部的元素不出队

    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

“已按 JDK 官方指南，全面使用 ArrayDeque 替代 Stack 和 Vector 的栈操作，兼顾高性能、可维护性与技术前瞻性。”