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

JavaScript 单向链表

欢迎大家来到我的博客,这是我的第一篇技术性博客,今天给大家讲解有关于JavaScript单向链表的建立和操作过程,希望大家能够从中收获到知识,我也会定期更新自己所学的知识到这个博客上。

链表

新建一个链表

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。JavaScript中的单向链表也是如此,建立一个链表我们首先先要建立一个最基础的属性:节点

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

因为JavaScript是一种弱类型的语言,所以使用函数定义节点,而next即为节点的指针,接下来就要创建我们的链表了,但是光有链表还不够,还需要一些链表的操作,添加节点的查找、插入、显示和删除四个功能。

1
2
3
4
5
6
7
8
function LList(){
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.display = display;
this.findPrevious = findPrevious;
this.remove = remove;
}

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

实现链表的查找功能

尽管已经建立出一个链表,但是因为这个链表只包含一个头节点,所以我们要插入自己想要的数据,但是如何确定插入元素在什么位置上呢?这就需要我们调用链表的查找函数 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
function insert(newElement,item){
var newNode = new Node(newElement);
var beforeNode = this.find(item);
newNode.next = beforeNode.next;
beforeNode.next = newNode;
}

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
function remove(item){
var findNode = this.findPrevious(item);
findNode.next = findNode.next.next;
}

接下来我们可以使用 display() 函数调用,就可以发现已经可以实现功能了,这是最基本的链表操作,接下来还会推出有关双向链表等博客,谢谢大家支持!

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