单链表（SLL）

引言

到目前为止，我们已经了解了数组如何存储和组织数据。JavaScript 并没有内置的链表结构。

然而，掌握链表知识在编程面试中非常有用！在本节中，我们将介绍链表的基本行为，并展示如何用 JavaScript 语法实现链表。让我们开始吧！

单向链表的结构

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

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

每个节点包含数据以及一个指向列表中下一个节点的指针。由于没有反向指针，说明这种链接是单向的，即整个链表只朝一个方向延伸，无法反向遍历。这也是它被称为“单向链表”的原因。

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

• Node 类
• LinkedList 类

接下来我们将逐一讨论这两个类。

1. Node 类

Node 类包含两个部分：

• 数据（data）
• 指针（nextElement）

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

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

以下是典型的 Node 类定义：

1class Node {
2  constructor(data) {
3    this.data = data;
4    this.nextElement = null;
5  }
6}

说明： 如前所述，Node 类有两个属性。data 存储你指定的值，nextElement 是指向链表中下一个元素的指针。

2. LinkedList 类

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

这就引入了头节点（head）的概念。头节点不存储任何数据，仅用于指向链表的起始位置。这意味着，对于链表的任何操作，我们都必须从头节点（即链表起点）开始遍历，才能到达目标节点。

下面是 LinkedList 类的实现：

1class LinkedList {
2  constructor() {
3    // head 指向链表的头部
4    this.head = null;
5  }
6}

说明： 实现非常简单。初始时，链表为空，因此其头指针指向 null。当链表中加入元素后，我们会看到 head 开始指向链表的第一个节点。