链表
Anthony_Stark_Li Anthony_Stark_Li 0 评论 programming 18 阅读

链表

一、单向链表的模拟实现

单向链表的每个节点只包含自身数据和下一个节点的引用，只能从头节点向尾节点遍历，操作相对简单，是理解链表结构的基础。

完整实现代码

public class MySinglyLinkedList { // 重命名类，明确是单向链表，更易理解

    // 静态内部类：链表节点（封装数据和下一个节点引用）
    // 为什么用静态内部类？避免外部类的隐式引用，节省内存，且节点逻辑与外部链表独立
    static class ListNode {
        public int val; // 节点存储的数据
        public ListNode next; // 指向下一个节点的引用（原代码中Address命名不直观，改为next更符合行业惯例）

        // 构造方法：初始化节点数据
        public ListNode(int val) {
            this.val = val;
            // next 默认为 null，无需显式赋值
        }
    }

    public ListNode head; // 链表的头节点（链表的入口，通过它遍历整个链表）

    /**
     * 手动创建一个测试链表（用于快速验证功能，非核心方法）
     */
    public void createLinkedList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

        // 建立节点间的引用关系，形成链表
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1; // 头节点指向第一个节点
    }

    /**
     * 头插法：在链表头部插入新节点
     * 优势：时间复杂度 O(1)，无需遍历链表
     * @param data 要插入的数据
     */
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        // 新节点的 next 指向原来的头节点
        newNode.next = head;
        // 头节点更新为新节点
        head = newNode;
    }

    /**
     * 尾插法：在链表尾部插入新节点
     * 劣势：时间复杂度 O(n)，需要遍历到链表末尾
     * @param data 要插入的数据
     */
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        // 特殊情况：链表为空，直接将头节点指向新节点
        if (head == null) {
            head = newNode;
            return;
        }
        // 遍历到链表末尾（cur.next 为 null 时，cur 就是尾节点）
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        // 尾节点的 next 指向新节点
        cur.next = newNode;
    }

    /**
     * 任意位置插入：在下标 index 处插入新节点（下标从 0 开始）
     * @param index 插入位置
     * @param data  插入数据
     */
    public void addIndex(int index, int data) {
        int size = size();
        // 1. 合法性校验：index 小于 0 或大于链表长度，插入失败
        if (index < 0 || index > size) {
            System.out.println("插入下标不合法！");
            return;
        }
        // 2. 复用头插法：index 为 0，直接头部插入
        if (index == 0) {
            addFirst(data);
            return;
        }
        // 3. 复用尾插法：index 等于链表长度，直接尾部插入
        if (index == size) {
            addLast(data);
            return;
        }
        // 4. 中间插入：找到 index 前一个节点（cur）
        ListNode newNode = new ListNode(data);
        ListNode cur = head;
        int count = 0;
        while (count != index - 1) { // 优化原代码，直接找到前驱节点，更高效
            cur = cur.next;
            count++;
        }
        // 5. 建立引用关系（先绑后面，再绑前面，避免链表断裂）
        newNode.next = cur.next;
        cur.next = newNode;
    }

    /**
     * 查找是否包含关键字 key
     * @param key 要查找的关键字
     * @return 包含返回 true，否则返回 false
     */
    public boolean contains(int key) {
        ListNode cur = head;
        // 遍历整个链表，逐一比对数据
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next; // 原代码遗漏此句，会导致死循环，已修复
        }
        return false;
    }

    /**
     * 删除第一次出现关键字为 key 的节点
     * @param key 要删除的关键字
     */
    public void remove(int key) {
        // 特殊情况1：链表为空，直接返回
        if (head == null) {
            System.out.println("链表为空，无法删除！");
            return;
        }
        // 特殊情况2：头节点就是要删除的节点
        if (head.val == key) {
            head = head.next;
            return;
        }
        // 1. 找到要删除节点的前驱节点（cur）
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                break; // 找到前驱节点，跳出循环
            }
            cur = cur.next;
        }
        // 2. 判断是否找到（避免链表中无 key 的情况）
        if (cur.next != null) {
            // 3. 跳过要删除的节点，建立新的引用
            cur.next = cur.next.next;
        } else {
            System.out.println("链表中无此关键字，无法删除！");
        }
    }

    /**
     * 删除所有值为 key 的节点
     * @param key 要删除的关键字
     */
    public void removeAllKey(int key) {
        // 特殊情况：链表为空，直接返回
        if (head == null) {
            System.out.println("链表为空，无法删除！");
            return;
        }
        // 1. 处理中间和尾部节点（借助前驱节点 prev 和当前节点 cur）
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == key) {
                // 找到要删除的节点，前驱节点直接跳过当前节点
                prev.next = cur.next;
            } else {
                // 未找到，前驱节点和当前节点同时后移
                prev = cur;
            }
            // 无论是否删除，当前节点都要后移
            cur = cur.next;
        }
        // 2. 处理头节点（最后处理，避免链表断裂）
        if (head.val == key) {
            head = head.next;
        }
    }

    /**
     * 得到链表的长度
     * @return 链表节点个数
     */
    public int size() {
        ListNode cur = head;
        int count = 0;
        // 遍历链表，统计节点个数
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 清空链表
     * 简单高效：直接将头节点置为 null，GC 会自动回收链表节点
     */
    public void clear() {
        head = null;
    }

    /**
     * 打印链表所有数据
     */
    public void display() {
        ListNode cur = head;
        // 遍历链表，逐个打印节点数据
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println(); // 换行，优化打印格式
    }
}

