为什么我要放弃javaScript数据结构与算法(第五章)—— 链表

这一章你将会学会如何实现和使用链表这种动态的数据结构,这意味着我们可以从中任意添加或移除项,它会按需进行扩张。

本章内容

  • 链表数据结构
  • 向链表添加元素
  • 从链表移除元素
  • 使用 LinkedList 类
  • 双向链表
  • 循环链表

第五章 链表

链表数据结构

要存储多个元素,数组(或列表)可能是最常见的数据结构了。然后这种数据结构有一个缺点:数组的大小是固定的,从数组的起点或中间插入或移除项的成本有点高,因为需要移动元素。

链表存储有序的元素集合,但不同于数组,链表中的元素在内存并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成,下图展示了一个链表的结构。

链表数据结构

相对于传统的数组,链表的一个好处在于,添加或者移除元素的时候不需要移动其他元素,然后,链表需要使用指针,因为实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素,而想要访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

现实中也有一些链表的例子,第一个例子就是康加舞队,每个人就是一个元素,手就是链向下一个人的指针,可以向队列汇总增加人——只需要找到想加入的点,断开连接,插入一个人,再重新连接起来。

另外一个例子就是寻宝游戏,你有一条线索,这条线索是指向寻找下一个线索的地点的指针,你顺着这条链去下一个地点,得到另一条指向再下一处的线索。得到列表中间的线索的唯一方法,就是从起点(第一个线索)顺着列表寻找。

还有一个可能就是用来说明链表中的最流行的例子,那就是火车。一列火车是由一系列车厢(也称车皮)组成的。每节车厢或车皮都互相连接。可以很容易的分离开一节车皮,改变它的位置,添加或移除它。

创建链表

了解链表是什么之后,就要开始实现我们的数据结构了,一下是我们的 LinkedList 类的骨架:

function LinkedList(){
    let Node = function(element){ // 需要一个Node辅助类,表示要加入列表的项,element 代表要添加到列表中的值, next d代表指向列表的下一个节点向的指针
        this.element = element;
        this.next = null;
    }

    let length = 0; // 存储列表项的数量 length 属性
    let head = null; // 存储第一个节点的引用在 head 变量

    this.append = function(element){};
    this.insert = function(position,element){}
    this.removeAt = function(position){}
    this.remove = function(element){}
    this.indexOf = function(position){}
    this.isEmpty = function(){}
    this.size = function(){}
    this.getHead = function(){}
    this.toString = function(){}
    this.print = function(){}

}

LinkedList 类的方法的功能

  • append(element):向列表尾部添加一个新的项
  • insert(position,element):向列表的特定位置插入一个新的项
  • removeAt(position):从列表的特定位置移除一项
  • remove(element):从列表中移除一项
  • indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1
  • isEmpty():如果链表中不包含任何元素,返回true,如果链表的长度大于0则返回 false
  • size():返回链表包含的元素个数,与数字的 length 属性类似
  • toString():由于列表项使用 Node 类,就需要重写继承自 JavaScript 对象默认的 toString 方法,让其只输出元素的值。

向链表尾部追加元素

向 LinkedList 对象尾部添加一个元素时,可能有两种场景,列表为空,添加的是第一个元素,或者列表不为空,向追加元素。

this.append = function(element){
    let node = new Node(element),current;
    if(head === null){
        head = node;
    }else{
        current = head;
        // 循环列表,直到找到最后一项
        while(current.next){
            current = current.next;
        }
        // 当current.next元素为null时,找到最后一项,将其 next 赋为 node,建立连接
        current.next = node;
    }
    length++;  // 更新列表的长度
};

可以在 append 函数 加上return node ,通过下面的代码来使用和测试目前创建的数据结构

let list = new LinkedList();
console.log(list.append(15)); // Node {element: 15, next: null}
console.log(list.append(10)); // Node {element: 10, next: null}

从链表中移除元素

移除元素也有两种场景:第一种是移除第一个元素,第二种是移除第一个以外的任一元素。我们要实现两种 remove 方法:第一种是从特定位置移除第一个元素,第二种是根据元素的值移除元素。

首先先实现移除特定位置的元素

this.removeAt = function(position){
    // 检查越界值
    if(position >-1 && position < length){
        let current = head,previous,index = 0;

        // 移除第一项
        if(position === 0){
            head = current.next;
            console.log(current.element);
        }else{
            while(index++ < position){
                previous = current;
                current = current.next;
            }
            // 将 previous 与 current 的下一项连接起来,跳过 current,从移除它
            previous.next = current.next;
        }
        length --;
        console.log(current.element);
        return current.element;
    }else{              
        return null;
    }           
}

如果想要移除第一个元素(position=0),要做的就是让 head 指向列表的第二个元素,我们用 current 变量穿甲一个对列表中第一个元素的应用,这样 current 变量就是对列表中第一个元素的引用,如果吧 head 赋值为 current.next 就会移除第一个元素。

