JavaScript 链表实现详解：单向、双向与循环链表

作者：小括号时间：2026-10-23 10:20:30浏览：319

本文深入解析 JavaScript 中链表数据结构的实现原理与代码编写。详细讲解单向链表的节点插入、删除与查找逻辑，并扩展至双向链表与循环链表的构建方法。通过 Node 与 LinkedList 类的具体实现，展示如何在 JS 中高效处理线性数据结构，适用于算法学习与底层原理掌握。

本文通过具体实例，详细阐述 JavaScript 中链表（Linked-list）算法与数据结构的实现方式，供开发者参考学习。

链表（Linked-list）

此前我们探讨了利用栈和队列存储数据的方法，它们本质上属于列表的一种，其底层数据存储结构均基于数组。

然而，数组并非在所有场景下都是最优选择。在许多编程语言中，数组长度固定，一旦数据填满，新增元素将变得极其困难。此外，数组在执行删除或添加操作时，往往需要平移其他元素，导致操作繁琐且效率低下。

相比之下，JavaScript 中的数组因实现为对象而避免了上述长度限制问题，但在与 C 或 Java 等语言对比时，其运行效率仍相对较低。

因此，我们可以考虑使用链表（Linked-list）作为替代方案。除了随机访问性能不如数组外，链表在绝大多数一维数组适用的场景中表现优异。特别是在 C 或 Java 等高级语言中，链表的优势更为明显。

链表存在多种类型，包括单向链表、双向链表、单向循环链表和双向循环链表。本文将重点基于对象实现应用最广泛的单向链表。

链表的定义

在实现链表之前，必须理解其基本概念，这是至关重要的一步。

链表是由一组节点构成的集合，每个节点通过一个对象引用来指向其后继节点，这种引用关系被称为“链”。为了便于理解，下面展示了一个简单的链接结构示意图。

链表（Linked-list）链表结构图

图中，data 字段保存节点数据，next 字段保存指向下一个节点的引用。需要注意的是，图中描述 data2 位于 data1 之后，而非表示它是链表的第二个元素。此外，链表的尾元素指向 null，标志着链表的结束。

由于确定链表起始点较为复杂，许多实现会在链表最前端添加一个特殊节点，称为头节点（Head Node），用于标识链表头部。改造后的链表结构如下所示。

链表（Linked-list）有头节点的链表

向链表插入节点效率较高，只需修改前驱节点使其指向新节点，并让新节点指向原前驱节点原本指向的节点即可。下面通过图片演示如何在 data2 节点后插入 data4 节点。

链表（Linked-list）插入节点

同样，从链表中删除节点也相对简单。只需将待删节点的前驱节点指向待删节点的后继节点，并将待删节点的 next 置为 null，即可完成删除。下面演示如何删除 data4 节点。

链表（Linked-list）删除节点

链表的设计

我们设计包含两个类：Node 类用于表示节点，LinkedList 类（或 LList）提供插入、删除等操作接口。

Node 类

Node 类包含两个属性：element 用于保存节点数据，next 用于保存指向下一节点的链接。具体实现如下。


//节点
function Node(element) {
  this.element = element;  //当前节点的元素
  this.next = null;     //下一个节点链接
}

LinkedList 类

LinkedList 类提供链表操作接口，包括插入、删除节点及查找指定值等。该类仅有一个属性，即使用一个 Node 对象保存链表的头节点。

其构造函数实现如下：


//链表类
function LList () {
  this.head = new Node( 'head' );   //头节点
  this.find = find;          //查找节点
  this.insert = insert;        //插入节点
  this.remove = remove;        //删除节点
  this.findPrev = findPrev;      //查找前一个节点
  this.display = display;       //显示链表
}

head 节点的 next 属性初始化为 null，当有新元素插入时，next 将指向新元素。

接下来，我们查看具体方法的实现细节。

insert：向链表插入一个节点

首先分析 insert 方法，插入节点需明确插入位置（某节点前或后）。我们先探讨如何在已知节点后插入新节点。

