JavaScript实现双向链表
一.什么是双向链表
- 双向链表：既可以从头遍历到尾，又可以从尾遍历到头。也就是说链表连接的过程是双向的，它的实现原理是：一个节点既有向前连接的引用，也有一个向后连接的引用。
- 双向链表的缺点：
- 每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些；
- 相对于单向链表，所占内存空间更大一些；
- 但是，相对于双向链表的便利性而言，这些缺点微不足道。
- 双向链表不仅有head指针指向第一个节点，而且有tail指针指向最后一个节点；
- 每一个节点由三部分组成：item储存数据、prev指向前一个节点、next指向后一个节点；
- 双向链表的第一个节点的prev指向null；
- 双向链表的最后一个节点的next指向null；
双向链表常见的操作（方法）：
- append（element）：向链表尾部添加一个新的项；
- inset（position，element）：向链表的特定位置插入一个新的项；
- get（element）：获取对应位置的元素；
- indexOf（element）：返回元素在链表中的索引，如果链表中没有元素就返回-1；
- update（position，element）：修改某个位置的元素；
- removeAt（position）：从链表的特定位置移除一项；
- isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false；
- size（）：返回链表包含的元素个数，与数组的length属性类似；
- toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值；
- forwardString（）：返回正向遍历节点字符串形式；
- backwordString（）：返回反向遍历的节点的字符串形式；
二、封装双向链表类
2.0.创建双向链表类
先创建双向链表类DoubleLinklist，并添加基本属性，再实现双向链表的常用方法：
1
2
3
4
5
6
7
8
9
10
11
12
| function DoublyLinkedList(){
this.head=null
this.tail=null
this.length=0
function Node(data){
this.data=data
this.preve=null
this.next=null
}
}
|
2.1.append(element)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
DoublyLinkedList.prototype.append=function(data){
var node=new Node(data)
if(this.head==null){
this.head=node
this.tail=node
}else{
node.preve=this.tail
this.tail.next=node
this.tail=node
}
this.length+=1
}
|
- 添加节点时 分情况讨论 如果添加的是第一个节点 我们将head与tail都指向它
- 如果不是第一个节点
- 通过：newNode.prev = this.tail：建立指向
- 通过：this.tail.next = node：建立指向
- 通过：this.tail = node：建立指向
2.2.toString()方法
1
2
3
4
5
6
7
8
9
10
|
DoublyLinkedList.prototype.toString=function(){
var current=this.head
var retcurrent=''
while(current){
retcurrent+=current.data+' '
current=current.next
}
return retcurrent
}
|
2.3.insert(position,element)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
DoublyLinkedList.prototype.insert=function(position,data){
if(position>this.length || position<0) return false
var node=new Node(data)
if(this.length==0){
this.head=node
this.tail=node
}else{
if(position==0){
this.head.preve=node
node.next=this.head
this.head=node
}else if(position==this.length){
this.tail.next=node
node.preve=this.tail
this.tail=node
}else{
var current=this.head
var index=0
while(index<position){
current=current.next
index++
}
node.next=current
node.preve=current.preve
current.preve.next=node
current.preve=node
}
}
this.length+=1
return true
}
|
双向链表中最复杂的方法 同样分情况讨论
1.当原链表为空时 直接放入新节点
2当原链表不为空
以上各情况分类讨论
2.4.get(position)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
DoublyLinkedList.prototype.get=function(position){
if(position>this.length || position<0) return false
if(this.length/2>position){
var current=this.head
var index=0
while(index<position){
current=current.next
index++
}
}else{
var current=this.tail
var index=this.length
while(index>position){
current=current.preve
index-=1
}
}
return current.data
}
|
- 定义两个变量current和index，按照之前的思路通过while循环遍历分别获取当前节点和对应的索引值index，直到找到需要获取的position位置后的一个节点，此时index = position =x，然后return current.data即可。
- 当this.length / 2 > position：从头（head）开始遍历；
- 当this.length / 2 < position：从尾（tail）开始遍历；
2.5.indexOf(element)
1
2
3
4
5
6
7
8
9
10
|
DoublyLinkedList.prototype.indexOf=function(data){
var current=this.head
var index=0
while(current.data != data){
current=current.next
index+=1
}
return index
}
|
- 以（current）作为条件，通过while循环遍历链表中的所有节点（停止条件为current = null）。在遍历每个节点时将current指向的当前节点的data和传入的data进行比较即可。
2.7.update(position,element)
1
2
3
4
5
6
7
8
9
10
11
| DoublyLinkedList.prototype.update=function(position,data){
if(position>this.length || position<0) return false
var current=this.head
var index=0
while(index<position){
current=current.next
index++
}
current.data=data
return true
}
|
- 以（index++ < position）为条件，通过while循环遍历链表中的节点（停止条件为index = position）。循环结束后，current指向需要修改的节点。
2.8.removeAt(position)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| DoublyLinkedList.prototype.removeAt=function(position){
if(position>=this.length || position<0) return false
var current=this.head
if(this.length==1){
this.head=null
this.tail=null
}
else if(position==0){
this.head.next.preve=null
this.head=this.head.next
}else if(position==this.length-1){
current=this.tail
this.tail.preve.next=null
this.tail=this.tail.preve
}else{
var index=0
while(index<position){
current=current.next
index++
}
current.next.preve=current.preve
current.preve.next=current.next
}
this.length-=1
return current.data
}
|
当链表的length = 1时：
- 情况1：删除链表中的所有节点：只需要让链表的head和tail指向null即可。
当链表的length > 1时：
情况2：删除链表中的第一个节点：
remove(element)、isEmpty()、size()、getHead()、getTail()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
DoublyLinkedList.prototype.remove=function(data){
var index=this.indexOf(data)
this.length-=1
return this.removeAt(index)
}
DoublyLinkedList.prototype.isEmpty=function(){
return this.length==0
}
DoublyLinkedList.prototype.size=function(){
return this.length
}
DoublyLinkedList.prototype.getHead=function(){
return this.head.data
}
DoublyLinkedList.prototype.getTail=function(){
return this.tail.data
}
|
三、链表结构总结
单向链表有head和next两个属性，双向链表有head、tail、next、prev四个属性。处理好它们的指向，相当于将它们正确地连接在一起，这样就组成了一条链，这就是简单链表的实现。
在实际开发中链表使用得非常多，比如Java中的LinkList就是双向链表。
3.1.注意点
- 在链表中current = current.next 可以从左往右看，看成是current –> current.next，即current指向current的下一个节点。
- 删除节点的原理：只要没有引用指向该对象，无论该对象是否有引用指向其他对象，该对象都会被回收（删除）。
- 参数中凡是有position的都要进行越界判断。
