单链表（SLL）

简介

“链表”是 C# 中另一种数据结构，由称为 节点 的元素按链条形式连接而成。每个节点包含数据以及指向列表中下一个节点的地址。在一种特定类型的链表中，每个节点仅有一个指针，用于存储对下一个元素的引用，这种链表被称为 单向链表（Singly Linked List, SLL）。下图展示了一个单向链表的结构。

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

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

• Node 类
• LinkedList 类

我们将逐一介绍这两个类。

Node 类

Node 类包含两个组成部分：

• 数据
• 地址

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

地址 指向链表中的下一个节点，是保证节点之间连接的关键。

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

1class Node {
2public: 
3  int data; // 要存储的数据（可以是 int、string、object 等）
4  Node nextElement;  // 指向下一个元素的地址
5
6  Node() {
7    // 构造函数，用于初始化新创建节点的 nextElement
8    nextElement = null;   
9  }
10}

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

LinkedList 类

链表本身是由多个节点对象组成的集合，这些节点已在前文定义。为了跟踪链表，需要一个指向链表第一个节点的指针。

这就是 头指针（head pointer）概念的意义所在。“头指针”指向链表的起始位置。这意味着，对于链表的任何操作，都必须从头开始遍历，才能到达目标节点。

以下是 LinkedList 类的实现：

1class LinkedList {
2public:
3  Node head;  // 指向链表的起始位置
4
5  LinkedList() {
6    head = null;
7  }
8};

说明： 实现非常简单。初始状态下，链表为空，即不包含任何节点。此时 head 指针的值为 null，表示它不指向任何内容。