单链表（SLL）

简介

链表是 C++ 中一种由 节点 连接而成的数据结构，形如一条链条。每个节点包含数据以及指向列表中下一个节点的指针。其中，每个节点仅有一个指针用于存储对下一个元素的引用，这种链表称为 单向链表（Singly Linked List, SLL）。下图展示了一个单向链表的结构。

如图所示，由于没有反向指针，链表只能单向连接，即整个链表只朝一个方向延伸，无法回溯。这也是它被称为“单向”链表的原因。

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

• Node 类
• LinkedList 类

我们将逐一进行讲解。

Node 类

Node 类包含两个组成部分：

• 数据
• 指针

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

指针 用于指向链表中的下一个节点，是实现节点之间连接的关键。

以下是一个存储整数的典型 Node 类定义：

1class Node {
2public: 
3  int data; // 存储的数据（可以是 int、string、对象等）
4  Node* nextElement;  // 指向下一个节点的指针
5
6  Node() {
7    // 构造函数，初始化新创建节点的 nextElement
8    nextElement = nullptr;   
9  }
10};

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

LinkedList 类

链表本身是由多个 Node 对象组成的集合。为了跟踪链表的结构，我们需要一个指向链表第一个节点的指针。

这就是 头指针（head pointer）的作用。头指针指向链表的起始位置。因此，对于链表的任何操作，我们都必须从头指针开始遍历，直到到达目标节点。

以下是 LinkedList 类的实现：

1class LinkedList {
2public:
3  Node* head;  // 指向链表开头的指针
4
5  LinkedList() {
6    head = nullptr;
7  }
8};

说明： 实现非常简单。初始状态下，链表为空，不包含任何节点。head 指针的值为 nullptr，表示它当前不指向任何节点。

---

接下来，我们将介绍标准 LinkedList 类中常见的各种功能函数。