当前位置：首页 > 全部内容 > 正文

JavaScript数据结构与算法：链表实现详解

作者：半夏

时间：2026-10-29

浏览：578

本文深入解析JavaScript中链表数据结构的实现原理。从线性表的顺序存储缺陷出发，介绍链式存储的优势。详细阐述单链表、静态链表、循环链表及双向链表的定义与区别，并提供单链表和双向链表的完整JavaScript代码实现，包括节点的创建、插入、查找与删除操作，帮助开发者掌握链表的核心逻辑。

文章目录

链表概述与JavaScript中的实现基础

在JavaScript中，队列和栈属于特殊的线性表，通常基于数组这种顺序存储结构实现。得益于JavaScript解释器对数组的底层优化，数组没有固定长度的限制，这解决了其他语言中数组填满后难以添加或删除元素的问题。JavaScript通过push、pop、shift、unshift和split等方法，直接优化了数组元素的增删操作，无需像传统数组那样移动所有元素。

线性表的顺序存储结构存在一个显著缺点：修改任一元素的排列都会导致整个集合的变化，因为内存中数据是连续存储且无间隙的，删除元素后必须填补空缺。针对这一问题的优化方案是链式存储结构。这种结构不再关注数据的物理排列，而是通过在每个元素内部记录下一个元素的位置来实现连接。因此，这种用链接方式存储的线性表被称为链表，其核心构成是数据加上指向下一个节点的地址。

在链式结构中，所谓的“地址”也被称为“链”。每个数据单元构成一个节点，而链表本质上是由一组节点组成的集合。每个节点都包含一个数据块，并通过引用指向下一个节点，从而形成连接。

链表概述与JavaScript中的实现基础

数组元素依靠其在内存中的位置关系进行逻辑引用，而链表则依赖每个数据元保存的引用指针关系来进行连接和访问。

这种结构带来的优势非常明显：插入数据时完全无需关心数据的排列顺序，只需将“链”的指向正确衔接即可。

这种链表的设计思路不再局限于数组，我们可以利用对象来实现。只要对象之间存在引用关系，即可构建链表结构。

常见的链表类型包括单链表、静态链表、循环链表和双向链表。

单链表是最基础的形式，数据单向传递，每个节点仅记录下一个节点的信息。这类似于电影《无间道》中梁朝伟饰演的角色，通过中间人向上线和下线传递信息，一旦中间环节断裂，身份便无法证明，正如片尾所言：“我是好人，谁知道呢？”

静态链表是利用数组来描述的链表。在数组中，每个下标代表一个“节”，其中包含了数据和指向下一节的索引或地址。

循环链表是为了解决单链表只能向后传递的问题。在单链表中，到达尾部后若要回溯到首部会非常麻烦，因此将尾部节点的链指向头部节点，形成循环结构。

双向链表是对单链表的优化，使得每个节点都能知晓其前驱和后继节点。除了后指针域，还增加了前指针域，从而提高了查找效率。虽然这增加了设计的复杂度，但总体上是空间换时间的策略。

综上所述，链表是线性表中针对顺序存储结构的一种优化手段。但在JavaScript中，由于数组具有自动更新引用位置的特殊性，我们可以采用对象的方式来实现链表存储结构。

单链表的实现原理与代码

单链表

我们首先实现一个最简单的链表关系。


function createLinkList() {
  var _this = {},
    prev = null;
  return {
    add: function(val) {
      //保存当前的引用
      prev = {
        data: val,
        next: prev || null
      }
    }
  }
}
var linksList = createLinkList(); 
linksList.add("arron1"); 
linksList.add("arron2"); 
linksList.add("arron3");
//node节的next链就是 -arron3-arron2-arron1

通过node对象的next属性直接引用下一个node对象，初步实现了链表的引用机制。这种链式思路在jQuery的异步deferred中的then方法，以及日本开发者cho45的jsdeferre库中均有应用。该实现的关键问题在于，如何动态地将数据插入到当前执行节点之后？

因此，我们需要设计一个遍历方法，用于搜索node链上的数据，找到对应的节点后将新节点插入当前链中，并更新位置记录。