二、双向链表的模拟实现

双向链表的每个节点包含自身数据、上一个节点引用（prev）和下一个节点引用（next），可以双向遍历，首尾操作更高效，也是 Java LinkedList 的底层实现。

完整实现代码

public class MyDoublyLinkedList { // 重命名类，明确是双向链表

    // 静态内部类：双向链表节点（封装数据、前驱节点、后继节点）
    static class ListNode {
        public int val;      // 节点存储的数据
        public ListNode prev; // 指向前一个节点的引用
        public ListNode next; // 指向后一个节点的引用

        // 构造方法：初始化节点数据
        public ListNode(int val) {
            this.val = val;
            // prev 和 next 默认为 null，无需显式赋值
        }
    }

    public ListNode head;  // 链表头节点
    public ListNode last;  // 链表尾节点（双向链表特有，直接指向尾节点，尾插法时间复杂度 O(1)）

    /**
     * 头插法：在链表头部插入新节点
     * @param data 要插入的数据
     */
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        // 特殊情况：链表为空，头节点和尾节点都指向新节点
        if (head == null) {
            head = newNode;
            last = newNode;
            return;
        }
        // 1. 新节点的 next 指向原来的头节点
        newNode.next = head;
        // 2. 原来的头节点的 prev 指向新节点
        head.prev = newNode;
        // 3. 头节点更新为新节点
        head = newNode;
    }

    /**
     * 尾插法：在链表尾部插入新节点
     * 优势：借助 last 节点，时间复杂度 O(1)
     * @param data 要插入的数据
     */
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        // 特殊情况：链表为空，头节点和尾节点都指向新节点
        if (head == null) {
            head = newNode;
            last = newNode;
            return;
        }
        // 1. 原来的尾节点的 next 指向新节点
        last.next = newNode;
        // 2. 新节点的 prev 指向原来的尾节点
        newNode.prev = last;
        // 3. 尾节点更新为新节点
        last = newNode;
    }

    /**
     * 任意位置插入：在下标 index 处插入新节点（下标从 0 开始）
     * @param index 插入位置
     * @param data  插入数据
     */
    public void addIndex(int index, int data) {
        int size = size();
        // 1. 合法性校验
        if (index < 0 || index > size) {
            System.out.println("插入下标不合法！");
            return;
        }
        // 2. 复用头插法
        if (index == 0) {
            addFirst(data);
            return;
        }
        // 3. 复用尾插法
        if (index == size) {
            addLast(data);
            return;
        }
        // 4. 中间插入：找到 index 对应的节点（cur）
        ListNode newNode = new ListNode(data);
        ListNode cur = head;
        int count = 0;
        while (count != index) {
            cur = cur.next;
            count++;
        }
        // 5. 建立引用关系（先绑前后，再断旧链，避免数据丢失）
        newNode.prev = cur.prev;
        newNode.next = cur;
        cur.prev.next = newNode;
        cur.prev = newNode;
    }

    /**
     * 查找是否包含关键字 key
     * @param key 要查找的关键字
     * @return 包含返回 true，否则返回 false
     */
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 删除第一次出现关键字为 key 的节点
     * @param key 要删除的关键字
     */
    public void remove(int key) {
        // 特殊情况1：链表为空
        if (head == null) {
            System.out.println("链表为空，无法删除！");
            return;
        }
        ListNode cur = head;
        // 特殊情况2：头节点是要删除的节点
        if (cur.val == key) {
            head = head.next;
            // 处理链表只有一个节点的情况
            if (head != null) {
                head.prev = null;
            } else {
                last = null;
            }
            return;
        }
        // 1. 找到要删除的节点
        while (cur != null) {
            if (cur.val == key) {
                break;
            }
            cur = cur.next;
        }
        // 2. 判断是否找到
        if (cur == null) {
            System.out.println("链表中无此关键字，无法删除！");
            return;
        }
        // 3. 处理中间节点和尾节点
        cur.prev.next = cur.next;
        // 处理尾节点的情况
        if (cur.next != null) {
            cur.next.prev = cur.prev;
        } else {
            last = cur.prev;
        }
    }

    /**
     * 删除所有值为 key 的节点
     * @param key 要删除的关键字
     */
    public void removeAllKey(int key) {
        // 特殊情况：链表为空
        if (head == null) {
            System.out.println("链表为空，无法删除！");
            return;
        }
        ListNode cur = head;
        while (cur != null) {
            // 找到要删除的节点
            if (cur.val == key) {
                // 处理头节点
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    } else {
                        last = null;
                    }
                } else {
                    // 处理中间节点和尾节点
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = cur.prev;
                    }
                }
            }
            // 当前节点后移
            cur = cur.next;
        }
    }

    /**
     * 得到链表的长度
     * @return 链表节点个数
     */
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 打印链表所有数据
     */
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 清空链表（安全清空，避免内存泄漏）
     */
    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            ListNode nextNode = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = nextNode;
        }
        head = null;
        last = null;
    }
}

