JavaScript数据结构之双向链表
单向链表在遍历时只能从头到尾或者从尾遍历到头；所以单向链表可以轻松到达下一节点，但是回到上一个节点是很困难的
而双向链表既可以从头遍历到尾,又可以从尾遍历到头，链表的相联是双向的，一个节点既有向前连接的引用，也有向后连接的引用
但是正因如此，双向链表在插入或者删除某个节点时，需要处理四个节点的引用，并且所占用内存空间也更大一些
双向链表实现
JavaScript代码实现双向链表
//创建双向链表的构造函数
functionDoublyLinkedList(){
//创建节点构造函数
functionNode(element){
this.element=element
this.next=null
this.prev=null//新添加的
}
//定义属性
this.length=0
this.head=null
this.tail=null//新添加的
//定义相关操作方法
//在尾部追加数据
DoublyLinkedList.prototype.append=function(element){
//1.根据元素创建节点
varnewNode=newNode(element)
//2.判断列表是否为空列表
if(this.head==null){
this.head=newNode
this.tail=newNode
}else{
this.tail.next=newNode
newNode.prev=this.tail
this.tail=newNode
}
//3.length+1
this.length++
}
//在任意位置插入数据
DoublyLinkedList.prototype.insert=function(position,element){
//1.判断越界的问题
if(position<0||position>this.length)returnfalse
//2.创建新的节点
varnewNode=newNode(element)
//3.判断插入的位置
if(position===0){//在第一个位置插入数据
//判断链表是否为空
if(this.head==null){
this.head=newNode
this.tail=newNode
}else{
this.head.prev=newNode
newNode.next=this.head
this.head=newNode
}
}elseif(position===this.length){//插入到最后的情况
//思考:这种情况是否需要判断链表为空的情况呢?答案是不需要,为什么?
this.tail.next=newNode
newNode.prev=this.tail
this.tail=newNode
}else{//在中间位置插入数据
//定义属性
varindex=0
varcurrent=this.head
varprevious=null
//查找正确的位置
while(index++=this.length)returnnull
//2.判断移除的位置
varcurrent=this.head
if(position===0){
if(this.length==1){
this.head=null
this.tail=null
}else{
this.head=this.head.next
this.head.prev=null
}
}elseif(position===this.length-1){
current=this.tail
this.tail=this.tail.prev
this.tail.next=null
}else{
varindex=0
varprevious=null
while(index++
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。