当前位置：首页 > article >正文

Java数据结构 (从0构建链表（LinkedList))

article 2025/1/23 14:41:01

在本文中，我们将基于 MySingleLinkedList 类，深入探讨单链表的实现，包括创建、插入、删除等核心操作，同时分享完整的代码示例。单链表是一种灵活的数据结构，适用于处理需要频繁插入和删除操作的场景，例如实现队列 📜、链式栈 🔥、循环队列 🔄 等。在计算机科学和实际开发中，链表结构被广泛应用。它不仅可以高效地处理插入和删除操作，还能够根据实际需求实现不同的链表结构。🚀本篇不仅涵盖了基本功能的代码展示，还补充了各种操作的实现细节和优化建议，旨在让读者能够全面掌握单链表的使用与实现。😊💡

链表的基本结构 📊

代码实现 🖥️

讲解 🧑‍🏫

a. 链表的基本操作 🔧

1. 链表的创建 🛠️

动态创建链表 💻

讲解 💡

2. 链表的遍历 🔍

讲解 📚

3. 获取链表长度 🔢

讲解 🧐

b. 插入操作 ➕

1. 头插法 🏁

讲解 ⚡

2. 尾插法 🔚

讲解 📈

3. 任意位置插入 🔄

讲解 📘

c. 删除操作 ❌

1. 删除第一个匹配的节点

讲解 🧠

2. 删除所有匹配的节点

讲解 🔍

3. 清空链表

讲解 💬

总结 🌟

链表的基本结构 📊

单链表由节点（ListNode）组成，每个节点包含三个部分：

值域（val）：存储节点的值。💎
指针域（next）：指向下一个节点。👉
前驱指针（prev）：尽管在单链表中未实际使用，它可以支持双向链表的扩展。🔄

代码实现 🖥️

以下是链表的基础结构代码：

public class MySingleLinkedList {
    static class ListNode {
        public ListNode next;
        public int val;
        public ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head; // 头节点 🧑‍💻
    public ListNode last; // 尾节点 🎯
}

讲解 🧑‍🏫

每个节点由 ListNode 类表示，包含数据域 val 和两个指针域 next 和 prev。
head 用于标记链表的起始位置，last 标记链表的尾节点（可选）。
相较于数组，链表在插入和删除操作中更具灵活性，但随机访问性能较差。链表的插入和删除操作无需移动其他元素，且通过指针的变动即可实现动态扩展，极大提高了操作效率。

链表的基本操作 🔧

1. 链表的创建 🛠️

手动链接节点的方式可以快速构建一个简单的链表。我们通过手动指定每个节点的连接方式，构造一个简单的链表。它适用于学习和理解链表基本结构：

public void createList() {
    ListNode listNode1 = new ListNode(1);
    ListNode listNode2 = new ListNode(2);
    ListNode listNode3 = new ListNode(3);
    ListNode listNode4 = new ListNode(4);
    ListNode listNode5 = new ListNode(5);

    this.head = listNode1;
    listNode1.next = listNode2;
    listNode2.next = listNode3;
    listNode3.next = listNode4;
    listNode4.next = listNode5;
    listNode5.next = null;
}

动态创建链表 💻

动态创建链表可以根据输入动态生成节点并构建链表，这样不仅增加了代码的灵活性，而且便于应对不同长度和结构的链表需求：

public void createListDynamic(int[] values) {
    if (values == null || values.length == 0) {
        return;
    }
    this.head = new ListNode(values[0]);
    ListNode cur = this.head;
    for (int i = 1; i < values.length; i++) {
        cur.next = new ListNode(values[i]);
        cur = cur.next;
    }
}

讲解 💡

动态连接节点：node1.next = node2 是构建链表的核心逻辑，通过该步骤，node1 的 next 指向了 node2，形成了节点之间的连接，链表的扩展就是通过这种方式完成的。🎯这种方式也适用于链表的动态增长，在需要时可以随时添加新的节点。
灵活性：动态方法使得链表的创建不再依赖固定的结构，可以根据用户的输入或其他需求动态生成节点，极大提高了代码的通用性。

2. 链表的遍历 🔍

通过遍历链表打印节点值，同时考虑链表为空时的情况，避免出现空指针异常。遍历链表时，需要从头节点开始依次访问每个节点：

public void display() {
    if (head == null) {
        System.out.println("链表为空");
        return;
    }
    ListNode cur = head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}

讲解 📚

动态连接节点：node1.next = node2 是构建链表、插入节点的基础，解决了链表动态扩展问题。
安全遍历链表：while (cur != null) 确保链表遍历过程可靠且高效，避免了指针错误或无限循环的问题。这样可以避免遍历时访问空指针或进入无限循环。⚠️
前进推进的流畅性：cur = cur.next 是链表遍历的核心语句，它使得 cur 从当前节点指向下一个节点，实现了链表的逐步推进。这个简洁的推进逻辑符合链表的递归结构特性，也使得代码更易于理解。😊

3. 获取链表长度 🔢

链表的长度可以通过遍历链表的所有节点来计算，直到达到链表的末尾：

public int size() {
    ListNode cur = head;
    int length = 0;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}