如果我们要移除列表的最后一项或者是中间的一项,为此,需要依靠一个细节来迭代列表,知道到达目标位置(index++ < position),使用一个用于内部控制和递增的 index 变量,current 变量总是对所循环列表的当前元素的引用(current = current.next),我们还需要一个对当前元素的前一个元素的引用(previous = current),它被命名为 previous。

因此,要从列表中移除当前元素,要做的就是将 previous.next 和 current.next 链接起来,这样当前元素就会被丢弃在计算机内存中,等着被垃圾回收站清除。

对于最后一个元素,在(while(index++ < position))跳出循环时, current 变量总是对列表中最后一个元素的引用(要移除的元素)。current.next 的值将是 null(因为它是最后一个元素)。由于还保留了对 previous 的引用(当前元素的前一个元素),previous 就指向了 current 。那么要移除 current,要做的就是把 previous.next 的值改变为 current.next 。

在任意位置插入元素

实现 insert 方法,使用这个方法可以在任意位置插入一个元素。

this.insert = function(position,element){
    // 检查越界值
    if(position >=0 && position <= length){
        let node = new Node(element),
        current = head,
        previous,
        index = 0;
        if(position === 0 ){ // 在第一个位置添加
            node.next = current;
            head = node;
        }else{
            while(index++ < position){
                previous = current;
                current = current.next;
            }
            node.next = current;
            previous.next = node;
        }
        length++;
        return true;
    }else{
        return false;
    }
}

current 变量是对列表中第一个元素的引用,我们需要做的是把 node.next 的值设为 current (列表中的第一个元素),现在 head 和 node.next 都指向了 current ,接下来要做的就是把 head 的引用改为 node ,这样列表中就有了一个新元素。

现在来处理第二种场景,在列表中间或者末尾添加一个新的元素。首先,循环访问列表,找打目标为位置,当跳出循环的时候, current 变量将是对想要插入新元素的位置之后一个元素的引用,而 previous 将是对想要插入新元素的位置之前的一个元素的引用。在这种情况下,我门要在 previous 和 current 之间添加新项。因此,需要将新项(node)和当前链接起来(node.next = current),然后需要改变 previous 和 current z之间的链接,我们还需要让 previous.next 指向 node。

实现其他方法

toString方法

this.toString = function(){
    let current = head,
    string = '';
    while(current){
        string += current.element + (current.next ? '-':'');
        current = current.next;
    }
    return string;
}

赋值current为 head, 循环访问 current,将 current 变量当做索引,初始化用于拼接元素的变量(string)。通过 current 来检查元素是否存在,如果列表为空或是到达列表中最后一个元素的下一位(null),while 循环中的代码就不会执行,就可以得到元素的内容,将其拼接到字符串中,最后,迭代下一个元素。最后,返回列表内容的字符串。

indexOf方法

indexOf方法接受一个元素的值,如果在列表中找到它,就返回元素的位置,否则返回 -1

this.indexOf = function(element){
    let current = head,
    index = 0;
    while(current){
        if(element === current.element){
            return index;
        }
        index++;
        current = current.next;
    }
    return -1;
}

循环变量 current,它的初始值是 head ,利用index 来计算位置数。访问元素,检查当前元素是否是我们要找的,如果是,就返回它的位置,不是就继续计数,检查列表中的下一个节点。

如果列表为空,或是到达列表的尾部(current = current.next 将是 null),循环就不会执行。如果没有找到值就返回 -1 。

实现了上面的方法,就可以实现remove等其他方法了

remove方法

this.remove = function(element){
    let index = this.indexOf(element);
    return this.removeAt(index);
}

isEmpty、size 和 getHead方法

isEmpty和size 和之前章节实现一模一样

this.isEmpty = function(){
    return length === 0;
}

this.size = function(){
    return length;
}

还有 getHead方法

this.getHead = function(){
    return head;
}

head 变量是 LinkedList 类的私有变量,我们如果需要在类的实现外部循环访问列表,就需要提供一种获取类的第一个元素的方法。

整个 LinkedList函数