核心优势说明

  1. 新增 last 尾节点：尾插法、删除尾节点无需遍历，效率从 O(n) 提升到 O(1)。
  2. 双向遍历支持：可通过 prev 向前遍历，为后续复杂操作（如逆序打印）提供便利。
  3. 安全清空：不仅置空 head 和 last，还逐个置空节点的 prev 和 next，避免潜在内存泄漏。

三、链表使用

掌握了底层模拟实现后，我们来使用 JDK 提供的 LinkedList，它基于双向链表实现，提供了丰富的操作方法，满足日常开发需求。

常用方法演示

import java.util.ArrayList;
import java.util.LinkedList;

public class LinkedListCommonMethods {
    public static void main(String[] args) {
        // 1. 创建 LinkedList 实例（泛型指定存储 Integer 类型数据）
        LinkedList<Integer> linkedList = new LinkedList<>();

        // 2. 新增元素
        linkedList.add(12); // 尾插元素（默认方法）
        linkedList.add(34); // 尾插元素
        linkedList.add(2, 45); // 在索引 2 处插入元素（中间插入）

        // 3. 批量添加元素
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(999);
        linkedList.addAll(arrayList); // 尾插整个集合的元素

        // 4. 删除元素
        linkedList.remove(2); // 删除索引 2 处的元素
        linkedList.remove((Integer) 999); // 删除第一个出现的 999（注意装箱，避免与索引删除混淆）

        // 5. 获取和修改元素
        int firstElement = linkedList.get(0); // 获取索引 0 处的元素
        linkedList.set(0, 888); // 将索引 0 处的元素修改为 888

        // 6. 查找元素
        boolean contains = linkedList.contains(888); // 判断是否包含 888
        int firstIndex = linkedList.indexOf(888); // 获取 888 第一次出现的索引
        int lastIndex = linkedList.lastIndexOf(888); // 获取 888 最后一次出现的索引

        // 7. 截取子链表（注意：子链表是原链表的视图，修改子链表会影响原链表）
        LinkedList<Integer> subList = (LinkedList<Integer>) linkedList.subList(0, 1);

        // 8. 打印结果（验证操作）
        System.out.println("原链表：" + linkedList);
        System.out.println("子链表：" + subList);

        // 9. 清空链表
        linkedList.clear();
        System.out.println("清空后链表：" + linkedList);
    }
}

