链表的作用和好处?如何用JS来写一个链表

2,405 阅读3分钟

链表是一种数据结构,里面的每个元素都包含下一个元素的位置信息,和数组做个对比,数组在内存中存放需要一段连续的位置,而数组则不用,可以分开存储在内存的任意位置。

这样做的好处是插入和删除速度快,步骤少,如果要在头部插入一个新的元素,链表只需要将第一个元素的位置信息添加进新的元素里即可,操作步骤为O(1),而数组则需要将里面所有的元素都往后移一位,步骤为O(n)。

坏处在于查找很慢,在链表里如果要找到某个元素,必须从第一个开始,顺藤摸瓜式地往下查找。 所以,链表通常用在插入和删除比较多的场景,比如记账软件和代办事项等。

现在,就用js来创建一个链表,实现链表的所有功能:

1.元素类 首先要有一个创建元素的类,这个元素包含了两个信息,一个是当前元素,另一个是下个元素的信息:

var Node = function(e){
    this.element = e
    this.next = null
}

2.链表类 其次要创建一个链表类,里面包含一个head和链表长度,当创立一个新的链表类时,链表里的head也会通过元素类来创建一个新的元素,这个新元素的element和next都是空的,创建的目的是将它作为第一个元素,因为无论是查找或者插入,都需要从第一个元素找起:

var LinkedList = function(){
    this.head = new Node()
    this._length = 0
}

3.Append 如果要插入一个元素的话,首先将要插入的元素创建一个新的node,然后判断head的next元素是否为空,如果不为空的话,可以提取head.next,这样就获得了下一个元素,然后接着判断,一直到空为止; 当next为空后说明到了最后一链,此时将之前创建的node赋值给next,然后给计数器加1,如:

LinkedList.prototype.append = function(){
    var node = new Node()
    var n = this.head
    while (n.next != null){
	n = n.next
    }
    n.next = node
    this._length++
}

4.Indexof 返回链表某个元素的位置,和append差不多,同样是从第一个开始不断寻找,每次寻找都会对比元素,如果返回true则输出,如:

LinkedList.prototype.indexof = function(e){
    var n = this.head
    for (let i = 0; i < this._length; i++){
	//因为第一个链表元素是空的,所以不需要对比,直接跳到下一个
	n = n.next
	if (n.element == e){
	    return i
	}
    }
}

5.Log 打印所有链表所有元素,如:

LinkedList.prototype.log = function(){
    var n = this.head.next
    while (n != null){
	log('>', n.element)
	n = n.next
    }
}

完整代码:

var Node = function(e){
    this.element = e
    this.next = null
}

var LinkdeList = function(){
    //当创建一个新的链表时,里面会包含一个空的链数
    this.head = new Node()
    this._length = 0
}

LinkdeList.prototype.append = function(e){
    var node = new Node(e)
    var n = this.head
    while(n.next != null){
        n = n.next
    }
    n.next = node
    this._length++
}

LinkdeList.prototype.indexof = function(e){
    var n = this.head
    for (let i = 0; i < this._length; i++) {
        n = n.next
        if (n.element == e){
            return i
        }
    }
}

LinkdeList.prototype.log = function(){
    var n = this.head.next
    while(n != null){
        log('>',n.element)
        n = n.next
    }
}