链表：从底层逻辑到实战应用，彻底搞懂线性结构的灵魂！

果酱带你啃java

发布于 2026-04-14 13:43:47

420

在数据结构的世界里，线性结构是最基础也最常用的一类，而链表作为线性结构的核心代表，以其灵活的内存管理特性，成为了程序员必须吃透的知识点。无论是面试中的算法题，还是实际开发中的性能优化，链表的理解深度都直接决定了解决方案的优劣。本文将从底层逻辑入手，结合实战案例，把链表的原理、操作、应用讲透，让你不仅 “会用”，更能 “懂原理”。

一、线性结构的双雄：链表与数组的本质区别

线性结构的定义是 “数据元素之间存在一对一的线性关系”，最典型的就是数组和链表。要理解链表，首先要搞清楚它和数组的核心差异 —— 这一切都源于内存存储方式的不同。

1. 数组：连续内存的 “整块地”

数组要求在内存中占据连续的存储空间，就像一排紧密相连的储物柜。比如一个int[] arr = {1,2,3}，在内存中会占用 3 个连续的int大小的空间（假设每个int占 4 字节，总占用 12 字节）。

这种存储方式的优点是随机访问效率极高（通过下标arr[i]可以直接计算内存地址），但缺点也很致命：

插入 / 删除元素时需要移动后续元素（比如在数组中间插入一个元素，后面的元素都要后移）；
初始化时必须指定大小，扩容需要重新分配内存并复制数据（比如 Java 的 ArrayList 扩容时会新建数组，复制原数据）。

2. 链表：离散内存的 “珍珠项链”

链表则完全不同 —— 它的每个元素（节点）分散在内存的不同位置，通过指针（或引用） 连接成链，就像用线串起的珍珠。每个节点包含两部分：

数据域：存储实际数据；
指针域：存储下一个（或上一个）节点的内存地址。

这种存储方式的优点是：

插入 / 删除元素只需修改指针指向，无需移动其他元素；
无需预先分配内存，大小可以动态调整。

缺点是随机访问效率低（要访问第i个元素，必须从头节点遍历到目标节点）。

权威依据：《数据结构与算法分析：Java 语言描述》（Mark Allen Weiss）中明确指出：“链表的主要优势在于插入和删除操作的效率，而数组的优势在于随机访问。”

二、链表的分类与结构解析

根据指针域的数量和连接方式，链表主要分为单链表、双向链表和循环链表三类。

1. 单链表：最简单的 “单向通道”

结构定义

单链表的每个节点只有一个指针域（next），指向后继节点；尾节点的next指向null；通常会设置一个头节点（哨兵节点）（不存储实际数据），方便操作。

结构流程图：

核心操作（附 Java 实现）

我们基于 JDK 17 实现一个规范的单链表：

（1）Maven 依赖配置

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.example</groupId>
    <artifactId>linkedlist-demo</artifactId>
    <version>1.0-SNAPSHOT</version>
    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
        <lombok.version>1.18.30</lombok.version>
        <spring-context.version>6.1.10</spring-context.version>
        <guava.version>33.2.1-jre</guava.version>
    </properties>
    <dependencies>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>${lombok.version}</version>
            <scope>provided</scope>
        </dependency>
        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-context</artifactId>
            <version>${spring-context.version}</version>
        </dependency>
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>${guava.version}</version>
        </dependency>
    </dependencies>
</project>

（2）单链表实现类

package com.example.linkedlist;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;

/**
 * 单链表实现类
 * 作者：ken
 */
@Slf4j
public class SingleLinkedList<T> {

    /**
     * 链表节点内部类
     */
    private static class Node<T> {
        T data;
        Node<T> next;

        /**
         * 节点构造方法
         * @param data 节点数据
         */
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    // 头节点（哨兵节点，不存储实际数据）
    private final Node<T> head;
    // 链表长度
    private int size;

    /**
     * 单链表初始化
     */
    public SingleLinkedList() {
        this.head = new Node<>(null);
        this.size = 0;
    }

