链表

一、链表基础概念

链表是一种非连续、非顺序的线性数据结构，由一系列节点组成，每个节点包含数据域和指针域，通过指针实现节点间的逻辑关联。

核心节点结构

// 单向链表节点
private static class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

// 双向链表节点
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;
    }
}

---

二、单向链表

1. 结构特点

• 每个节点仅包含数据域和一个后继指针 next，指向后一个节点
• 尾节点的 next 为 null，无向前遍历能力
• 物理存储不连续，无需预分配固定大小的内存空间

2. 时间复杂度分析

操作类型	场景	时间复杂度
查询	查询头节点	O(1)
查询	查询其他节点	O(n)（需遍历链表）
插入/删除	操作头节点	O(1)
插入/删除	操作其他节点	O(n)（需遍历找到目标节点）

---

三、双向链表

1. 结构特点

• 每个节点包含数据域、后继指针 next 和前驱指针 prev
• 支持双向遍历，给定节点可直接访问其前驱和后继节点
• 头尾节点的 prev 和 next 分别为 null，通常维护 first 和 last 指针快速访问首尾

2. 时间复杂度分析

操作类型	场景	时间复杂度
查询	查询头/尾节点	O(1)
查询	平均查询	O(n)
查询	给定节点找前驱节点	O(1)
插入/删除	操作头/尾节点	O(1)
插入/删除	给定节点增删	O(1)
插入/删除	其他节点增删	O(n)（需遍历定位）

---

四、单向链表 vs 双向链表

特性	单向链表	双向链表
节点结构	仅含 next 指针	含 prev 和 next 双指针
遍历方向	仅支持从前向后遍历	支持双向遍历
前驱节点访问	需遍历链表，O(n)	直接访问，O(1)
内存开销	每个节点仅需一个指针空间	每个节点需两个指针空间，开销更大
增删操作	已知前驱节点时O(1)，否则O(n)	已知节点时O(1)，效率更高

---

五、面试高频问题解析

1. 问：单向链表和双向链表的核心区别是什么？答： 核心区别在于节点结构和遍历能力。单向链表每个节点仅含后继指针，只能从前向后遍历，访问前驱节点需遍历链表；双向链表每个节点同时含前驱和后继指针，支持双向遍历，访问前驱节点为O(1)，但内存开销更大。

2. 问：双向链表的增删操作效率一定比单向链表高吗？答： 不一定。增删操作的效率取决于是否能快速定位节点：若已知目标节点，双向链表的增删操作（修改前后节点指针）为O(1)，效率高于单向链表；若需遍历定位节点，两者时间复杂度均为O(n)，差异不大。

3. 问：为什么LinkedList采用双向链表实现？答： 双向链表支持快速访问首尾节点和前驱节点，增删操作更灵活，适合频繁在首尾或已知节点附近增删元素的场景；同时双向遍历能力也提升了迭代效率，符合LinkedList作为通用序列容器的设计目标。

4. 问：链表和数组相比，有哪些优缺点？答：

   • 优点：内存无需连续，动态扩容无需拷贝数据，增删操作（已知节点）效率高（O(1)）
   • 缺点：随机访问效率低（O(n)），需遍历查找；每个节点额外存储指针，内存开销大；无法利用缓存局部性原理，访问性能差