要在已知节点后插入，首先需定位该节点。为此，我们需要一个 find 方法遍历链表以查找指定数据。若找到，该方法返回保存该数据的节点。我们先实现 find 方法。

find：查找给定节点


//查找给定节点

function find ( item ) {
  var currNode = this.head;
  while ( currNode.element != item ){
    currNode = currNode.next;
  }
  return currNode;
}

find 方法展示了在链表上移动的逻辑。首先创建新节点并将头节点赋值给它，然后循环遍历链表。若当前节点的 element 属性与目标信息不符，则移动到下一节点；若查找成功，返回包含该数据的节点；否则返回 null。

找到目标节点后，即可插入新节点：将新节点的 next 属性设置为原节点 next 属性的值，然后设置原节点的 next 属性指向新节点。具体实现如下。


//插入节点

function insert ( newElement , item ) {
  var newNode = new Node( newElement );
  var currNode = this.find( item );
  newNode.next = currNode.next;
  currNode.next = newNode;
}

现在我们可以测试链表。在此之前，我们先定义一个 display 方法来显示链表元素，以验证结果是否正确。

display：显示链表


//显示链表元素

function display () {
  var currNode = this.head;
  while ( !(currNode.next == null) ){
    console.log( currNode.next.element );
    currNode = currNode.next;
  }
}

实现原理同上，将头节点赋值给新变量，然后循环链表，直到当前节点的 next 属性为 null 时停止。在循环过程中打印每个节点的数据即可。


var fruits = new LList();

fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');

console.log(fruits.display());    // Apple
                   // Banana
                   // Pear

remove：从链表中删除一个节点


从链表中删除节点时，我们先要找个待删除节点的前一个节点，找到后，我们修改它的 next 属性，使其不在指向待删除的节点，而是待删除节点的下一个节点。那么，我们就得需要定义一个 findPrevious 方法遍历链表，检查每一个节点的下一个节点是否存储待删除的数据。如果找到，返回该节点，这样就可以修改它的 next 属性了。 findPrevious 的实现如下：

//查找带删除节点的前一个节点

function findPrev( item ) {
  var currNode = this.head;
  while ( !( currNode.next == null) && ( currNode.next.element != item )){
    currNode = currNode.next;
  }
  return currNode;
}

基于上述逻辑，remove 方法的实现便水到渠成。


//删除节点

function remove ( item ) {
  var prevNode = this.findPrev( item );
  if( !( prevNode.next == null ) ){
    prevNode.next = prevNode.next.next;
  }
}

我们编写一段测试程序来验证 remove 方法：


// 接着上面的代码，我们再添加一个水果

fruits.insert('Grape' , 'Pear');
console.log(fruits.display());   // Apple
                  // Banana
                  // Pear
                  // Grape

// 我们把香蕉吃掉

fruits.remove('Banana');
console.log(fruits.display());   // Apple
                  // Pear
                  // Grape

Great！测试成功，至此你已经实现了一个基本的单向链表。

双向链表

虽然从链表头节点正向遍历很简单，但反向遍历却较为困难。我们可以通过给 Node 类增加 previous 属性，使其指向前驱节点，从而形成双向链表，如下图所示。

链表（Linked-list）双向链表

此时，插入节点需同时修改前驱和后继关系，但删除节点的效率得到提升，因为不再需要专门查找待删除节点的前驱节点。

双向链表的实现

实现双向链表首先需给 Node 类增加 previous 属性：


//节点类

function Node(element) {
  this.element = element;  //当前节点的元素
  this.next = null;     //下一个节点链接
  this.previous = null;   //上一个节点链接
}

双向链表的 insert 方法与单链表相似，但需设置新节点的 previous 属性以指向其前驱节点。定义如下：


//插入节点
function insert ( newElement , item ) {
  var newNode = new Node( newElement );
  var currNode = this.find( item );
  newNode.next = currNode.next;
  newNode.previous = currNode;
  currNode.next = newNode;
}