    /**
     * 获取链表长度
     * @return 链表元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 判断链表是否为空
     * @return 空返回true，否则false
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 头插法：在链表头部插入元素
     * @param data 要插入的数据
     */
    public void addFirst(T data) {
        if (ObjectUtils.isEmpty(data)) {
            log.warn("插入数据不能为空");
            return;
        }
        Node<T> newNode = new Node<>(data);
        newNode.next = head.next;
        head.next = newNode;
        size++;
        log.info("头插元素{}成功，当前链表长度：{}", data, size);
    }

    /**
     * 尾插法：在链表尾部插入元素
     * @param data 要插入的数据
     */
    public void addLast(T data) {
        if (ObjectUtils.isEmpty(data)) {
            log.warn("插入数据不能为空");
            return;
        }
        Node<T> newNode = new Node<>(data);
        Node<T> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        size++;
        log.info("尾插元素{}成功，当前链表长度：{}", data, size);
    }

    /**
     * 指定位置插入元素（索引从0开始）
     * @param index 插入位置
     * @param data 要插入的数据
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    public void add(int index, T data) {
        if (ObjectUtils.isEmpty(data)) {
            log.warn("插入数据不能为空");
            return;
        }
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("索引越界：index=" + index + "，size=" + size);
        }
        Node<T> prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<T> newNode = new Node<>(data);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
        log.info("在索引{}插入元素{}成功，当前链表长度：{}", index, data, size);
    }

    /**
     * 根据索引获取元素
     * @param index 索引位置
     * @return 对应位置的元素
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界：index=" + index + "，size=" + size);
        }
        Node<T> current = head.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    /**
     * 删除指定索引的元素
     * @param index 索引位置
     * @return 删除的元素
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界：index=" + index + "，size=" + size);
        }
        Node<T> prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<T> toRemove = prev.next;
        prev.next = toRemove.next;
        size--;
        log.info("删除索引{}的元素{}成功，当前链表长度：{}", index, toRemove.data, size);
        return toRemove.data;
    }

    /**
     * 遍历链表并输出元素
     */
    public void traverse() {
        if (isEmpty()) {
            log.info("链表为空");
            return;
        }
        StringBuilder sb = new StringBuilder();
        Node<T> current = head.next;
        while (current != null) {
            sb.append(current.data).append(" -> ");
            current = current.next;
        }
        sb.delete(sb.length() - 4, sb.length());
        log.info("链表元素：{}", sb);
    }

    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.traverse(); // 1 -> 2 -> 3
        
        list.addFirst(0);
        list.traverse(); // 0 -> 1 -> 2 -> 3
        
        list.add(2, 100);
        list.traverse(); // 0 -> 1 -> 100 -> 2 -> 3
        
        System.out.println("索引2的元素：" + list.get(2)); // 100
        
        list.remove(1);
        list.traverse(); // 0 -> 100 -> 2 -> 3
    }
}

单链表操作的底层逻辑

头插：新节点的next指向原头节点的后继，头节点的next指向新节点（时间复杂度 O (1)）；
尾插：必须遍历到尾节点，再修改尾节点的next（时间复杂度 O (n)）；
中间插入 / 删除：关键是找到前驱节点，修改其next指向（时间复杂度 O (n)，因为要遍历找前驱）。

2. 双向链表：可进可退的 “双向通道”

单链表的缺点是无法反向遍历，删除节点时需要额外找前驱。双向链表解决了这个问题 —— 每个节点有两个指针：prev（前驱）和next（后继）。

结构定义

双向链表通常设置头哨兵和尾哨兵节点，首尾相连更方便操作。

结构流程图：

核心操作实现

package com.example.linkedlist;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;

/**
 * 双向链表实现类
 * 作者：ken
 */
@Slf4j
public class DoublyLinkedList<T> {

    private static class Node<T> {
        T data;
        Node<T> prev;
        Node<T> next;

