简介

为了本课程的目的，我们将介绍以下几种链表类型，并用 Python 实现它们：

1. 单向链表
2. 双向链表
3. 循环链表

以下是单向链表的简单示意图：

结构

每个链表都由节点组成，如上图所示。每个节点包含两个部分：

1. 数据（Data）
2. 下一个节点指针（Next）

数据 部分用于存储链表中节点的数据元素，可以是字符串、字符、数字或其他类型的对象。在上图中，数据元素为 A、B 和 C，均为字符类型。

下一个节点指针 是每个节点中的一个指针，用于指向下一个节点。

链表的起始位置称为 头节点（head）。head 是一个指向链表开头的指针，若要遍历链表以获取或访问某个元素，就需要从 head 开始逐个移动。

单向链表的最后一个节点指向一个空值（null），这个概念标志着链表的结束。在 Python 中，我们使用 None 表示该空值。最后一个节点的 next 指针指向 None，表示链表已到末尾。

数组 vs 链表

插入/删除操作

在数组开头插入或删除元素的时间复杂度为 $O(n)$。假设我们有一个数组和一个要插入到开头的值，插入时需要将所有元素向右移动一位，为新元素腾出空间。由于元素的移动，时间复杂度为 $O(n)$。删除数组开头的元素时也类似：需要将所有元素向左移动一位，因此时间复杂度同样是 $O(n)$。

而在链表头部插入节点，只要给定头节点，就是一个常数时间操作，因为只需调整少数几个指针即可完成。如果已知要插入位置的前一个节点指针，插入操作也是常数时间。

访问元素

在数组中根据索引访问元素的速度远高于在链表中访问第 n 个元素。数组的元素访问是常数时间操作，因为数组在内存中是连续存储的，给定索引后可直接定位到对应元素。

而在链表中访问第 n 个元素，必须从头节点开始逐个遍历，直到到达目标位置，因此时间复杂度为 $O(n)$。

内存连续性

数组在内存中是连续存储的，因此可以实现常数时间访问；而链表则不具备这种连续内存的优势。

在选择数据结构时，请务必参考上述对比表格，权衡数组与链表的优缺点。面对具体问题时，应判断是否更适合使用数组。为此，你需要清楚了解两种数据结构各自的优劣势。

实现

现在我们来创建 Python 中的类：

• Node 类
• LinkedList 类

1class Node:
2  def __init__(self, data):
3    self.data = data
4    self.next = None
5
6class LinkedList:
7  def __init__(self):
8    self.head = None

我们定义了一个名为 Node 的类。在该类的构造函数中，接收 self 和 data 参数（第 2 行）。每个节点包含 data 和 next 两部分。我们将 self.data 设置为传入的 data 值（第 3 行），并将 self.next 初始化为 None（第 4 行）。后续在使用节点时会重新设置 next，但初始状态设为 None 即可。目前，Node 类就这些内容。

第 6 行定义了 LinkedList 类，在其构造函数中同样接收 self。第 8 行定义了 head 指针，它指向链表的第一个节点。初始时将其设为 None。

在完成类的定义后，下一节课我们将学习如何向链表中插入元素。