双向链表的 remove 方法比单链表更高效，无需查找前驱节点。只需找到待删除节点，将其前驱节点的 next 指向待删除节点的后继，并将后继节点的 previous 指向待删除节点的前驱即可。定义如下：


//删除节点

function remove ( item ) {
  var currNode = this.find ( item );
  if( !( currNode.next == null ) ){
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next = null;
    currNode.previous = null;
  }
}

此外还有反向显示链表（dispReverse）、查找最后一个元素（findLast）等方法，相信读者已具备相关思路。这里提供基本双向链表的完整代码供参考。


 //节点
 
function Node(element) {
  this.element = element;  //当前节点的元素
  this.next = null;     //下一个节点链接
  this.previous = null;     //上一个节点链接
}

//链表类

function LList () {
  this.head = new Node( 'head' );
  this.find = find;
  this.findLast = findLast;
  this.insert = insert;
  this.remove = remove;
  this.display = display;
  this.dispReverse = dispReverse;
}

//查找元素

function find ( item ) {
  var currNode = this.head;
  while ( currNode.element != item ){
    currNode = currNode.next;
  }
  return currNode;
}

//查找链表中的最后一个元素

function findLast () {
  var currNode = this.head;
  while ( !( currNode.next == null )){
    currNode = currNode.next;
  }
  return currNode;
}


//插入节点

function insert ( newElement , item ) {
  var newNode = new Node( newElement );
  var currNode = this.find( item );
  newNode.next = currNode.next;
  newNode.previous = currNode;
  currNode.next = newNode;
}

//显示链表元素

function display () {
  var currNode = this.head;
  while ( !(currNode.next == null) ){
    console.debug( currNode.next.element );
    currNode = currNode.next;
  }
}

//反向显示链表元素

function dispReverse () {
  var currNode = this.findLast();
  while ( !( currNode.previous == null )){
    console.log( currNode.element );
    currNode = currNode.previous;
  }
}

//删除节点

function remove ( item ) {
  var currNode = this.find ( item );
  if( !( currNode.next == null ) ){
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next = null;
    currNode.previous = null;
  }
}

var fruits = new LList();

fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');
fruits.insert('Grape' , 'Pear');

console.log( fruits.display() );    // Apple
                    // Banana
                    // Pear
                    // Grape
                    
console.log( fruits.dispReverse() );  // Grape
                    // Pear
                    // Banana
                    // Apple

循环链表

循环链表与单链表相似，节点类型一致，唯一区别在于创建循环链表时，头节点的 next 属性指向其自身，即：


head.next = head;

这种行为导致链表中每个节点的 next 属性都指向头节点，即尾节点指向头节点，形成循环结构，如下图所示。

链表（Linked-list）循环链表

原理已明，此处不再赘述代码，相信读者能独立完成实现。

至此，我们对链表有了深入理解。为使链表功能更完善，读者可发挥创意，添加向前/向后移动节点、显示当前节点等方法，共同进步。

感兴趣的朋友可使用在线 HTML/CSS/JavaScript 代码运行工具：http://tools.jb51.net/code/HtmlJsRun 测试上述代码运行效果。

更多关于 JavaScript 相关内容感兴趣的读者可查看本站专题：《JavaScript 数学运算用法总结》、《JavaScript 数据结构与算法技巧总结》、《JavaScript 数组操作技巧总结》、《JavaScript 排序算法总结》、《JavaScript 遍历算法与技巧总结》、《JavaScript 查找算法技巧总结》及《JavaScript 错误与调试技巧总结》

希望本文所述对大家 JavaScript 程序设计有所帮助。

作者最新文章

JS语法错误会阻止加载吗？区分SyntaxError与资源加载失败

2026-11-05 16:08:46

JavaScript常见SyntaxError语法错误排查与修复方法

2026-11-05 13:58:44

JS中slice、substring和substr截取字符串的区别

2026-11-05 13:43:47

JS 转 TS 手动迁移最佳实践：从配置 tsconfig 到消除 any 类型

2026-11-05 11:53:32

为什么JS数组push后得到的是数字而不是数组？

2026-11-05 09:59:18