        Node(T data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private final Node<T> head;
    private final Node<T> tail;
    private int size;

    public DoublyLinkedList() {
        this.head = new Node<>(null);
        this.tail = new Node<>(null);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }

    /**
     * 尾插法（优化：直接通过tail.prev找到尾节点，无需遍历）
     */
    public void addLast(T data) {
        if (ObjectUtils.isEmpty(data)) {
            log.warn("插入数据不能为空");
            return;
        }
        Node<T> newNode = new Node<>(data);
        Node<T> lastNode = tail.prev;
        
        lastNode.next = newNode;
        newNode.prev = lastNode;
        newNode.next = tail;
        tail.prev = newNode;
        
        size++;
        log.info("尾插元素{}成功，当前长度：{}", data, size);
    }

    /**
     * 删除指定节点（双向链表优势：无需找前驱）
     */
    public T remove(Node<T> node) {
        if (ObjectUtils.isEmpty(node) || node == head || node == tail) {
            throw new IllegalArgumentException("无效节点");
        }
        Node<T> prev = node.prev;
        Node<T> next = node.next;
        
        prev.next = next;
        next.prev = prev;
        
        node.prev = null;
        node.next = null;
        size--;
        return node.data;
    }

    /**
     * 反向遍历（双向链表特有）
     */
    public void reverseTraverse() {
        if (isEmpty()) {
            log.info("链表为空");
            return;
        }
        StringBuilder sb = new StringBuilder();
        Node<T> current = tail.prev;
        while (current != head) {
            sb.append(current.data).append(" <-> ");
            current = current.prev;
        }
        sb.delete(sb.length() - 5, sb.length());
        log.info("反向遍历元素：{}", sb);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();
        list.addLast("A");
        list.addLast("B");
        list.addLast("C");
        list.reverseTraverse(); // C <-> B <-> A
    }
}

双向链表的优势

删除操作更高效：已知节点时，无需遍历找前驱（时间复杂度 O (1)）；
支持双向遍历：适合需要反向访问的场景（如 LRU 缓存）。

3. 循环链表：首尾相连的 “环形通道”

循环链表是单链表或双向链表的变种 —— 尾节点的next指向头节点（单循环链表），或头节点的prev指向尾节点（双向循环链表）。

结构定义（单循环链表）

典型应用：约瑟夫环问题

约瑟夫环问题描述：n个人围成一圈，从第一个人开始报数，报到m的人出列，接着从下一个人继续报数，直到最后一个人。用循环链表可以直观解决：

package com.example.linkedlist;

import lombok.extern.slf4j.Slf4j;

/**
 * 约瑟夫环问题（单循环链表实现）
 * 作者：ken
 */
@Slf4j
public class JosephusProblem {

    private static class Node {
        int num;
        Node next;

        Node(int num) {
            this.num = num;
        }
    }

    /**
     * 解决约瑟夫环问题
     * @param n 总人数
     * @param m 报数阈值
     * @return 最后存活的人的编号
     */
    public static int solve(int n, int m) {
        if (n <= 0 || m <= 0) {
            throw new IllegalArgumentException("参数必须大于0");
        }
        // 构建循环链表
        Node head = new Node(1);
        Node current = head;
        for (int i = 2; i <= n; i++) {
            current.next = new Node(i);
            current = current.next;
        }
        current.next = head; // 首尾相连
        
        // 开始报数
        Node prev = current; // 前驱节点（初始为尾节点）
        current = head; // 当前节点（初始为头节点）
        while (current.next != current) { // 只剩一个节点时停止
            // 报数m次
            for (int i = 1; i < m; i++) {
                prev = current;
                current = current.next;
            }
            log.info("出列：{}", current.num);
            prev.next = current.next; // 删除当前节点
            current = prev.next; // 下一个节点开始报数
        }
        return current.num;
    }

