本文详细讲解 JavaScript 中链表数据结构的实现方法，涵盖单向链表、双向链表及循环链表的核心原理与代码实现。通过 Node 类与 LinkedList 类的定义，深入解析 insert、remove、find 等关键方法的逻辑，并对比数组在增删操作上的性能差异，帮助开发者掌握动态存储分配技巧及不同链表结构的适用场景。
链表与数组的性能对比
此前已分别探讨过基于数组实现的栈与队列数据结构。然而，数组并非在所有场景下都是最优选择，例如在数组中插入或删除元素时，往往需要移动其他元素以填补空隙。相比之下，JavaScript 中的 splice() 方法虽能避免直接访问其他元素，但在特定性能需求下，若发现数组操作效率低下，则应考虑使用链表结构。
链表的基本概念
链表的概念
链表是一种常见且支持动态存储分配的数据结构。它包含一个名为 head 的“头指针”变量，该变量存储一个地址，指向链表的第一个元素。链表中的每个节点都通过一个对象引用指向其后继节点，这种指向关系被称为“链”。
与依赖下标（位置索引）引用元素的数组不同，链表元素通过节点间的相互关系进行引用。因此，链表的插入操作具有较高的效率。下图演示了在链表中插入节点 d 的具体过程：
删除过程：
基于对象的单向链表实现
基于对象的链表
我们将定义两个类：Node 类用于表示节点数据，LinkedList 类用于封装操作链表的各种方法。
首先观察 Node 类的定义：
function Node(element){
this.element = element;
this.next = null;
}其中，element 属性用于保存节点上的数据，next 属性用于保存指向下一个节点的链接。
接下来是 LinkedList 类的定义：
function LinkedList(){
this.head = new Node('head');
this.find = find;
this.insert = insert;
this.remove = remove;
this.show = show;
}
find() 方法从头节点开始，沿着链表的节点逐一查找，直到找到 element 内容与 item 相等的节点并返回该节点；若未找到，则返回 null。
function find(item){
var currentNode = this.head;//从头结点开始
while(currentNode.element!=item){
currentNode = currentNode.next;
}
return currentNode;//找到返回结点数据，没找到返回null
}Insert 方法。通过前文插入演示可知，实现插入操作主要包含以下四步：
1、创建新节点
2、找到目标节点（即插入位置的前驱节点）
3、修改目标节点的 next 指向链接
4、将目标节点的 next 值赋值给要插入的新节点的 next 属性
function insert(newElement,item){
var newNode = new Node(newElement);
var currentNode = this.find(item);
newNode.next = currentNode.next;
currentNode.next = newNode;
}Remove() 方法。删除某一节点前，需要先找到被删除节点的前驱节点。为此，我们定义 frontNode() 辅助方法：
function frontNode(item){
var currentNode = this.head;
while(currentNode.next.element!=item&¤tNode.next!=null){
currentNode = currentNode.next;
}
return currentNode;
}简要步骤如下：
1、创建节点（此处指定位逻辑）
2、找到目标节点的前驱节点
3、修改前驱节点的 next 指向被删除节点的下一个节点
function remove(item){
var frontNode = this.frontNode(item);
//console.log(frontNode.element);
frontNode.next = frontNode.next.next;
}Show() 方法：
function show(){
var currentNode = this.head,result;
while(currentNode.next!=null){
result += currentNode.next.element;//为了不显示head结点
currentNode = currentNode.next;
}
}测试程序：
var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());输出：
双向链表的实现与反序遍历
双向链表
从链表头节点遍历到尾节点相对简单，但有时我们需要从后向前遍历。此时，可以通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接来实现。下图展示了双向链表的工作原理：
首先，我们在 Node 类中增加 front 属性：
function Node(element){
this.element = element;
this.next = null;
this.front = null;
}当然，相应的 insert() 方法和 remove() 方法也需要进行相应修改：
function insert(newElement,item){
var newNode = new Node(newElement);
var currentNode = this.find(item);
newNode.next = currentNode.next;
newNode.front = currentNode;//增加front指向前驱结点
currentNode.next = newNode;
}
function remove(item){
var currentNode = this.find(item);//找到需要删除的节点
if (currentNode.next != null) {
currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
currentNode.next = null;//并设置前驱与后继的指向为空
currentNode.front = null;
}
}
反序显示链表：
需要给双向链表增加一个方法，用于查找最后一个节点。findLast() 方法定位链表中的最后一个节点，从而避免从前往后遍历以获取尾部信息。
function findLast() {//查找链表的最后一个节点
var currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
return currentNode;
}实现反序输出：
function showReverse() {
var currentNode = this.head, result = "";
currentNode = this.findLast();
while(currentNode.front!=null){
result += currentNode.element + " ";
currentNode = currentNode.front;
}
return result;
}测试程序：
var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());输出：
循环链表的特性与实现
循环链表
循环链表是另一种形式的链式存储结构。其特点是表中最后一个节点的指针域指向头节点，从而使整个链表形成一个环。循环链表与单向链表相似，节点类型一致，唯一区别在于创建循环链表时，头节点的 next 属性指向其自身，即：
head.next = head
这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。下图表示循环链表的结构：
修改构造方法：
function LinkedList(){
this.head = new Node('head');//初始化
this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
this.find = find;
this.frontNode = frontNode;
this.insert = insert;
this.remove = remove;
this.show = show;
}此时需注意链表的输出方法 show() 与 find() 方法。原有的逻辑在循环链表中会导致死循环，因此 while 循环的终止条件需修改为当循环回到头节点时退出。
function find(item){
var currentNode = this.head;//从头结点开始
while(currentNode.element!=item&¤tNode.next.element!='head'){
currentNode = currentNode.next;
}
return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
var currentNode = this.head,result = "";
while (currentNode.next != null && currentNode.next.element != "head") {
result += currentNode.next.element + " ";
currentNode = currentNode.next;
}
return result;
}测试程序：
var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());测试结果：
本文用到的示例代码地址：https://github.com/LJunChina/JavaScript
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持本站！