function LinkedList(){
    let Node = function(element){ // 需要一个Node辅助类,表示要加入列表的项,element 代表要添加到列表中的值, next d代表指向列表的下一个节点向的指针
        this.element = element;
        this.next = null;
    }

    let length = 0; // 存储列表项的数量 length 属性
    let head = null; // 存储第一个节点的引用在 head 变量

    this.append = function(element){
        let node = new Node(element),current;
        if(head === null){
            head = node;
        }else{
            current = head;
            // 循环列表,直到找到最后一项
            while(current.next){
                current = current.next;
            }
            // 当current.next元素为null时,找到最后一项,将其 next 赋为 node,建立连接
            current.next = node;
        }
        length++;  // 更新列表的长度
    };

    this.insert = function(position,element){
        // 检查越界值
        if(position >=0 && position <= length){
            let node = new Node(element),
            current = head,
            previous,
            index = 0;
            if(position === 0 ){ // 在第一个位置添加
                node.next = current;
                head = node;
            }else{
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            length++;
            return true;
        }else{
            return false;
        }
    }

    this.removeAt = function(position){
        // 检查越界值
        if(position >-1 && position < length){
            let current = head,previous,index = 0;

            // 移除第一项
            if(position === 0){
                head = current.next;
                console.log(current.element);
            }else{
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                // 将 previous 与 current 的下一项连接起来,跳过 current,从移除它
                previous.next = current.next;
            }
            length --;
            return current.element;
        }else{              
            return null;
        }           
    }

    this.remove = function(element){
        let index = this.indexOf(element);
        return this.removeAt(index);
    }

    this.indexOf = function(element){
        let current = head,
        index = 0;
        while(current){
            if(element === current.element){
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }

    this.isEmpty = function(){
        return length === 0;
    }

    this.size = function(){
        return length;
    }

    this.getHead = function(){
        return head;
    }

    this.toString = function(){
        let current = head,
        string = '';
        while(current){
            string += current.element + (current.next ? '-':'');
            current = current.next;
        }
        return string;
    }

}

双向链表

链表有多种不同的类型,这一节介绍 双向链表,双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素。如下图所示

双向链表

先从实现 DoublyLinkedList 类所需要的变动开始

function DoublyLinkedList(){
    let Node = function(elememt){
        this.elememt = elememt;
        this.next = null;
        this.prev = null; // 新增的
    }
    let length = 0;
    let head = null;
    let tail = null // 新增的

    // 这里是方法
}

可以看出,Node 类中新增了 prev属性(一个新指针),在 DoublyLinkedList 类里也有用来保存对列表最后一项的引用的 tail 属性。

双向链表提供了两种迭代列表的方式:从头到尾,或者从尾到头。我们也可以方位一个特定节点的下一个或者是上一个元素。在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新迭代。这是双向链表的一个优点。

在任意位置插入新元素

向双向链表中插入一个新项跟(单向)链表非常相类似。区别在于,链表只要控制一个 next 指针,而双向链表则要同时控制 next 和 prev (previous,前一个)这两个指针。

this.insert = function(position,elememt){
    // 检查越界值
    if(position >= 0 && position <= length){
        let node = new Node(elememt),
        current = head,
        previous,
        index = 0;
        if(position === 0){ // 在第一个位置添加
            if(!head){
                head = node;
                tail = node;
            }else{
                node.next = current;
                current.prev = node;
                head = node;
            }
        }else if(position === length){ // 最后一项
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        }else{
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            node.next = current;
            previous.next = node;

            current.prev = node;
            node.prev = previous;
        }
        length++
        return true;
    }else{
        return false;
    }
}   

在列表的第一个位置(列表的起点)插入一个新元素,如果列表为空(if(!head)),那只需将 head 和 tail 都指向这个新节点。如果不为空, current 变量将是对列表中的第一个元素的引用。就像我们在链表中所做的,把 node.next 设为 current ,而head 将指针指向 node (它被设为列表中的第一个元素)。不同之处,我们还需要为指向上一个元素的指针设一个值。current.prev 指针将由 指向 null 变成指向 新元素(current.prev = node)。node.prev 指针已经是 null,因此不需要在更新任何东西了。

假如我们要在列表最后添加一个新元素。这是一个特殊情况,因为我们还控制着指向最后一个元素的指针(tail)。current 变量将引用最后一个元素(current = tail)。然后分开建立第一个链接:node.prev 将引用current。current.next 指针(指向null)将指向 node (由于构造函数,node.next 已经指向了 null)。然后只剩下一件事,就是更新 tail ,它将由 指向 current 变成指向 node 。

第三种场景:在列表中插入一个新元素,就像我们在之前方法中所做,迭代列表,知道到达要找的位置(while (index++ < position))。我们将在 current 和 previous 元素之间插入新元素。首先,node.next 将指向 current ,而 previous.next 将指向 node,这样就不会跌势节点之间的链接。然后需要处理所有的链接:current.prev 将指向node ,而 node.prev 将指向 previous

从任意位置移除元素

从双向链表中移除元素跟链表非常类似。唯一区别就是还需要设置一个位置的指针。

this.removeAt = function(position){
    // 检查越界值
    if(position > -1 && position < length){
        let current = head,
        previous,
        index = 0;
        // 移除第一项
        if(position === 0){
            head = current.next;
            // 如果只有一项,更新 tail
            if(length === 1){
                tail = null;
            }else{
                head.prev = null;
            }
        }else if(position === length-1){ // 最后一项
            current = tail;
            tail = current.prev;
            tail.next = null;
        }else{
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            // 将 previous 与 current 的下一项连接起来——跳过 current
            previous.next = current.next;
            current.next.prev = previous;
        }
        length --;
        return current.elememt;
    }else{
        return null;
    }
}

我们需要处理三种场景,从头部、从中间和从尾部移除一个元素。

移除第一个元素。current 变量是对列表中第一个元素的引用,也就是我们想要移除的远古三。需要做的就是改变 head 的引用,将其从 current 改为下一个元素(head = current.next;),但是我们还需要更新 current.next 指向上一个元素的指针(因为第一个元素的 prev 指针是 null)。因此,把 head.prev 的引用改为 null(因为 head 也指向了列表中的第一个元素,或者也可以用 current.next.prev )。由于还需要控制 tail 的引用,我们可以检测要移除的是否是第一个元素,如果是,只需要把 tail 也设为 null。

移除最后一个位置的元素。既然已经有了对最后一个元素的引用(tail),我们就不需要为找到它而迭代列表。我们可以把 tail 的引用赋给 current 变量。接下来,就需要吧 tail 的引用更新为列表中的倒数第二个元素(current.prev,或者 tail.prev也可以)。既然 tail 指向了倒数第二个元素,我们需要把 next 指针更新为 null (tail.next = null)。

最后一种场景,从列表中移除一个元素。首先需要迭代列表,直到到达要找的位置。current 变量所引用的就是要移除的远古三。那么要移除它,我们可以通过更新 previous.next 和 current.next.prev 的引用,在列表中跳过它。因此,previous.next 将 指向 current.next ,而 current.next.prev 将指向 previous。

完整代码

function DoublyLinkedList(){
    let Node = function(elememt){
        this.elememt = elememt;
        this.next = null;
        this.prev = null; // 新增的
    }
    let length = 0;
    let head = null;
    let tail = null // 新增的


    this.append = function(elememt){
        let node = new Node(elememt),
        current;
        if(!head){
            head = node;
            tail = node;
        }else{
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        }
        length++;
    }

    this.insert = function(position,elememt){
        // 检查越界值
        if(position >= 0 && position <= length){
            let node = new Node(elememt),
            current = head,
            previous,
            index = 0;
            if(position === 0){ // 在第一个位置添加
                if(!head){
                    head = node;
                    tail = node;
                }else{
                    node.next = current;
                    current.prev = node;
                    head = node;
                }
            }else if(position === length){ // 最后一项
                current = tail;
                current.next = node;
                node.prev = current;
                tail = node;
            }else{
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;

                current.prev = node;
                node.prev = previous;
            }
            length++
            return true;
        }else{
            return false;
        }
    }   

    this.removeAt = function(position){
        // 检查越界值
        if(position > -1 && position < length){
            let current = head,
            previous,
            index = 0;
            // 移除第一项
            if(position === 0){
                head = current.next;
                // 如果只有一项,更新 tail
                if(length === 1){
                    tail = null;
                }else{
                    head.prev = null;
                }
            }else if(position === length-1){ // 最后一项
                current = tail;
                tail = current.prev;
                tail.next = null;
            }else{
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 将 previous 与 current 的下一项连接起来——跳过 current
                previous.next = current.next;
                current.next.prev = previous;
            }
            length --;
            return current.elememt;
        }else{
            return null;
        }
    }

    this.remove = function(elememt){
        let index = this.indexOf(elememt);
        this.removeAt(index);
    }   

    this.toString = function(){
        let current = head,
        str = '';
        while (current) {
            str += current.elememt + (current.next?'-':'');
            current = current.next;
        }
        return str;
    }       

    this.indexOf = function(elememt){
        let current = head,
        index = 0;
        while (current) {
            if(current.elememt === elememt){
                return index
            }
            current = current.next;
            index++
        }
        return -1;
    }

    this.isEmpty = function(){
        return length === 0;
    }

    this.size = function(){
        return length;
    }

    this.getHead = function(){
        return head;
    }

}

循环链表

循环链表可以像链表一样只有单向引用,也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于,最后一个元素指向下一个元素的指针(tail.next)不是引用 null,而是指向第一个元素(head),如下图所示

循环链表

双向链表有指向 head 元素的 tail.next ,和指向 tail 元素的 head.prev

双向循环链表

小结

这一章中,学习了链表这种数据结构,及其辩题双向链表和循环链表,知道了如何在任意位置添加和移除元素,已经如何循环访问两边,比数组重要的优点就是,无需移动链表中的元素,就能轻松添加和移除元素。当你需要添加和移除很多元素的时候,最好的选择就是链表,而非数组。下一章将学习集合,最后一种顺序数据结构。

书籍链接: 学习JavaScript数据结构与算法