    public static void main(String[] args) {
        int survivor = solve(5, 3); // 5人，报数3出列
        log.info("最后存活的人：{}", survivor); // 结果：4
    }
}

三、链表的经典算法题与实战技巧

链表是算法面试的 “常客”，掌握以下经典题的解法，能帮你应对 80% 的链表面试题。

1. 反转单链表（迭代 + 递归）

反转链表是最基础的链表算法题，有两种核心解法：

（1）迭代法（空间复杂度 O (1)）

package com.example.linkedlist.algorithm;

import com.example.linkedlist.SingleLinkedList;
import lombok.extern.slf4j.Slf4j;

/**
 * 单链表反转工具类
 * 作者：ken
 */
@Slf4j
public class LinkedListReverser {

    /**
     * 迭代法反转单链表
     * @param head 原链表的头节点（哨兵的next）
     * @return 反转后的头节点
     */
    public static <T> SingleLinkedList.Node<T> reverseIteratively(SingleLinkedList.Node<T> head) {
        SingleLinkedList.Node<T> prev = null;
        SingleLinkedList.Node<T> current = head;
        while (current != null) {
            SingleLinkedList.Node<T> nextTemp = current.next; // 保存后继
            current.next = prev; // 反转指针
            prev = current; // 移动prev
            current = nextTemp; // 移动current
        }
        return prev;
    }

    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.traverse(); // 1 -> 2 -> 3
        
        list.head.next = reverseIteratively(list.head.next);
        list.traverse(); // 3 -> 2 -> 1
    }
}

（2）递归法（空间复杂度 O (n)）

/**
 * 递归法反转单链表
 */
public static <T> SingleLinkedList.Node<T> reverseRecursively(SingleLinkedList.Node<T> head) {
    if (head == null || head.next == null) {
        return head; // 基准情况：空链表或单节点
    }
    SingleLinkedList.Node<T> newHead = reverseRecursively(head.next); // 反转剩余部分
    head.next.next = head; // 反转当前节点与后继的指针
    head.next = null; // 避免环
    return newHead;
}

2. 环形链表检测（Floyd 判圈算法）

如何判断一个单链表是否有环？最经典的解法是快慢指针法（也叫龟兔赛跑算法）：

package com.example.linkedlist.algorithm;

import com.example.linkedlist.SingleLinkedList;
import lombok.extern.slf4j.Slf4j;

/**
 * 环形链表检测工具类
 * 作者：ken
 */
@Slf4j
public class CycleDetector {

    /**
     * 检测链表是否有环
     * @param head 链表头节点
     * @return 有环返回true
     */
    public static <T> boolean hasCycle(SingleLinkedList.Node<T> head) {
        if (head == null || head.next == null) {
            return false;
        }
        SingleLinkedList.Node<T> slow = head; // 慢指针（一步）
        SingleLinkedList.Node<T> fast = head.next; // 快指针（两步）
        
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false; // 快指针到尾，无环
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true; // 相遇则有环
    }

    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        
        // 构建环：3的next指向2
        SingleLinkedList.Node<Integer> node3 = list.head.next.next.next;
        SingleLinkedList.Node<Integer> node2 = list.head.next.next;
        node3.next = node2;
        
        log.info("链表是否有环：{}", hasCycle(list.head.next)); // true
    }
}

权威依据：Floyd 判圈算法由 Robert W. Floyd 于 1967 年提出，时间复杂度 O (n)，空间复杂度 O (1)，是检测链表环的最优解法。

四、链表的实际应用场景

链表不仅是算法题的 “玩具”，在实际开发中也有广泛应用：

1. Java 集合中的 LinkedList

JDK 17 的LinkedList底层是双向链表（非循环），核心特性：

实现了List和Deque接口，支持队列 / 双端队列操作；
插入 / 删除效率高（已知节点时 O (1)），随机访问效率低（O (n)）。

查看 JDK 源码（java.util.LinkedList）：

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

// 尾插法实现
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. LRU 缓存实现

LRU（Least Recently Used）缓存的核心是 “淘汰最近最少使用的元素”，双向链表 + 哈希表是最优实现方案：