//在链表中找到对应的节
var findNode = function createFindNode(currNode) {
  return function(key){
    //循环找到执行的节，如果没有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

这是一个查找当前节点的方法，通过传递原始的头部headNode节点，一直向下查找next，直到找到对应的节点信息。

这里使用了curry（柯里化）方法来实现查找逻辑。

在插入节点时，针对链表地址的换算关系如下处理。

假设存在a-b-c-d的链表，如果要在c节点（c.next指向d）后面插入一个f节点。

插入后的链表变为a-b-c-f-d。此时需要将c.next指向f，并将f.next指向d。

通过insert方法增加节点。


//创建节
function createNode(data) {
  this.data = data;
  this.next = null;
}
//初始化头部节
//从headNode开始形成一条链条
//通过next衔接
var headNode = new createNode("head");

//在链表中找到对应的节
var findNode = function createFindNode(currNode) {
  return function(key){
    //循环找到执行的节，如果没有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

//插入一个新节
this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(key);
  //插入新的接，更改引用关系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
};

首先分离出createNode的构建逻辑。在初始化时，先创建一个头部节点对象，作为链表开头的初始化对象。

在insert增加节点的方法中，通过对headNode链进行查找，找到对应的节点，将新节点添加之后，最后修改链的关系。

如何从链表中删除一个节点？

由于链表的特殊性，假设链表为a->b->c->d，如果要删除c节点，就必须修改b.next指向c为b.next指向d。因此，需要找到前一个节点并修改其链表next地址，这类似于DOM操作中removeChild找到父节点调用移除子节点。

同样，在remove方法的设计中，需要设计一个遍历逻辑，向上回溯找到前一个父节点即可。


//找到前一个节
var findPrevious = function(currNode) {
  return function(key){
    while (!(currNode.next == null) &&
      (currNode.next.data != key)) {
      currNode = currNode.next;
    }
    return currNode;      
  }
}(headNode);

//插入方法
this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
    //修改链表关系
    prevNode.next = prevNode.next.next;
  }
};

测试代码：


<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">
 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
 }

 //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的节
 var findNode = function createFindNode(currNode) {
  return function(key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);

 //找到前一个节
 var findPrevious = function(currNode) {
  return function(key) {
  while (!(currNode.next == null) &&
   (currNode.next.data != key)) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);


 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(key);
  //插入新的接，更改引用关系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
 };

 //插入方法
 this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
  //修改链表关系
  prevNode.next = prevNode.next.next;
  }
 };


 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }

</script>

双向链表的优化与实现

双链表

原理与单链表相同，只不过给每个节点增加了一个前链表的指针。

链表概述与JavaScript中的实现基础

增加节点


//插入一个新节
this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
};

删除节点


this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next     = null;
    currNode.previous   = null;
  }
};

在删除操作中有一个明显的优化：不需要找到父节点了，因为双链表具有双向引用，所以效率比单链表要高。

测试代码：


<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">

 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
  this.previous = null
 }

   //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的数据
 var findNode = function(currNode, key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
  currNode = currNode.next;
  }
  return currNode;
 }

 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
 };

 this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
  currNode.previous.next = currNode.next;
  currNode.next.previous = currNode.previous;
  currNode.next     = null;
  currNode.previous   = null;
  }
 };

 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }


</script>

git代码下载：https://github.com/JsAaron/data_structure.git

实用工具推荐

电子包浆

绿化、压缩、噪点和虚拟水印，自由调节做旧程度。

使用 ›
图片压缩

选择画质和输出格式，预览压缩前后的大小。

使用 ›
作者最新文章

JavaScript闭包与类(Class)的区别及适用场景对比

JavaScript入门要学ES6吗？let与箭头函数等新特性解析

JavaScript 8种数据类型详解：基本类型与引用类型的区别

怎么在JavaScript中使用async/await优化Ajax异步流程

JavaScript replace回调函数实现动态正则替换逻辑

相关文章
热门文章
更多
CSS text-transform与JS修改首字母大写的适用场景区别
JS中constructor属性判断数组存在哪些风险
JS正则替换中$1捕获组引用与字符串重组技巧
全栈开发中JavaScript与Java怎么协作？前后端技术栈配合解析
Node.js后端生成高强度随机字符串的方法
怎么在本地运行JavaScript脚本：Node.js下载安装与环境配置教程
JS正则表达式基础：字面量与RegExp构造函数的区别及常用元字符
JS 解压出现乱码或报错怎么解决？
JavaScript常见SyntaxError语法错误排查与修复方法
JavaScript实现按钮点击冷却时间的完整代码示例