双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。 双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点。本文主要介绍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双向链表和双向循环链表的实现的详细内容。更多信息请关注PHP中文网其他相关文章！
声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
es6数组怎么去掉重复并且重新排序May 05, 2022 pm 07:08 PM去掉重复并排序的方法：1、使用“Array.from(new Set(arr))”或者“[…new Set(arr)]”语句，去掉数组中的重复元素，返回去重后的新数组；2、利用sort()对去重数组进行排序，语法“去重数组.sort()”。
JavaScript的Symbol类型、隐藏属性及全局注册表详解Jun 02, 2022 am 11:50 AM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于Symbol类型、隐藏属性及全局注册表的相关问题，包括了Symbol类型的描述、Symbol不会隐式转字符串等问题，下面一起来看一下，希望对大家有帮助。
原来利用纯CSS也能实现文字轮播与图片轮播！Jun 10, 2022 pm 01:00 PM怎么制作文字轮播与图片轮播？大家第一想到的是不是利用js，其实利用纯CSS也能实现文字轮播与图片轮播，下面来看看实现方法，希望对大家有所帮助！
JavaScript对象的构造函数和new操作符（实例详解）May 10, 2022 pm 06:16 PM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于对象的构造函数和new操作符，构造函数是所有对象的成员方法中，最早被调用的那个，下面一起来看一下吧，希望对大家有帮助。
javascript怎么移除元素点击事件Apr 11, 2022 pm 04:51 PM方法：1、利用“点击元素对象.unbind("click");”方法，该方法可以移除被选元素的事件处理程序；2、利用“点击元素对象.off("click");”方法，该方法可以移除通过on()方法添加的事件处理程序。
JavaScript面向对象详细解析之属性描述符May 27, 2022 pm 05:29 PM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于面向对象的相关问题，包括了属性描述符、数据描述符、存取描述符等等内容，下面一起来看一下，希望对大家有帮助。
foreach是es6里的吗May 05, 2022 pm 05:59 PMforeach不是es6的方法。foreach是es3中一个遍历数组的方法，可以调用数组的每个元素，并将元素传给回调函数进行处理，语法“array.forEach(function(当前元素,索引,数组){...})”；该方法不处理空数组。
整理总结JavaScript常见的BOM操作Jun 01, 2022 am 11:43 AM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于BOM操作的相关问题，包括了window对象的常见事件、JavaScript执行机制等等相关内容，下面一起来看一下，希望对大家有帮助。
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
AI Hentai Generator
免费生成ai无尽的。
热门文章
R.E.P.O.能量晶体解释及其做什么（黄色晶体）
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
1 周前ByDDD
R.E.P.O.如果您听不到任何人，如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
在哪里可以找到原子中的起重机控制钥匙卡
1 周前ByDDD
热工具
EditPlus 中文破解版
体积小，语法高亮，不支持代码提示功能
ZendStudio 13.5.1 Mac
功能强大的PHP集成开发环境
VSCode Windows 64位 下载
微软推出的免费、功能强大的一款IDE编辑器
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
Dreamweaver Mac版
视觉化网页开发工具
