在这里插入图片描述

文章目录

单向链表：从创建到操作全解析 📝

链表是计算机科学中最基础且重要的数据结构之一，而单向链表更是许多复杂结构的基石。掌握它，将为你的编程之路打下坚实基础！🚀

在计算机科学中，链表（Linked List） 是一种常见的数据结构，用于存储元素的集合。与数组不同，链表中的元素在内存中并非连续存放，而是通过指针相互连接。其中，单向链表（Singly Linked List） 是最简单的链表类型，每个节点包含数据和指向下一个节点的指针。本文将深入探讨单向链表的创建、插入、删除和遍历操作，并提供详细的代码示例和图表说明。

1. 单向链表的基本概念 🧠

单向链表由一系列节点组成，每个节点包含两部分：

  • 数据域（Data）：存储实际的数据。
  • 指针域（Next）：存储指向下一个节点的地址。

链表的第一个节点称为头节点（Head），最后一个节点的指针指向 NULL，表示链表结束。由于节点通过指针连接，链表可以动态地增长或缩小，非常灵活。

下面是一个简单的单向链表结构示意图，使用 Mermaid 图表展示：

Head

Data: 10
Next: -

Data: 20
Next: -

Data: 30
Next: NULL

与数组相比，链表的主要优点是动态大小和高效插入/删除，但缺点是无法随机访问元素。如果你想了解更多关于数据结构的基础知识，可以参考 GeeksforGeeks 的数据结构指南，这是一个非常全面的资源。

2. 实现单向链表 🛠️

我们将使用 Python 来实现单向链表，因为 Python 语法简洁易懂，适合教学目的。其他语言（如 C++ 或 Java）的实现逻辑类似。

2.1 定义节点类

首先，我们需要定义一个节点类，表示链表中的每个元素：

class Node:
    def __init__(self, data):
        self.data = data  # 数据域
        self.next = None   # 指针域，初始化为 None

这个类很简单：data 存储值，next 存储对下一个节点的引用。

2.2 创建链表

创建链表通常从初始化头节点开始。头节点是链表的起点，如果链表为空，头节点为 None。

class LinkedList:
    def __init__(self):
        self.head = None  # 初始化头节点为空

# 示例：创建一个空链表
my_list = LinkedList()

此时，链表为空，head 为 None。接下来，我们将通过插入操作添加节点。

3. 插入操作 ➕

插入操作是链表的常见操作之一，可以在头部、尾部或特定位置插入节点。

3.1 在头部插入

在头部插入节点是最简单的插入方式。新节点成为头节点，并指向原来的头节点。

def insert_at_head(self, data):
    new_node = Node(data)  # 创建新节点
    new_node.next = self.head  # 新节点指向原头节点
    self.head = new_node  # 更新头节点为新节点

示例使用：

my_list = LinkedList()
my_list.insert_at_head(10)  # 链表：10 -> NULL
my_list.insert_at_head(20)  # 链表：20 -> 10 -> NULL

这个过程可以通过以下 Mermaid 图表可视化：

新节点: 20

原头节点: 10

Head

NULL

3.2 在尾部插入

在尾部插入需要遍历链表找到最后一个节点，然后将其 next 指向新节点。

def insert_at_tail(self, data):
    new_node = Node(data)
    if self.head is None:  # 如果链表为空
        self.head = new_node
    else:
        current = self.head
        while current.next:  # 遍历到最后一个节点
            current = current.next
        current.next = new_node  # 最后一个节点指向新节点

示例使用：

my_list = LinkedList()
my_list.insert_at_tail(10)  # 链表：10 -> NULL
my_list.insert_at_tail(20)  # 链表：10 -> 20 -> NULL

3.3 在特定位置插入

在特定位置（如第 k 个节点后）插入稍微复杂一些。需要先找到第 k 个节点，然后调整指针。

def insert_after_position(self, data, position):
    if position < 0:
        print("位置无效")
        return
    new_node = Node(data)
    current = self.head
    count = 0
    while current and count < position:
        current = current.next
        count += 1
    if current is None:
        print("位置超出链表长度")
    else:
        new_node.next = current.next
        current.next = new_node