双向链表维护访问顺序（头节点：最近使用，尾节点：最少使用）；
哈希表（HashMap）记录 key 到节点的映射，支持 O (1) 时间复杂度查找。

完整实现：

package com.example.cache;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存实现（双向链表+哈希表）
 * 核心特性：最近使用的元素移至头部，容量满时淘汰尾部元素
 * 时间复杂度：get/put 均为 O(1)
 * 作者：ken
 */
@Slf4j
public class LRUCache<K, V> {

    /**
     * 缓存节点内部类（双向链表节点）
     */
    private static class CacheNode<K, V> {
        K key;
        V value;
        CacheNode<K, V> prev;
        CacheNode<K, V> next;

        /**
         * 节点构造方法
         * @param key 缓存键
         * @param value 缓存值
         */
        CacheNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity; // 缓存最大容量
    private final Map<K, CacheNode<K, V>> cacheMap; // 哈希表：key -> 节点映射
    private final CacheNode<K, V> head; // 头哨兵节点（最近使用）
    private final CacheNode<K, V> tail; // 尾哨兵节点（最少使用）

    /**
     * 初始化LRU缓存
     * @param capacity 缓存容量（必须大于0）
     * @throws IllegalArgumentException 容量非法时抛出
     */
    public LRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("缓存容量必须大于0，当前输入：" + capacity);
        }
        this.capacity = capacity;
        this.cacheMap = new HashMap<>(capacity); // 初始容量与缓存容量一致，减少扩容
        this.head = new CacheNode<>(null, null);
        this.tail = new CacheNode<>(null, null);
        head.next = tail; // 初始化链表：头 -> 尾
        tail.prev = head;
    }

    /**
     * 获取缓存值（访问后将节点移至头部）
     * @param key 缓存键
     * @return 缓存值（不存在返回null）
     */
    public V get(K key) {
        if (ObjectUtils.isEmpty(key)) {
            log.warn("获取缓存失败：key不能为空");
            return null;
        }
        CacheNode<K, V> node = cacheMap.get(key);
        if (ObjectUtils.isEmpty(node)) {
            log.info("缓存未命中：key={}", key);
            return null;
        }
        // 访问的节点移至头部（标记为最近使用）
        moveToHead(node);
        log.info("缓存命中：key={}, value={}", key, node.value);
        return node.value;
    }

    /**
     * 存入缓存（满容量时淘汰最少使用的尾节点）
     * @param key 缓存键
     * @param value 缓存值
     */
    public void put(K key, V value) {
        if (ObjectUtils.isEmpty(key) || ObjectUtils.isEmpty(value)) {
            log.warn("存入缓存失败：key或value不能为空");
            return;
        }
        CacheNode<K, V> node = cacheMap.get(key);
        if (!ObjectUtils.isEmpty(node)) {
            // 已存在：更新值并移至头部
            node.value = value;
            moveToHead(node);
            log.info("更新缓存：key={}, new value={}", key, value);
            return;
        }
        // 容量满：淘汰尾节点（最少使用）
        if (cacheMap.size() >= capacity) {
            CacheNode<K, V> removedNode = removeTail();
            cacheMap.remove(removedNode.key);
            log.info("缓存满，淘汰最少使用节点：key={}", removedNode.key);
        }
        // 新增节点：插入头部并加入哈希表
        CacheNode<K, V> newNode = new CacheNode<>(key, value);
        addToHead(newNode);
        cacheMap.put(key, newNode);
        log.info("新增缓存：key={}, value={}", key, value);
    }

    /**
     * 将节点移至头部（最近使用）
     * @param node 目标节点
     */
    private void moveToHead(CacheNode<K, V> node) {
        removeNode(node); // 先从原位置移除
        addToHead(node); // 再插入头部
    }

    /**
     * 将节点插入头部
     * @param node 目标节点
     */
    private void addToHead(CacheNode<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 从链表中移除指定节点
     * @param node 目标节点
     */
    private void removeNode(CacheNode<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // 断开节点引用，避免内存泄漏
        node.prev = null;
        node.next = null;
    }

    /**
     * 移除尾节点（最少使用）
     * @return 被移除的尾节点
     */
    private CacheNode<K, V> removeTail() {
        CacheNode<K, V> tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }

    /**
     * 打印缓存链表（从头部到尾部，反映访问优先级）
     */
    public void printCache() {
        if (cacheMap.isEmpty()) {
            log.info("缓存为空");
            return;
        }
        StringBuilder sb = new StringBuilder("缓存顺序（最近使用→最少使用）：");
        CacheNode<K, V> current = head.next;
        while (current != tail) {
            sb.append(current.key).append("=").append(current.value).append(" → ");
            current = current.next;
        }
        sb.delete(sb.length() - 4, sb.length());
        log.info(sb.toString());
    }

    public static void main(String[] args) {
        // 初始化容量为3的LRU缓存
        LRUCache<String, Integer> lruCache = new LRUCache<>(3);
        
        lruCache.put("a", 1);
        lruCache.put("b", 2);
        lruCache.put("c", 3);
        lruCache.printCache(); // 输出：a=1 → b=2 → c=3（初始顺序）
        
        lruCache.get("a"); // 访问a，移至头部
        lruCache.printCache(); // 输出：a=1 → c=3 → b=2（a变为最近使用）
        
        lruCache.put("d", 4); // 容量满，淘汰最少使用的b
        lruCache.printCache(); // 输出：d=4 → a=1 → c=3
        
        lruCache.put("c", 33); // 更新c的值
        lruCache.printCache(); // 输出：c=33 → d=4 → a=1（c移至头部）
    }
}

