简介

到目前为止，我们已经了解了列表如何为我们存储和组织数据。Python 并没有内置的链表结构，因为在引入列表之后，链表不再是必需的。

然而，在编程面试中，掌握链表的相关知识非常有用！在本节中，我们将介绍链表的基本行为，并演示如何使用 Python 语法实现它们。这也将加深你对 Python 底层机制的理解。

让我们开始吧！

单向链表的结构

链表数据结构最基础的形式是单向链表。首先，让我们来看一下它的基本结构：

如上图所示，链表由一个个节点连接而成，形如链条。

每个节点包含数据以及一个指向链表中下一个节点的指针。由于没有反向指针，这种结构形成的是单向连接，即整个链表只能沿一个方向遍历，无法回溯。因此被称为单向链表。

如果你目前感觉有些困惑，也不必担心。现阶段，你只需要关注实现单向链表所需的两个类：

• 节点类（Node Class）
• 链表类（LinkedList Class）

接下来我们逐一介绍。

1. 节点类（Node Class）

节点类包含两个部分：

• 数据（Data）
• 指针（Pointer）

数据是你希望存储在节点中的值，可以类比为列表中某个索引位置上的元素。其数据类型可以是字符串、整数，甚至是用户自定义的类。

指针用于指向链表中的下一个节点，是维持链表连接的关键。

注意：这里的“指针”实际上是一个 Node 类型的变量。

以下是 Node 类的一个典型定义：

Node.py

1class Node:
2    def __init__(self, data):
3        self.data = data  # 数据域
4        self.next_element = None  # 指向下一个节点的指针

说明：如前所述，Node 类有两个成员变量。data 存储用户指定的值，next_element 是指向链表中下一个节点的指针。

2. 链表类（LinkedList Class）

链表本身是由上述 Node 对象组成的集合。为了追踪整个链表，我们需要一个指向链表第一个节点的指针。

这就引出了**头节点（head）**的概念。头节点不存储实际数据，仅作为指向链表起始位置的入口。这意味着，对链表进行任何操作时，我们都必须从头节点（链表起点）开始遍历，才能访问到目标节点。

LinkedList 类的实现如下所示：

LinkedList.py

1class LinkedList:
2    def __init__(self):
3        self.head_node = None  # 指向第一个节点的指针

说明：该实现非常简单。当链表首次被创建时，它不包含任何节点，因此头节点初始化为 None。

现在我们已经介绍了基本实现，接下来将讨论链表与列表之间的区别。