本文详细解析了 JavaScript 中双向链表的实现过程。从单链表的局限性出发，介绍了双向链表的结构特点，包括 prev、data 和 next 指针。重点讲解了 DoublyLinkedList 类的封装，以及 append、insert、get、remove 等核心方法的逻辑与代码实现，帮助开发者掌握双向链表在 JS 中的应用。
一、什么是双向链表
已知单链表仅支持单向遍历（通常从头至尾），其原理依赖于前驱节点持有指向后继节点的引用。该结构存在显著局限性：
虽能便捷访问后续节点，但回溯至前驱节点较为困难。鉴于实际开发中常需逆向访问场景，双向链表应运而生。
双向链表定义为支持双向遍历（头至尾、尾至头）的数据结构。尽管其插入或删除操作需处理四个引用而非两个，且内存开销略高于单链表，但相较于操作便利性，这些缺点可忽略不计。 下文展示双向链表结构图。如下所示：
双向链表核心特性：
- 引入head与tail指针分别指向首尾节点。
- 节点由三部分构成：前驱指针（prev）、数据域（data）及后继指针（next）。
- 首节点的prev属性值为null。
- 尾节点的next属性值为null。
结构抽象示意如下：
明确结构后，下文阐述双向链表的封装实现。
二、双向链表的封装
首先定义DoublyLinkedList类以表征链表整体结构。内部嵌套Node类用于封装节点信息（含前驱引用、数据及后继引用）。在Node类中维护三个属性：链表长度、头节点引用及尾节点引用。具体实现如下：
function DoublyLinkedList(){
this.head = null;
this.tail = null;
this.length = 0;
function Node(data){
this.data = data;
this.prev = null;
this.next = null;
}
三、双向链表的常用操作
在此基础上，实现双向链表的标准操作方法：
append（element:向列表尾部添加一个项
insert(position,element):向列表的特定位置插入一个项
get(position):获取对应位置的元素
indexOf(element):返回元素在列表中的索引，若未找到则返回-1
update(position，ele):修改某个位置的元素
removeAt(position):从列表的指定位置移除一项
remove(element):从列表中移除一项
isEmpty():若链表为空返回true，长度大于0返回false
size():返回链表包含的元素个数，对应数组的length属性
toString():因列表项依赖Node类，需重写继承自JavaScript对象的默认toString方法，以输出元素值。
forwardString():返回正向遍历的节点字符串形式
backwardString():返回反向遍历的节点字符串形式
接下来逐一实现上述方法。
1、append（element)方法-----向列表尾部添加一个项
该方法逻辑与单链表类似。首先创建新节点，判断链表状态：若为空，直接将头部指向新节点；若不为空，则令新节点的前驱指针指向当前尾部，并将原尾部节点的后继指针指向新节点。
Doubly.prototype.append = function(data){
var newNode = new Node(data);
if(this.length == 0){
this.head = newNode;
}else{
newNode.prev = this.tail;
this.tail.next = newNode;
}
this.tail = newNode;
this.length += 1;
}
2、将链表转化为字符串形式
1、toString():正向输出元素的值
此方法旨在获取所有元素并生成字符串。因默认遍历需从首节点开始，故从head出发，循环遍历各节点并提取element进行拼接，最终返回字符串。具体实现为创建临时节点current指向头部，通过next指针向后遍历并拼接数据。
DoublyLinkedList.prototype.tostring = function(){
var current = this.head;
var str = '';
while(current){
str += current.data + ' ';
current = current.next;
}
return str;
}
2、forwardString():返回正向遍历的节点字符串形式
该方法实现双向链表的正向打印输出，可直接复用前述方法：
DoublyLinkedList.prototype.forwardString = function(){
return this.toString()
}
3、backwardString():返回反向遍历的节点字符串形式
此方法旨在从尾部向前遍历获取元素并打印。实现时创建临时节点current指向尾部，通过prev指针向前遍历，拼接每次遍历得到的数据并返回字符串。
DoublyLinkedList.prototype.backwardString = function(){
var current = this.tail;
var str = '';
//依次向前遍历，获取每一个节点
while(current){
str += current.data +' ';
current = current.prev;
}
return str;
}
验证：
例如通过append()方法创建含三个数据的双向链表，并分别执行正向与反向拼接：
var list = new DoublyLinkedList();
list.append("a");
list.append("b");
list.append("c");
list.append("d");
console.log('toString()方法：'+list.toString());
console.log('forwardString()方法：'+list.forwardString());
console.log('backwardString()方法：'+list.backwardString());
打印结果为：
验证成功。
3、insert(position,element):向列表的特定位置插入一个项
该方法逻辑相对复杂。首先校验插入位置是否越界。若未越界，根据链表状态处理：若链表为空，新节点即为首尾节点，直接更新头尾指针；若链表非空，插入位置分三种情况：首位、末尾或中间。具体操作如下：
DoublyLinkedList.prototype.insert = function(position,data){
var newNode = new Node(data);
//越界判断，如果不满足，返回false
if(position<0 || position>this.length){
return false;
}else{
//再次判断
//如果链表为空，直接插入
if(position==0){
this.head = newNode;
this.tail = newNode;
}else {
//如果链表不为空
//如果插入位置为末尾
if(position == this.length){
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}else if(position == 0){
//如果插入位置为首位
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}else{
//如果插入位置为中间
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode;
current.prev = newNode;
}
this.length += 1;
}
}
}
验证：如果在1位置插入xl,如下所示:
list.insert(1,'xl')
console.log(list.toString());
运行结果为：
验证成功。
4、get(position):获取对应位置的元素
该方法首先校验位置是否越界。若有效，定义临时节点与索引，使临时节点指向头结点。遍历过程中索引自增，当遍历至目标位置时，返回该临时节点对应的元素。
DoublyLinkedList.prototype.get = function(position){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
return current.data;
}
}
验证：查询position = 2的元素
console.log('list.get(2):'+list.get(2));
结果为：
验证成功。
然而，上述查找方式仅支持单向遍历，效率受限。为此可采用双向查找策略：若目标位置小于或等于链表长度的一半，则从前向后查找；若大于长度一半，则从后往前查找。实现代码为：
DoublyLinkedList.prototype.get = function(position){
if(position<0 || position>=this.length){
return false;
}else{
var len = Math.floor(this.length/2);
if(position<=len){
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
}else{
var index = this.length-1;
var current = this.tail;
while(index-->position){
current = current.prev;
}
}
return current.data;
}
}
5、indexOf(element):返回元素在列表中的索引
创建临时节点与索引，使临时节点指向头结点。依次向后遍历并递增索引，当遍历到的元素等于指定值时，当前临时节点的位置即为目标位置，其索引即为目标值的索引。
DoublyLinkedList.prototype.indexOf = function(data){
var current = this.head;
var index = 0;
while(current){
if(current.data === data){
return index;
}
current = current.next;
index ++;
}
return -1;
}
验证成功。
6、 update(position，ele):修改某个位置的元素
首先校验修改位置是否越界。若有效，定义临时节点与索引，使临时节点指向头结点，索引初始为0。遍历并判断临时节点索引与目标位置是否一致，若一致，则直接修改该临时节点的数据域。
DoublyLinkedList.prototype.update = function(position,newData){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = curent.next;
}
current.data = newData;
return true;
}
}
验证：将0位置的数据换成rc
list.update(0,'rc')
console.log("list.update(0,'rc')为:");
console.log(list.toString());
验证成功。
7、removeAt(position):从列表的指定位置移除一项
该方法思想与insert()方法相似。首先校验是否越界。若未越界，若链表仅含一个节点，则直接移除，使头尾节点均指向空；若链表含多个节点，则分三种情况处理，操作如下：
DoublyLinkedList.prototype.removeAt = function(position){
if(position<0 || position>=this.length){
return null;
}else{
var current = this.head;
if(this.length ===1){
//链表长度为1
this.head = null;
this.tail = null
}else{//链表长度不为1
if(position === 0){
//删除首位
this.head.next.prev = null;
this.head = this.head.next;
}else if(position === this.length-1){
this.tail.prev.next = null;
this.tail = this.tail.prev;
}else{
var index = 0;
while(index++ <position){
current = current.next;
}
current.prev.next = current.next;
current.next.pre = current.prev;
}
}
this.length -=1;
return current.data;
}
}
验证：删除位置3的数据：
list.removeAt(3)
console.log("list.removeAt(3)为:");
console.log(list.toString());
结果为：
验证成功
8、remove(element):从列表中移除一项
可直接依据indexOf(element)方法获取元素在链表中的位置，再根据removeAt(position)方法执行删除操作。
DoublyLinkedList.prototype.remove = function(data){
var index = this.indexOf(data);
return this.removeAt(index);
}
验证：删除数据为rc的节点：
list.remove('rc');
console.log("list.remove('rc')为:");
console.log(list.toString());
9、isEmpty():判断链表是否为空
直接判断链表中元素个数是否为零。若为零则返回true（为空），否则返回false（非空）。
DoublyLinkedList.prototype.isEmpty = function(){
return this.length ==0;
}
验证：
console.log("链表是否为空："+list.isEmpty());
10、size():返回链表包含的元素个数
链表长度即元素个数。
DoublyLinkedList.prototype.size = function(){
return this.length;
}
验证：
console.log("链表的元素个数为："+list.size());
以上就是JavaScript实现双向链表过程解析的详细内容，更多关于JavaScript 双向链表的资料请关注本站其它相关文章！