JavaScript数据结构之双向链表和双向循环链表的实现
作者：木棉时间：2026-10-22 10:08:26浏览：541
本文详细解析JavaScript中双向链表与双向循环链表的实现原理。通过对比单向链表，阐述双向链表节点中前向指针的作用及其在双向迭代中的优势。同时介绍如何将双向链表首尾相连构建双向循环链表，并提供完整的JavaScript代码示例，帮助开发者深入理解这两种数据结构的构建与遍历方法。
双向链表的基本概念
与普通链表仅包含指向下一个节点的链接不同，双向链表中的每个节点都拥有双向链接：一个指向后继元素，另一个指向前驱元素。
双向链表支持两种方向的列表迭代：既可以从头遍历到尾，也可以从尾遍历到头。此外，用户可以直接访问任意特定节点的前一个或后一个元素。在单向链表中，若迭代时错过目标节点，必须返回链表起点重新遍历；而双向链表则避免了这一不便，这是其显著优势之一。
单向链表仅能沿单一方向遍历节点，而双向链表通过在节点指针域中增加前向指针，实现了双向遍历能力。这使得双向链表能够从任意节点出发，完整遍历整个链表。
function DoublyLinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0,
head = null,
tail = null;
this.append = function(element){
var node = Node(element),
current,
previous;
if(!head){
head = node;
tail = node;
}else{
current = head;
while(current){
previous = current;
current = current.next;
}
node.next = current;
current.prev = node;
previous.next = node;
node.prev = previous;
}
length++;
return true;
}
this.insert = function(position,element){
if(position > -1 && position < length){
var node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0){
if(!head){
head = node;
tail = node;
}else{
node.next = current;
current.prev = node;
head = node;
}
}else if (position === length -1){
current = tail;
current.next = node;
node.prev = current;
}else {
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
index = 0,
previous;
if (position === 0) {
head = current.next;
if(length === 1){
tail = null;
}else{
head.prev = null;
}
}else if(position === length - 1){
current = tail;
tail = current.prev;
tail.next = null;
} else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
};
length-- ;
return current.element;
}else{
return false;
}
};
this.remove = function(element){
var current = head,
previous;
if(current.element === element){
head = current.next;
}
previous = current;
current = current.next;
while(current){
if (current.element = element) {
previous.next = current.next;
current.next.prev = previous;
}else{
previous = current;
current = current.next;
}
}
return false;
};
this.remove = function(){
if (length === 0) {
return false;
};
var current = head,
previous;
if(length === 1){
head = null;
tail = null;
length--;
return current.element;
}
while(current){
previous = current;
current = current.next;
}
previous.next = null;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index++ < length){
if (current.element === element) {
return index;
};
current = current.next;
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '';
while(current){
string += current.element;
current = current.next;
}
return string;
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
};
}
双向循环链表的构建
双向循环链表是将双向链表的头部与尾部指针相互连接而形成的结构。这种结构允许从任意节点同时向两个方向进行遍历，从而实现了最快的节点查询速度。
/*双向循环链表*/
function DoublyCircularLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0,
head = null,
tail = null;
this.append = function(element){
var node = new Node(element),
current,
previous;
if (!head) {
head = node;
tail = node;
head.prev = tail;
tail.next = head;
}else{
current = head;
while(current.next !== head){
previous = current;
current = current.next;
}
current.next = node;
node.next = head;
node.prev = current;
};
length++;
return true;
};
this.insert = function(position, element){
if(position >= 0 && position <= length){
var node = new Node(element),
index = 0,
current = head,
previous;
if(position === 0){
if(!head){
node.next = node;
node.tail = node;
head = node;
tail = node;
}else{
current.prev = node;
node.next = current;
head = node;
node.prev = tail;
}
}else if(position === length){
current = tail;
current.next = node;
node.prev = current;
tail = node;
node.next = head;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
current.prev = node;
node.next = current;
previous.next = node;
node.prev = previous;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
index = 0,
previous;
if(position === 0){
current.next.previous = tail;
head = current.next;
}else if(position === length - 1){
current = tail;
current.prev.next = head;
head.prev = current.prev;
tail = current.prev;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return true;
}else{
return false;
}
};
this.remove = function(element){
var current = head,
previous,
indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck === 0){
current.next.prev = tail;
head = current.next;
}else{
current.next.prev = previous;
previous.next = current.next;
}
length--;
return true;
}
previous = current;
current = current.next;
indexCheck++;
}
return false;
};
this.remove = function(){
if(length === 0){
return false;
}
var current = head,
previous,
indexCheck = 0;
if(length === 1){
head = null;
tail = null;
length--;
return current.element;
}
while(indexCheck++ < length){
previous = current;
current = current.next;
}
previous.next = head;
tail = previous.next;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index++ < length){
if(current.element === element){
return index;
}
current = current.next;
}
return false;
};
this.toString = function(){
var current = head,
indexCheck = 0,
string = '';
while(current && indexCheck < length){
string += current.element;
indexCheck++;
current = current.next;
}
return string;
};
this.isEmpty = function(){
return length === 0;
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
};
this.size = function(){
return length;
};
} 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。
作者最新文章
JavaScript怎么准确判断数据类型：typeof、instanceof与Object.prototype.toString
2026-11-05 17:09:21
JS中将数组和对象混合组装为JSON字符串
2026-11-05 16:41:42
JS运算符优先级与结合性的区别是什么？
2026-11-05 13:22:02
JS Map怎么只遍历Key或Value
2026-11-05 13:00:36
D3.js 与 ECharts 选型对比：灵活性 vs 开发效率
2026-11-05 09:45:01