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

JavaScript 单向链表与双向链表实现详解

作者：异步漫步

时间：2026-10-29

浏览：359

本文详细讲解 JavaScript 中链表数据结构的实现，涵盖单向链表与双向链表的核心概念及代码实现。内容涉及节点构造函数、append、insert、remove 等关键方法的逻辑推导与具体编码，对比数组优势，并提供完整的单向及双向链表操作示例，帮助开发者掌握动态内存管理与指针操作技巧。

文章目录

链表简介

链表简介

链表是一种基础的线性数据结构，其存储方式不同于数组的连续内存分配。在链表中，数据并非按物理顺序紧密排列，而是通过每个节点中存储的指向下一个节点的指针（引用）来建立逻辑连接。这种结构允许程序灵活利用内存空间，避免了数组需要提前声明固定长度所带来的资源浪费或溢出问题，特别适合动态数据管理场景。

单向链表

单向链表

作为链表最基础的形态，单向链表中的每个节点由两部分组成：一部分存储实际数据元素，另一部分存储指向后继节点的指针。链表的最后一个节点其指针域通常指向空值（NULL），标志着链表的结束。这种结构直观地体现了数据的前后关联关系。

JavaScipt中单向链表的实现

JavaScipt中单向链表的实现

实现单向链表的第一步是定义其构造函数，用于初始化链表的基本状态，包括头节点引用和长度计数。


/**
 * 单向链表构造函数
 */
function LinkedList() {
 /**
  * 单向链表中节点的构造函数
  * @param {Any} element 要传入链表的节点
  */
 var Node = function(element) {
  this.element = element;
  //下个节点的地址
  this.next = null;
 }

 //单向链表的长度
 var length = 0;
 //单向链表的头结点，初始化为NULL
 var head = null;
}

相较于栈或队列等线性结构，单向链表的构造函数实现更为复杂，因为它需要维护节点间的指针关系。一个完整的单向链表类通常需要提供以下核心操作方法：

  1. append(element): 添加元素到链表尾部
  2. insert(position,element): 向单向链表中某个位置插入元素
  3. indexOf(element): 寻找某个元素在单向链表的位置
  4. remove(element): 移除给定的元素
  5. removeAt(position): 移除单向链表中某个位置的元素
  6. getHead(): 获取单向链表的头部
  7. isAmpty(): 检查单向链表是否为空，为空则返回true
  8. toString(): 将链表所有内容以字符串输出
  9. size(): 返回单向链表长度

append方法:

该方法用于将新元素追加到链表的末尾。实现逻辑首先创建包含新数据的新节点，若链表为空则直接将该节点设为头节点；否则，遍历链表至最后一个节点（其 next 为 null），将最后一个节点的 next 指向新节点，并更新链表长度。


/**
 * 向单向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  // 当前项等于链表头部元素.
  // while循环到最后一个，从而将该节点加入链表尾部。
  current = head;
  // 当next为null时，判定为false。退出循环。
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

insert方法:

该方法用于在指定索引位置插入新元素。首先验证位置合法性（0 到 length 之间）。若插入位置为 0，则新节点的 next 指向当前头节点，并将头节点更新为新节点；否则，通过循环找到目标位置的前驱节点和后继节点，调整指针使新节点插入其中，最后增加长度并返回成功标识。


/**
 * 向单向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @param {Any} element 要插入的元素
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {
  var node = new Node(element);
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   node.next = current;
   head = node;
  } else {
   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

indexOf方法:

该方法用于查找指定元素在链表中的索引位置。从头部开始遍历，若当前节点的 element 与目标元素严格相等（===），则返回当前索引；若遍历结束未找到，则返回 -1。


/**
 * 寻找某个元素在单向链表中的位置
 * @param {Any} element 要寻找的元素
 * @return {Number}     返回值>=0则代表找到相应位置
 */
this.indexOf = function(element) {
 var current = head;
 var index = -1;

 while (current) {
  if (element === current.element) {
   return index;
  }
  index++;
  current = current.next;
 }

 return -1;
};

remove方法:

该方法用于移除链表中第一个匹配指定值的元素。其实现依赖于 indexOf 方法获取目标元素的索引，随后调用 removeAt 方法执行实际的移除操作并返回被移除的元素值。


/**
 * 移除给定的元素
 * @param {Any} element 要移除的元素
 * @return {Number}     返回值>=0表示移除成功
 */
this.remove = function(element) {
 var index = this.indexOf(element);
 return this.removeAt(index);
};

removeAt方法:

该方法用于移除指定索引位置的节点。首先验证索引范围。若移除的是头节点，则将 head 指针直接指向原 head 的 next 节点；否则，通过循环找到目标节点的前驱节点，将前驱节点的 next 指向目标节点的 next，从而跳过目标节点。操作完成后长度减 1，并返回被移除节点的数据。


/**
 * 移除单向链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}     移除成功返回被移除的元素，不成功则返回NULL
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   // 因为之前head指向第一个元素，现在把head修改为指向第二个元素。
   // 核心概念在于链表前后全靠指针链接，而非数组一般。
   // 所以只需要改变head的元素。
   head = current.next;
  } else {
   while (index++ < position) {
    // previous指要操作元素位置之前的那个元素，current表示之后的那个元素。
    previous = current;
    current = current.next;
   }

   previous.next = current.next;
  }

  length--;

  return current.element;
 } else {
  return null;
 }
};

getHead方法:

该方法用于获取链表的头节点引用，直接返回内部维护的 head 变量。


/**
 * 获取单向链表的头部
 * @return {Any} 单向链表的头部
 */
this.getHead = function() {
 return head;
}