示例使用：

my_list = LinkedList()
my_list.insert_at_tail(10)
my_list.insert_at_tail(30)
my_list.insert_after_position(20, 0)  # 在位置0后插入20: 10 -> 20 -> 30 -> NULL

插入操作是链表的优势之一，平均时间复杂度为 O(1) 对于头部插入，O(n) 对于其他位置。如果你想深入了解时间复杂度的概念，可以阅读 Programiz 的算法复杂度指南。

4. 删除操作 ❌

删除操作移除链表中的节点，可以按值或按位置删除。

4.1 删除头部节点

删除头部节点很简单：将头节点指向下一个节点即可。

def delete_at_head(self):
    if self.head is None:
        print("链表为空，无法删除")
    else:
        self.head = self.head.next  # 头节点指向下一个节点

示例使用：

my_list = LinkedList()
my_list.insert_at_head(10)
my_list.insert_at_head(20)
my_list.delete_at_head()  # 删除20，链表变为: 10 -> NULL

4.2 删除特定值节点

删除特定值节点需要遍历链表，找到该节点并调整指针绕过它。

def delete_by_value(self, data):
    if self.head is None:
        print("链表为空，无法删除")
        return
    if self.head.data == data:  # 如果头节点就是要删除的节点
        self.head = self.head.next
        return
    current = self.head
    while current.next:
        if current.next.data == data:
            current.next = current.next.next  # 绕过要删除的节点
            return
        current = current.next
    print("未找到值为", data, "的节点")

示例使用：

my_list = LinkedList()
my_list.insert_at_tail(10)
my_list.insert_at_tail(20)
my_list.insert_at_tail(30)
my_list.delete_by_value(20)  # 删除20，链表变为: 10 -> 30 -> NULL

删除过程可以通过以下 Mermaid 图表展示（删除值为20的节点）：

渲染错误: Mermaid 渲染失败: Parse error on line 10: ...--> D C -.-> D // 虚线表示被移除的链接 D ----------------------^ Expecting 'SEMI', 'NEWLINE', 'EOF', 'AMP', 'START_LINK', 'LINK', 'LINK_ID', got 'NODE_STRING'

4.3 删除特定位置节点

类似插入，删除特定位置节点需要遍历到该位置的前一个节点。

def delete_by_position(self, position):
    if self.head is None or position < 0:
        print("无效操作")
        return
    if position == 0:
        self.head = self.head.next
        return
    current = self.head
    count = 0
    while current and count < position - 1:
        current = current.next
        count += 1
    if current is None or current.next is None:
        print("位置超出范围")
    else:
        current.next = current.next.next

示例使用：

my_list = LinkedList()
my_list.insert_at_tail(10)
my_list.insert_at_tail(20)
my_list.insert_at_tail(30)
my_list.delete_by_position(1)  # 删除位置1的节点20，链表变为: 10 -> 30 -> NULL

删除操作的时间复杂度与插入类似：头部删除为 O(1)，其他为 O(n)。

5. 遍历操作 🔍

遍历是访问链表中每个元素的过程，通常用于打印、搜索或处理数据。

5.1 简单遍历打印

从头节点开始，依次访问每个节点并打印其数据，直到遇到 NULL。