LRU 缓存的底层逻辑解析

数据结构协同：双向链表负责维护访问顺序，哈希表负责快速查找，两者结合实现 O (1) 操作效率；
核心操作原理：
- 新增 / 更新：节点插入头部（最近使用），哈希表同步映射；
- 访问：节点移至头部，维持优先级；
- 淘汰：移除尾节点（最少使用），哈希表同步删除；
哨兵节点的作用：避免头 / 尾节点为空判断，简化链表操作逻辑（符合《阿里巴巴 Java 开发手册》中 “避免空指针” 的规范）。

五、链表在数据库中的应用：InnoDB 链表结构

链表不仅在内存中广泛使用，在数据库底层也有重要应用。以 MySQL 8.0 的 InnoDB 存储引擎为例，其核心数据结构就大量依赖链表：

1. 聚簇索引的双向链表组织

InnoDB 的聚簇索引（主键索引）叶子节点存储完整数据行，且叶子节点之间通过双向链表连接：

按主键顺序排序，支持范围查询（如 WHERE id BETWEEN 100 AND 200）；
双向链表的前驱 / 后继指针指向相邻主键的叶子节点，遍历效率高。

结构流程图：

2. 事务隔离的 undo 日志链表

InnoDB 的 undo 日志用于事务回滚和 MVCC（多版本并发控制），undo 日志以链表形式组织：

每个事务产生的 undo 日志记录通过指针连接，形成 undo 链表；
事务提交后，undo 日志不会立即删除，而是放入链表等待 purge 线程清理。

3. 实战验证：InnoDB 链表结构的影响

创建测试表并验证范围查询的高效性（MySQL 8.0 环境）：

sql