isAmpty、toString、size方法

这些辅助方法分别用于检查链表是否为空（判断 head 是否为 null）、将链表内容转换为字符串表示（通常遍历节点拼接数据）以及返回当前链表的节点总数。


/**
 * 判断单向链表是否为空
 * @return {Boolean} 为空则返回true，不为空则返回false
 */
this.isAmpty = function() {
 return length === 0
};

/**
 * 将链表所有内容以字符串输出
 * @return {String} 要输出的字符串
 */
this.toString = function() {
 var current = head;
 var string = '';

 while (current) {
  string += current.element;
  current = current.next;
 }
 return string;
};

/**
 * 返回单向链表长度
 * @return {Number} 单向链表的长度
 */
this.size = function() {
 return length;
};

双向链表

双向链表

双向链表是对单向链表的扩展，其节点不仅包含指向后继节点的指针，还包含指向前驱节点的指针。这种双向链接结构使得从任意节点向前或向后遍历成为可能，增加了操作的灵活性，但同时也增加了内存开销和指针管理的复杂度。

JavaScipt中双向链表的实现

JavaScipt中双向链表的实现

双向链表的构造函数同样需要初始化头节点、尾节点（可选，用于优化尾部操作）以及长度变量，并定义节点结构以支持双向指针。


/**
 * 双向链表的构造函数
 */
function DoublyLinkedList() {
 /**
  * 双向链表中节点的构造函数
  * @param {Any} element 要传入链表的元素
  */
 var Node = function(element) {
  this.element = element;
  this.prev = null;
  this.next = null;
 }

 //双向链表的长度
 var length = 0;
 //双向链表的头结点，初始化为NULL
 var head = null;
 //双向链表的尾结点，初始化为NULL
 var tail = null;
}

双向链表需要提供以下核心方法以支持双向遍历和操作：

  1. append(element): 添加元素到双向链表尾部
  2. insert(position,element): 向双向链表中某个位置插入元素
  3. removeAt(position): 移除双向链表中某个位置的元素
  4. showHead(): 获取双向链表的头部
  5. showLength(): 获取双向链表长度
  6. showTail(): 获取双向链表的尾部

append方法:

该方法用于在双向链表尾部添加元素。创建新节点后，若链表为空，则初始化 head 和 tail；否则，将当前尾节点的 next 指向新节点，并将新节点的 prev 指向当前尾节点，最后更新 tail 为新节点。


/**
 * 向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 * @return {Any}     加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);

 if (head === null) {
  head = node;
  tail = node;
 } else {
  var previous;
  var current = head;

  while (current.next) {
   current = current.next;
  }

  current.next = node;
  node.prev = current;
  tail = node;
 }

 length++;
 return node;
};

insert方法:

该方法用于在指定位置插入元素。验证位置后，若插入头部，需特殊处理 head 和 tail 指针；若在中间或尾部，则通过遍历找到目标位置的前驱和后继节点，调整四个指针（前驱的 next、后继的 prev、新节点的 prev 和 next）以完成插入，并更新长度。


/**
 * 向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {

  var node = new Node(element);
  var index = 0;
  var previous;
  var current = head;

  if (position === 0) {

   if (head === null) {
    head = node;
    tail = node;
   } else {
    current.prev = node;
    node.next = current;
    head = node;
   }
  } else if (position === length) {

   current = tail;
   current.next = node;
   node.prev = current;
   tail = node;
  } else {

   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.prev = previous;
   current.prev = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

removeAt方法:

该方法用于移除指定位置的节点。验证索引后，若移除的是头节点，需更新 head；若移除的是尾节点，需更新 tail。对于中间节点，需调整前驱节点的 next 和后继节点的 prev 以跳过被移除节点，最后更新长度并返回移除的数据。


/**
 * 移除链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}       移除成功返回被移除的元素，不成功则返回false
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var index = 0;
  var previous;

  if (position === 0) {
   head = current.next;

   if (length === 1) {
    tail = null;
    head.prev = null;
   }
  } else if (position === length - 1) {
   current = tail;
   tail = current.prev;
   tail.next = null;
  } else {
   while (index++ < position) {
    previous = current.prev;
    current = current.next;
   }
   previous.next = current.next;
   current.next.prev = previous;
  }

  length--;
  return current.element;
 } else {
  return false;
 }
};

showHead、showLength、showTail方法

这些方法分别用于返回头节点引用、当前链表长度以及尾节点引用，辅助外部程序获取链表状态。


/**
 * 获取链表的头部
 * @return {Any} 链表的头部
 */
this.showHead = function() {
 return head;
};

/**
 * 获取链表长度
 * @return {Number} 链表长度
 */
this.showLength = function() {
 return length;
};

/**
 * 获取链表尾部
 * @return {Any} 链表尾部
 */
this.showTail = function() {
 return tail;
};

感想

感想

在实现链表的过程中，先根据需求编写代码，随后与标准教材或参考实现进行对比，能发现自身逻辑中的潜在漏洞和复杂性。实际编码中容易忽略边界条件（如空链表、单节点链表）和指针指向的细节，导致逻辑混乱。通过对比学习，可以更深刻地理解指针操作的正确性和数据结构设计的严谨性。

实用工具推荐

电子包浆

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

使用 ›
图片压缩

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

使用 ›
作者最新文章

JavaScript怎么遍历对象的Symbol键和不可枚举属性

封装一个健壮的JS字符串判空工具函数

JavaScript合并数组的三种常用方法：concat、扩展运算符与push

JavaScript立即执行函数(IIFE)是什么及基本语法

JS对象数组转字符串为什么推荐用JSON.stringify()

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