本文详细解析如何使用 JavaScript 实现链表数据结构。从 Node 节点类的定义出发，逐步演示 LinkNodeList 类的构建，涵盖 push、insert、getVal、remove 及 toString 等核心方法的逻辑与代码实现，帮助开发者深入理解链表的内存分配与指针操作机制。
链表的基本概念
根据《算法第四版》的定义，链表是一种递归数据结构：它要么为空（null），要么是一个指向节点（node）的引用，该节点包含一个泛型元素以及指向另一条链表的引用。如果这听起来有些抽象，我们可以用更通俗的方式解释。
我们熟悉数组，在存储多个元素时，数组是最常见的选择。但数组的大小是固定的，若要在数组中随意插入或删除元素，往往需要移动其他元素，这种操作的开销较高。
链表由有序元素组成，与数组不同，链表中的元素在内存中并非连续存放。每个元素由一个存储数据本身的节点和一个指向下一个元素的引用（即指针或链接）构成。因此，链表在添加或删除元素时，无需移动其他元素，具有更高的灵活性。
在查找方面，数组可以通过索引直接访问任意位置的元素，而链表必须从起点开始遍历，直到找到目标元素。下面通过一张示意图来直观展示链表的结构：
使用 JavaScript 实现链表
接下来，我们将使用 JavaScript 代码实现一个链表。在刷 LeetCode 链表相关题目时，你可能会经常看到类似这样的代码片段：
这部分代码用于创建链表中的每个节点，这里我们使用 ES6 的类（class）语法来实现。
Node 类定义
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
链表类的构建
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
}
head 属性表示链表的头节点，count 属性记录链表中节点的数量。我们需要实现哪些具体方法呢？
- push(element)：向链表尾部添加一个新元素。
- insert(element, position)：在链表的指定位置插入一个新元素。
- getVal(index)：返回指定位置的元素值。如果该位置不存在，则返回 undefined。
- remove(position)：从链表的指定位置移除一个元素。
- isEmpty()：如果链表为空，返回 true；如果链表长度大于 0，返回 false。
- size()：返回链表中包含的元素个数，类似于数组的 length 属性。
- toString()：返回表示整个链表的字符串形式。
size 方法实现
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
···
size() {
return this.count;
}
···
}
利用 count 属性记录节点数量，直接返回 count 即可获取链表大小。
isEmpty 方法实现
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
···
isEmpty() {
return this.size() === 0;
}
···
}
只需判断 size() 的返回值是否为 0 即可确定链表是否为空。
push 方法实现
向链表尾部添加一个新元素。
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
···
push(element) {
const node = new Node(element);
if (this.head === null) {
this.head = node;
} else {
let current; = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.count++;
}
···
}
要在链表尾部添加元素，首先需通过 Node 类创建新节点。如果当前 head 不存在，说明链表为空，直接将 head 指向新节点即可。否则，遍历找到链表的最后一个节点，将其 next 指向新节点，并将 count 加 1。
getVal 方法实现
获取指定位置的元素值。
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
···
getVal(index) {
if (index > 0 && index <= this.count) {
let node = this.head;
for (let i = 0; i < index; i++) {
node = node.next;
}
return node;
}
return undefined;
}
···
}
接收要查找的位置索引，首先判断该位置是否有效。如果无效，直接返回 undefined。
若位置有效，则从头节点开始循环遍历，直到找到目标索引对应的节点。循环结束时，node 即为该位置元素的引用。
insert 方法实现
在链表的指定位置插入一个新元素。
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
···
insert(ele, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(ele);
if (index === 0) {
const current = this.head;
node.next = current;
this.head = node;
} else {
const prev = this.getVal(index - 1);
node.next = prev.next;
prev.next = node;
}
this.count++;
return true;
}
return false;
}
···
}
首先判断插入位置是否有效，若无效则直接返回 false，表示插入失败。
若位置有效，则创建新节点。如果插入位置为 0（即头节点），需将新节点的 next 指向当前头节点，并将 head 更新为新节点。
若插入位置在其他地方，需获取插入位置的前一个节点 prev，将新节点的 next 指向 prev 的下一个节点，然后将 prev 的 next 重新指向新节点。
只要插入操作有效，都需要对 count 进行更新。
remove 方法实现
从链表中移除一个元素。
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
···
remove(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
// 移除第一项
if (index === 0) {
this.head = current.next;
} else {
const prev = this.getVal(index - 1);
current = prev.next;
prev.next = current.next;
}
this.count--;
return current.val;
}
return undefined;
}
···
}
首先判断要移除的位置是否有效，若无效则返回 undefined。
如果移除的是第一个节点，直接将 head 指向下一个节点即可。
如果移除的是其他位置的节点，需获取该位置的前一个节点 prev，将 prev 的 next 指向当前节点的下一个节点（即 current.next）。
只要移除操作有效，都需要对 count 进行更新。
toString 方法实现
返回表示整个链表的字符串。由于列表项使用了 Node 类，需要重写继承自 JavaScript 对象默认的 toString 方法，使其仅输出元素的值。
class LinkNodeList {
constructor() {
this.head = null;
this.count = 0;
}
···
toString() {
if (this.head === null) {
return "";
}
let objString = `${this.head.val}`;
let current = this.head.next;
for (let i = 1; i < this.size() && current !== null; i++) {
objString = `${objString}=>${current.val}`;
current = current.next;
}
return objString;
}
···
}
如果 head 不存在，说明是空链表，直接返回空字符串。
接下来，将链表的每个元素通过“=>”符号拼接成字符串。下面查看实际运行效果。
以上即为使用 JavaScript 实现链表数据结构的详细代码解析，更多关于 JS 链表实现的资料，请关注本站其他相关文章！