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

本章内容

• 链表数据结构
• 向链表添加元素
• 从链表移除元素
• 使用 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数据结构与算法