8 数据结构概述之链表

在前一篇教程中，我们谈到了数据结构中的数组，了解了它们的特性、优缺点以及在具体案例中的应用。今天，我们将更深入地探讨链表这一数据结构，帮助大家理解其构成、特点以及使用场景。

一、链表的基本概念

链表是一种线性数据结构，它由一系列节点构成。每个节点包含两部分：

1. 数据字段：存储数据。
2. 指针字段：指向下一个节点。

链表的一个主要特点是存储元素不需要在内存中连续，这样可以动态地增加或减少元素。

链表的基本结构

在实际编程中，链表的节点通常用一个结构体来表示。例如，在Python中，我们可以定义一个链表节点如下：

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

在这个结构中，data 存储着节点的数据，而 next 存储着指向下一个节点的链接。

二、链表的类型

链表主要有三种常见类型：

1. 单向链表：每个节点只包含指向下一个节点的指针。
2. 双向链表：每个节点包含指向前一个节点和下一个节点的指针，可以在两个方向上遍历。
3. 循环链表：最后一个节点指向第一个节点，使得整个链表形成一个闭环。

示例：单向链表

以单向链表为例，我们可以定义链表本身以及一些基本操作，比如添加节点和遍历链表：

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

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

使用示例

在链表中添加元素和遍历链表的过程如下：

linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.display()  # 输出：1 -> 2 -> 3 -> None

三、链表的优缺点

优点

• 动态大小：链表的大小可以灵活地增加或减少，方便存储变动不居的数据。
• 插入/删除操作：在已知位置的情况下，进行插入或删除操作更为高效，只需改变指针，无需移动大块数据。

缺点

• 空间复杂度：每个节点除了数据还需要一个指针，因而占用更多的内存。
• 访问效率：访问特定节点时，必须从头遍历，时间复杂度为$O(n)$，而数组可以在$O(1)$的时间内访问特定元素。

四、链表的应用场景

链表在很多场景中都能发挥作用，例如：

1. 实现队列和栈：链表可被用来实现队列（FIFO）和栈（LIFO）数据结构。
2. 动态数据存储：如实现动态数组（ArrayList），在元素数量变化频繁的情况下比数组更有效。
3. 图的邻接表表示：链表可以用来表示图的边，简化对节点及其连接的表示。

五、小结

链表作为一种基础数据结构，其灵活性和高效的插入、删除特性使其在实际应用中被广泛使用。虽然链表在随机访问方面不如数组高效，但在需求动态存储时，链表展现出独有的优势。

在下一篇教程中，我们将继续我们的算法小白教程系列，探讨“数据结构概述之栈和队列”。通过对这些数据结构的理解，进一步加深对算法和数据结构的综合应用能力。