多种遍历方式演示

LinkedList 支持多种遍历方式，其中 ListIterator 支持双向遍历，是其特色之一。

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListTraversal {
    public static void main(String[] args) {
        // 初始化链表
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);

        // 方式1：普通迭代器（正向遍历）
        System.out.println("普通迭代器正向遍历：");
        Iterator<Integer> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();

        // 方式2：ListIterator 正向遍历（支持后续反向遍历，功能更强）
        System.out.println("ListIterator 正向遍历：");
        ListIterator<Integer> listIterator = linkedList.listIterator();
        while (listIterator.hasNext()) {
            System.out.print(listIterator.next() + " ");
        }
        System.out.println();

        // 方式3：ListIterator 反向遍历（双向链表的优势体现）
        System.out.println("ListIterator 反向遍历：");
        ListIterator<Integer> reverseIterator = linkedList.listIterator(linkedList.size());
        while (reverseIterator.hasPrevious()) {
            System.out.print(reverseIterator.previous() + " ");
        }
        System.out.println();
    }
}

四、相关内部类

在链表模拟实现中，我们使用了静态内部类，而日常开发中还会遇到匿名内部类，这两种内部类在 Java 中应用广泛，这里做简单梳理。

静态内部类

静态内部类是被 static 修饰的内部类，它与外部类的实例无关，仅属于外部类本身。

特点与示例

public class OuterClass {
    public int data1; // 实例成员变量
    public static int data2; // 静态成员变量

    // 静态内部类
    static class StaticInnerClass {
        public void innerMethod() {
            // 静态内部类：无法访问外部类的实例成员变量（data1）
            // data1 = 1; // 编译报错
            data2 = 100; // 可以访问外部类的静态成员变量（data2）
            System.out.println("静态内部类方法执行，data2 = " + data2);
        }
    }

    public static void main(String[] args) {
        // 创建静态内部类实例：无需先创建外部类实例，直接通过外部类.内部类创建
        OuterClass.StaticInnerClass staticInner = new OuterClass.StaticInnerClass();
        staticInner.innerMethod(); // 调用内部类方法
    }
}

核心要点

  1. 访问权限：无法访问外部类的实例成员，只能访问静态成员。
  2. 实例创建：无需依赖外部类实例，直接创建。
  3. 应用场景：当内部类与外部类的实例无关，仅为封装相关逻辑（如链表的节点）时使用。

匿名内部类

匿名内部类是没有类名的内部类，它在声明的同时完成实例化，只能使用一次，常用于简化接口/抽象类的实现。

特点与示例

// 定义一个接口
interface Greeting {
    void greet();
}

public class OuterClassAnonymous {
    public static void main(String[] args) {
        // 匿名内部类：实现 Greeting 接口，同时完成实例化
        Greeting greeting = new Greeting() {
            // 匿名内部类中可以定义成员变量
            private int count = 1;

            @Override
            public void greet() {
                System.out.println("Hello, LinkedList! 这是第 " + count + " 次问候");
                count++;
            }
        }; // 注意：匿名内部类末尾必须加分号

        // 调用匿名内部类的方法
        greeting.greet();
    }
}

核心要点

  1. 无类名：无需单独定义类，直接实现接口/继承抽象类。
  2. 一次实例化：声明与实例化同时完成，只能创建一个实例。
  3. 应用场景：快速实现简单的接口/抽象类，无需复用（如事件监听、线程创建）。
文章标签
#Datastructure#Java
许可协议
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
顺序表 2025-07-26
栈与队列 2025-08-11

评论区