5 线性数据结构之链表

在上一篇中，我们讨论了线性数据结构之数组，了解了它们的基本特性、使用方式以及一些优缺点。在这一篇中，我们将聚焦于另一个重要的线性数据结构——链表。链表作为一种基础的数据结构，广泛应用于各类程序设计中。我们将详细探讨它的定义、结构、操作以及与数组的对比。

什么是链表？

链表是一种动态数据结构，它由一系列节点组成。每个节点包含了两部分信息：存储数据的部分（通常称为数据域）和指向下一个节点的引用（称为指针域）。与数组不同，链表在内存中的存储是不连续的，这使得它的大小可以动态变化。

一个链表的基本结构可以表示为：

[数据 | 指针] -> [数据 | 指针] -> [数据 | 指针] -> NULL

链表的基本类型

1. 单向链表：每个节点只指向下一个节点。
2. 双向链表：每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
3. 循环链表：链表的尾节点指向头节点，形成一个环。

在本教程中，我们主要讨论单向链表。

单向链表的基本操作

以下是链表的基本操作：

1. 创建链表：初始化一个空链表。
2. 插入节点：在链表指定位置插入新节点。
3. 删除节点：删除链表中指定位置的节点。
4. 查找节点：查找链表中是否存在某个值。
5. 遍历链表：访问链表中的每一个节点。

实例代码

下面的示例代码展示了一个简单的单向链表实现及其基本操作：

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

class LinkedList:
    def __init__(self):
        self.head = None  # 链表头

    def insert(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node  # 如果链表为空，新节点就是头节点
        else:
            current = self.head
            while current.next:  # 找到链表的最后一个节点
                current = current.next
            current.next = new_node  # 将新节点插入到链表末尾

    def delete(self, key):
        current = self.head
        prev = None
        
        # 如果头节点就是要删除的节点
        if current and current.data == key:
            self.head = current.next  # 将头节点移除
            return

        # 查找要删除的节点
        while current and current.data != key:
            prev = current
            current = current.next

        # 如果找到了要删除的节点
        if current:
            prev.next = current.next  # 跳过当前节点
        else:
            print("未找到要删除的节点")

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

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

# 使用示例
ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)

print("链表内容:")
ll.display()

ll.delete(2)

print("删除节点2后的链表内容:")
ll.display()

print("查找节点3:", ll.search(3))  # True
print("查找节点4:", ll.search(4))  # False

逐步解释上面的代码

1. **节点类 Node**：每个节点包含一个数据属性和一个指向下一个节点的属性。

2. **链表类 LinkedList**：管理链表的操作，有插入、删除、查找和显示等方法。

3. 插入方法：如果链表为空，新节点成为头节点；否则，遍历找到最后一个节点并将新节点插入。

4. 删除方法：遍历查找要删除的节点，调整指针以跳过该节点。

5. 查找方法：遍历链表，检查节点的数据是否等于要查找的值。

6. 显示方法：输出链表中所有节点的数据。

链表的优缺点

优点：

• 动态大小：链表可以根据需要动态扩展或收缩，而数组大小固定。
• 高效的插入和删除：在增加或删除节点时不需要移动其他节点，只需修改指针。

缺点：

• 内存开销：每个节点都需要额外的内存空间来存储指针。
• 访问速度较慢：与数组相比，链表的随机访问速度慢，因为必须从头部开始遍历。

总结

链表是一种灵活且强大的数据结构，非常适合于需要频繁插入和删除操作的场景。相较于数组，链表更具动态性，但在内存使用和访问速度上又有所劣势。在下一篇中，我们将讨论线性数据结构之栈，与链表的特性和应用进行对比，敬请期待！