-- 创建聚簇索引表（主键为聚簇索引）
CREATE TABLE `user` (
  `id` bigint NOT NULL AUTO_INCREMENT COMMENT '主键',
  `username` varchar(50) NOT NULL COMMENT '用户名',
  `age` int NOT NULL COMMENT '年龄',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='用户表（聚簇索引演示）';

-- 插入测试数据（主键有序）
INSERT INTO `user` (username, age) VALUES 
('zhangsan', 20), ('lisi', 25), ('wangwu', 30), 
('zhaoliu', 35), ('qianqi', 40);

-- 范围查询（利用聚簇索引双向链表，高效遍历）
EXPLAIN ANALYZE SELECT * FROM `user` WHERE id BETWEEN 2 AND 4;

执行结果分析：

EXPLAIN ANALYZE 显示 type: range，说明使用聚簇索引的范围扫描；
由于叶子节点是双向链表，InnoDB 只需找到 id=2 的节点，再通过 next 指针遍历到 id=4，无需全表扫描。

六、链表的性能优化与避坑指南

1. 性能优化技巧

（1）使用哨兵节点简化边界判断

如前文实现的链表，通过头哨兵 / 尾哨兵节点，避免了 “插入头节点”“删除尾节点” 时的空指针判断，代码更简洁且性能更优（减少分支判断）。

（2）预分配节点减少内存开销

高频插入 / 删除场景下，可使用对象池预分配链表节点，避免频繁创建 / 销毁对象导致的 GC 压力：

package com.example.linkedlist.pool;

import com.google.common.collect.Queues;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;

import java.util.Queue;

/**
 * 链表节点对象池（基于队列实现）
 * 作者：ken
 */
@Slf4j
public class NodePool<T> {

    private final Queue<SingleLinkedList.Node<T>> pool;
    private final int maxSize; // 池最大容量

    public NodePool(int maxSize) {
        this.maxSize = maxSize;
        this.pool = Queues.newArrayDeque(maxSize);
    }

    /**
     * 从池中获取节点
     * @param data 节点数据
     * @return 链表节点
     */
    public SingleLinkedList.Node<T> getNode(T data) {
        if (pool.isEmpty()) {
            log.info("节点池为空，创建新节点");
            return new SingleLinkedList.Node<>(data);
        }
        SingleLinkedList.Node<T> node = pool.poll();
        node.data = data;
        node.next = null; // 重置指针，避免脏数据
        return node;
    }

    /**
     * 归还节点到池中
     * @param node 待归还节点
     */
    public void returnNode(SingleLinkedList.Node<T> node) {
        if (ObjectUtils.isEmpty(node) || pool.size() >= maxSize) {
            return;
        }
        // 清空节点数据，避免内存泄漏
        node.data = null;
        node.next = null;
        pool.offer(node);
    }
}

（3）双向链表替代单链表（需反向访问场景）

如 LRU 缓存、双向遍历场景，双向链表虽然占用更多内存（多一个 prev 指针），但能将删除操作的时间复杂度从 O (n) 降至 O (1)，整体性能更优。

2. 常见坑与避坑方案

（1）空指针异常（链表操作第一坑）

原因：未判断节点是否为 null 就访问 next/prev 指针；
避坑：
1. 始终使用哨兵节点；
2. 操作指针前先通过 ObjectUtils.isEmpty() 判断节点是否为空；
3. 示例：
// 错误写法（可能空指针） if (current.next != null) { ... } // 正确写法（先判空） if (!ObjectUtils.isEmpty(current) && current.next != null) { ... }

（2）链表环导致的死循环

原因：删除节点时未断开指针，或插入节点时错误指向已存在节点；
避坑：
1. 删除节点后，主动断开其 prev/next 指针（如 LRU 缓存的 removeNode 方法）；
2. 使用 Floyd 判圈算法检测环（见前文 “环形链表检测”）；
3. 示例：
// 删除节点时断开指针 private void removeNode(CacheNode<K, V> node) { node.prev.next = node.next; node.next.prev = node.prev; node.prev = null; // 断开前驱 node.next = null; // 断开后继 }

（3）随机访问的性能误区

误区：认为链表可以像数组一样通过索引快速访问；
避坑：
1. 随机访问场景优先使用数组或 ArrayList；
2. 若必须使用链表，可通过哈希表建立索引到节点的映射（如 LRU 缓存的实现），将访问复杂度降至 O (1)。

（4）并发安全问题

原因：多线程环境下，链表的插入 / 删除操作可能导致数据不一致；

避坑：

无锁场景：使用 java.util.concurrent.ConcurrentLinkedQueue（基于 CAS 实现的线程安全链表）；
锁场景：使用 ReentrantLock 保护临界区，或使用 synchronized 关键字；
示例（线程安全的单链表）： package com.example.linkedlist.threadsafe; import lombok.extern.slf4j.Slf4j; import org.springframework.util.ObjectUtils; import java.util.concurrent.locks.ReentrantLock; /** * 线程安全的单链表（基于ReentrantLock） * 作者：ken */ @Slf4j public class ThreadSafeSingleLinkedList<T> { private static class Node<T> { T data; Node<T> next; Node(T data) { this.data = data; } } private final Node<T> head = new Node<>(null); private final ReentrantLock lock = new ReentrantLock(); private int size; public void addLast(T data) { if (ObjectUtils.isEmpty(data)) { return; } lock.lock(); try { Node<T> newNode = new Node<>(data); Node<T> current = head; while (current.next != null) { current = current.next; } current.next = newNode; size++; } finally { lock.unlock(); // 确保锁释放 } } }

七、链表与数组的终极对比（实战选型指南）

对比维度	链表（单 / 双向）	数组（ArrayList）	选型建议
内存分配	离散分配（动态扩容）	连续分配（初始化需指定容量）	内存紧张 / 动态大小场景选链表
随机访问效率	O (n)（需遍历）	O (1)（下标直接访问）	高频随机访问选数组
插入 / 删除效率	O (1)（已知节点）/ O (n)（找节点）	O (n)（需移动元素）	高频插入 / 删除选链表（如消息队列）
内存开销	额外存储指针（双向链表更甚）	无额外开销	内存敏感场景选数组
缓存友好性	差（离散存储，命中率低）	好（连续存储，缓存命中高）	CPU 密集型计算选数组
线程安全	非线程安全（需额外处理）	非线程安全（需额外处理）	并发场景选 ConcurrentLinkedQueue/CopyOnWriteArrayList

权威选型依据

《Java 并发编程实战》明确指出：“对于频繁修改的集合，链表（如 LinkedList）的性能优于数组（如 ArrayList）；对于频繁访问的集合，数组的性能更优。”

实战选型案例

选链表：消息队列（高频入队 / 出队）、LRU 缓存（高频更新访问顺序）、undo 日志链（事务回滚）；
选数组：排行榜（高频查询 Top N）、数据统计（高频随机访问）、缓存热点数据（缓存友好）。

八、总结：链表的核心价值与学习建议

1. 核心价值

链表的本质是 “用指针串联离散数据”，其核心价值在于灵活的内存管理和高效的插入 / 删除操作。它不仅是数据结构的基础，更是理解复杂数据结构（如树、图）的关键 —— 树的节点本质是多指针的链表，图的边本质是双向链表的延伸。

2. 学习建议

手写实现：亲手实现单链表、双向链表的增删改查，理解指针操作的底层逻辑；
算法训练：重点攻克反转链表、环形链表检测、链表相交等经典算法题（LeetCode 206、141、160 等）；
源码分析：阅读 JDK LinkedList、ConcurrentLinkedQueue 的源码，理解工业级实现的优化技巧；
实战落地：用链表实现简单的消息队列、LRU 缓存，将理论转化为实践。

3. 拓展思考

链表的思想还可以延伸到其他领域：

分布式系统：一致性哈希环的节点映射（类似环形链表）；
操作系统：进程调度的就绪队列（双向链表）；
大数据：Hadoop 的 MapReduce 任务调度链（链表组织任务）。

掌握链表，不仅能解决面试和开发中的实际问题，更能培养 “指针思维” 和 “线性结构设计能力”。希望本文能帮你彻底搞懂链表，让这个基础数据结构成为你的 “加分项”！

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2025-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除

指针

本文分享自果酱带你啃java 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！