当前位置：首页 > 全部内容 > JavaScript 数据结构之链表的实现：单向、双向与循环链表详解

JavaScript 数据结构之链表的实现：单向、双向与循环链表详解

作者：纸飞机时间：2026-10-21 23:50:58浏览：160

本文详细讲解 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&&currentNode.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&&currentNode.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

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持本站！

作者最新文章

JS动态构建复杂嵌套JSON对象的方法

2026-11-05 15:41:52

JS负数取余为什么是负数？详解余数与模运算区别

2026-11-05 13:34:41

JS 解压出现乱码或报错怎么解决？

2026-11-05 12:32:38

JS 中 startsWith、indexOf 与正则判断字符串前缀的对比

2026-11-04 22:19:43

JS解析Excel后怎么将数据转换为JSON格式

2026-11-04 20:58:28