def traverse(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("NULL")

示例使用：

my_list = LinkedList()
my_list.insert_at_tail(10)
my_list.insert_at_tail(20)
my_list.insert_at_tail(30)
my_list.traverse()  # 输出: 10 -> 20 -> 30 -> NULL

5.2 搜索元素

遍历链表，检查每个节点的数据是否匹配目标值。

def search(self, data):
    current = self.head
    position = 0
    while current:
        if current.data == data:
            return position  # 返回找到的位置
        current = current.next
        position += 1
    return -1  # 未找到

示例使用：

position = my_list.search(20)  # 返回1
if position != -1:
    print("元素找到，位置:", position)
else:
    print("元素未找到")

遍历的时间复杂度为 O(n)，因为需要访问每个节点。对于大型链表，优化遍历算法可能很重要，但单向链表的基本遍历无法避免 O(n) 复杂度。

6. 完整代码示例 📦

下面是一个完整的 Python 程序，包含单向链表的所有操作：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_tail(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def insert_after_position(self, data, position):
        if position < 0:
            print("位置无效")
            return
        new_node = Node(data)
        current = self.head
        count = 0
        while current and count < position:
            current = current.next
            count += 1
        if current is None:
            print("位置超出链表长度")
        else:
            new_node.next = current.next
            current.next = new_node

    def delete_at_head(self):
        if self.head is None:
            print("链表为空，无法删除")
        else:
            self.head = self.head.next

    def delete_by_value(self, data):
        if self.head is None:
            print("链表为空，无法删除")
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next
        print("未找到值为", data, "的节点")

    def delete_by_position(self, position):
        if self.head is None or position < 0:
            print("无效操作")
            return
        if position == 0:
            self.head = self.head.next
            return
        current = self.head
        count = 0
        while current and count < position - 1:
            current = current.next
            count += 1
        if current is None or current.next is None:
            print("位置超出范围")
        else:
            current.next = current.next.next

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("NULL")

    def search(self, data):
        current = self.head
        position = 0
        while current:
            if current.data == data:
                return position
            current = current.next
            position += 1
        return -1

# 演示代码
if __name__ == "__main__":
    ll = LinkedList()
    ll.insert_at_tail(10)
    ll.insert_at_tail(20)
    ll.insert_at_tail(30)
    print("初始链表:")
    ll.traverse()

    ll.insert_at_head(5)
    print("在头部插入5后:")
    ll.traverse()

    ll.insert_after_position(15, 1)
    print("在位置1后插入15后:")
    ll.traverse()

    ll.delete_by_value(20)
    print("删除值20后:")
    ll.traverse()

    pos = ll.search(15)
    print("元素15的位置:", pos)

输出结果：

初始链表:
10 -> 20 -> 30 -> NULL
在头部插入5后:
5 -> 10 -> 20 -> 30 -> NULL
在位置1后插入15后:
5 -> 10 -> 15 -> 20 -> 30 -> NULL
删除值20后:
5 -> 10 -> 15 -> 30 -> NULL
元素15的位置: 2

这个完整示例展示了如何组合使用各种操作来管理链表。你可以尝试修改代码，练习这些操作。

7. 应用场景与总结 🎯

单向链表在许多实际场景中都有应用：

  • 实现栈和队列：链表可以高效地支持先进先出（FIFO）或后进先出（LIFO）操作。
  • 动态内存管理：在操作系统中，链表用于管理空闲内存块。
  • 浏览器历史记录：许多浏览器使用链表来支持前进和后退功能。
  • 音乐播放列表：播放列表中的歌曲可以组织为链表，方便插入和删除。

链表的优点包括动态大小、高效插入/删除，但缺点是无法随机访问、需要额外内存存储指针。在选择数据结构时，应根据具体需求权衡利弊。

如果你想进一步学习链表和其他数据结构，Wikipedia 的链表条目提供了详细的理论背景和历史信息。

总之，单向链表是编程和计算机科学基础中的重要组成部分。掌握它的操作不仅有助于理解更复杂的数据结构，还能提高你解决实际问题的能力。快乐编码！💻✨

注意：本文代码示例采用 Python 实现，其他语言逻辑类似。确保在实践时根据语言特性调整语法。

# 链表 # 数据结构
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

AtomGit 首发开源｜光轮智能发布全球首个十万小时级全模态人类行为开源数据集 EgoSuite-Open100K

avatar AtomGit开源社区
cover

构筑赋能金融行业应用 Agent｜20 强决战北京，一场金融 Agent 的硬核答卷

avatar AtomGit开源社区
cover

最高赢取价值万元大奖，仓颉生态创新开发挑战赛开启！

avatar AtomGit开源社区