&web_id=" language="JavaScript">
Fork me on GitHub

JavaScript 双向链表

经过上次的单向链表的讲解,大家可能对链表这种数据结构有了一定的理解,今天要讲的是有关JavaScript双向链表的基本介绍。
有关单向链表的基础知识请参考我的博客JavaScript 单向链表

双向链表

新建一个链表

双向链表跟单向链表的节点结构不同之处就是双向链表有一个前驱,这就需要我们构建一个指向前一个节点的指针。

1
2
3
4
5
function Node(element){
this.element = element;
this.next = null;
this.previous = null
}

接下来就如单向链表一样创建一个链表。

1
2
3
4
5
6
7
8
9
10
function LList(){
this.head = new Node("head"); //建立链表的头节点
this.find = find; //查找指定节点
this.insert = insert; //插入节点
this.display = display; //显示所有节点
this.findLast = findLast; //查找最后一个节点
this.remove = remove; //删除指定节点
this.disReverse = disReverse; //链表的反序排列
this.findPrevious = findPrevious;
}

至此,一个链表的基本结构就建好了,接下来我们需要通过一系列的功能测试这个链表。

实现链表的查找功能

就如单向链表一样,需要我们调用链表的查找函数 find()。

1
2
3
4
5
6
7
function find(item){
var findNode = this.head;
while(findNode.element!=item){
findNode = findNode.next;
}
return findNode;
}

查找函数的参数就是链表的内容,即element。

实现链表的插入功能

查找的目的不仅仅是创建一个链表,你也可以通过查找函数确定链表内数据是否正确,接下来需要实现的就是我们的插入函数 insert() 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insert(newElement,item){
var newNode = new Node(newElement); //创建一个新的节点
var beforeNode = this.find(item); //寻找想插入的前一个元素
if(beforeNode.next!=null){
newNode.next = beforeNode.next; //新创建节点的指针复制
beforeNode.next.previous = newNode; //将新创建节点下一个节点指向新创建的节点
beforeNode.next = newNode; //将前一个节点的指针指向新创建的节点
newNode.previous = beforeNode; //将新建节点的前驱指向上一个节点
}
else{
newNode.next = beforeNode.next; //新创建节点的指针复制
beforeNode.next = newNode; //将前一个节点的指针指向新创建的节点
newNode.previous = beforeNode; //将新建节点的前驱指向上一个节点
}
}

newElement是你想要插入节点的内容,而item是你想要插入节点的前一个节点的内容。

实现链表的显示功能

通过查找前一个节点,就可以实现在指定节点后插入节点的操作了。接下来检验我们的函数是否可用,就需要调用我们的显示函数 display() 了。

1
2
3
4
5
6
7
function display(){
var findNode = this.head;
while(!(findNode.next == null)){
console.log(findNode.next.element);
findNode = findNode.next;
}
}

display() 需要在Google console 中调用,通过调用你会发现建立了一个完整的链表结构,而且可以随心所欲的更改链表的数据了。

实现链表的删除功能

链表的删除功能其实就是将链表的指针指向下下个节点上,因为浏览器的缓存特性,浏览器会自动清除无用的节点,这样便实现了链表节点的删除,但在删除节点之前我们需要找到删除的节点的前一个节点,然后改变指针就可以了。

1
2
3
4
5
6
7
function findPrevious(item){
var findNode = this.head;
while(findNode.next.element!=item){
findNode =findNode.next;
}
return findNode;
}

找到前一个节点,就可以实现我们的删除操作了,删除需要 remove() 函数实现。

1
2
3
4
5
6
7
8
9
10
function remove(item){
var findNode = this.findPrevious(item);//找到删除节点的前一个节点
if(findNode.next.next!=null){
findNode.next = findNode.next.next; //将删除节点之后的节点向前移位
findNode.next.next.previous = findNode;//将删除节点的前指针指向删除节点的前一个节点,浏览器自动清除无用的节点
}
else{
findNode.next = findNode.next.next; //将删除节点之后的节点向前移位
}
}

接下来我们可以使用 display() 函数调用,就可以发现已经可以实现功能了。

实现链表的反序排序功能

双向链表区别于单向链表最重要的功能就是反向排序,反向排序需要我们找到最后一个节点,然后通过前驱依次遍历,首先我们需要 findLast() 实现查找最后一个节点。

1
2
3
4
5
6
7
function findLast(){
var findNode = this.head; //找到表头
while(!(findNode.next == null)){ //查找是否节点的后驱指针为空
findNode = findNode.next;
}
return findNode;
}

然后直接调用排序函数就可以实现链表的反向排序输出了。

1
2
3
4
5
6
7
8
function disReverse(){
var findNode = this.head;
findNode = this.findLast();
while(!(findNode.previous == null)){
console.log(findNode.element);
findNode = findNode.previous;
}
}

通过这次讲解是不是对链表这种数据结构产生了兴趣?接下来还会推出有关循环链表的博客,也会给大家讲一个小游戏,敬请期待!

Godlike Meteor wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
我知道不会有人点开,但万一真有人想不开呢?
------ 本文结束 ------