JavaScript 链表

[Checkson]

前言

在之前的章节中，我们讨论了如何使用数组来实现列表、栈和队列等数据结构。本章节，我们讨论另一种列表：链表。我们将会认识到为什么有时候，链表会优于数组，还会实现一个基于对象的链表，并且附上一些实战内容。

背景

数组并不总是组织数据的最佳数据结构，原因如下。在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。然而，JavaScript 的数组并不存在上述问题，因为使用 split() 方法不需要再访问数组中的其他元素了。

JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言（比如 C++ 和 Java）的数组相比，效率很低。

如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。

定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的集合。如下图所示：

数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。然而要标识出链表的起始节点却有点麻烦，许多链表的实现都在链表最前面有一个特殊节点，叫做头节点。如下图所示：

链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。下图演示了如何在 Tue 节点后加入 Fri 节点。

从链表中删除一个元素也很简单。将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了。下图演示了从链表中删除“Fri”节点的过程。

链表节点（Node）类实现

完整代码地址，Node类包含两个属性：

• el 用来保存节点上的数据
• next 用来保存指向下一个节点的链接

1. 构造函数

function Node (el) {
    this.el = el;
    this.next = null;
}

链表（Link）类实现

完整代码地址，Link类提供了以下的方法：

• insert 插入新节点
• remove 删除节点
• display 显示链表元素的方法
• 其他一些辅助方法

1. 构造函数

function Link () {
    this.head = new Node('head');
}

2. find：按节点的值查找节点

Link.prototype.find = function (el) {
    var currNode = this.head;
    while (currNode && currNode.el != el) {
        currNode = currNode.next;
    }
    return currNode;
}

find 方法展示了如何在链表上进行移动。首先，创建一个新节点，并将链表的头节点赋给这个新创建的节点。然后在链表上进行循环，如果当前节点的 el 属性和我们要找的信息不符，就从当前节点移动到下一个节点。如果查找成功，该方法返回包含该数据的节点；否则，返回 null。

3. insert：插入一个节点

Link.prototype.insert = function (newEl, oldEl) {
    var newNode = new Node(newEl);
    var findNode = this.find(oldEl);
    if (findNode) {
        newNode.next = findNode.next;
        findNode.next = newNode;
    } else {
        throw new Error('找不到给定插入的节点');
    }
}

find 方法一旦找到给定的节点，就可以将新节点插入链表了。

4. display：展示链表节点元素

// 展示链表中的元素
Link.prototype.display = function () {
    var currNode = this.head.next;
    while (currNode) {
        console.log(currNode.el);
        currNode = currNode.next;
    }
}

5. findPrev：寻找给定节点的前一个节点

Link.prototype.findPrev = function (el) {
    var currNode = this.head;
    while (currNode.next && currNode.next.el !== el) {
        currNode = currNode.next;
    }
    return currNode;
}

6. remove：删除给定的节点

Link.prototype.remove = function (el) {
    var prevNode = this.findPrev (el);
    if (prevNode.next != null) {
        prevNode.next = prevNode.next.next;
    } else {
        throw new Error('找不到要删除的节点');
    }
}

链表（Link）类测试

var link = new Link();
link.append(1);
link.append(3);
link.display();
console.log('------------'); 
link.insert(2, 1);
link.display();
console.log('------------'); 
link.remove(1);
link.display();

运行结果：

1
3
------------
1
2
3
------------
2
3

上面介绍的链表我们称作：单向链表（单链表），其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。下面我们介绍另一种链表：双向链表（双链表）。

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。如下图所示：

双向链表节点（DNode）类实现

完整代码地址，相比于单向链表节点（Node）类，我们只需新增一个 prev 属性，指向之前一个链表节点的引用即可。

function DNode (el) {
    this.el = el;
    this.prev = null;
    this.next = null;
}

双向链表（DLink）类实现

完整代码地址，相比于单链表，双链表的操作会复杂一点。

1. 构造函数

function DLink () {
    this.head = new DNode('head');
}

2. append：向链表结尾添加一个节点

DLink.prototype.append = function (el) {
    var currNode = this.head;
    while (currNode.next != null) {
        currNode = currNode.next;
    }
    var newNode = new DNode(el);
    newNode.next = currNode.next;
    newNode.prev = currNode;
    currNode.next = newNode;
}

3. find：查找给定的节点

DLink.prototype.find = function (el) {
    var currNode = this.head;
    while (currNode && currNode.el != el) {
        currNode = currNode.next;
    }
    return currNode;
}

4. insert：插入一个节点

DLink.prototype.insert = function (newEl, oldEl) {
    var newNode = new DNode(newEl);
    var currNode = this.find(oldEl);
    if (currNode) {
        newNode.next = currNode.next;
        newNode.prev = currNode;
        currNode.next = newNode;
    } else {
        throw new Error('未找到指定要插入节点位置对应的值！')
    }
}

5. display：顺序展示链表节点

DLink.prototype.display = function () {
    var currNode = this.head.next;
    while (currNode) {
        console.log(currNode.el);
        currNode = currNode.next;
    }
}

6. findLast：查找最后一个节点

DLink.prototype.findLast = function () {
    var currNode = this.head;
    while (currNode.next != null) {
        currNode = currNode.next;
    }
    return currNode;
}

7. dispReverse：逆序展示链表元素

DLink.prototype.dispReverse = function () {
    var currNode = this.head;
    currNode = this.findLast();
    while (currNode.prev != null) {
        console(currNode.el);
        currNode = currNode.prev;
    }
}

8. remove：删除节点

DLink.prototype.remove = function (el) {
    var currNode = this.find(el);
    if (currNode && currNode.next != null) {
        currNode.prev.next = currNode.next;
        currNode.next.prev = currNode.prev;
        currNode.next = null;
        currNode.previous = null;
    } else {
        throw new Error('找不到要删除对应的节点');
    }
}

双向链表（DLink）类测试

// 实例化
var doubleLink = new DLink();
doubleLink.append(1);
doubleLink.append(2);
doubleLink.append(4);
doubleLink.display();
console.log('-------------------------');
doubleLink.dispReverse();
console.log('-------------------------');
doubleLink.insert(3, 2);
doubleLink.display();
doubleLink.remove(1);
console.log('-------------------------');
doubleLink.display();

运行结果：

1
2
4
-------------------------
4
2
1
-------------------------
1
2
3
4
-------------------------
2
3
4

循环链表

循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即：this.head.next = this.head，并保证链表中最后一个节点的 next 属性，始终指向
head，如下图所示：

循环链表（CLink）实现

1. 构造函数

完整代码地址，这里，我们沿用单链表中的节点（Node）类，做为循环链表的节点类。不同的是，我们在 CLink 构造函数阶段，就要把 this.head 赋值给 this.head.next。

function CLink () {
    this.head = new Node('head');
    this.head.next = this.head;
}

2. append: 向链表节点增加一个元素

CLink.prototype.append = function (el) {
    var currNode = this.head;
    while (currNode.next != null) {
        currNode = currNode.next;
    }
    var newNode = new Node(el);
    newNode.next = currNode.next;
    currNode.next = newNode;
}

3. find：根据节点的值查找链表节点

CLink.prototype.find = function (el) {
    var currNode = this.head;
    while (currNode && currNode.el != el) {
        currNode = currNode.next;
    }
    return currNode;
}

4. insert：插入一个节点

CLink.prototype.insert = function (newEl, oldEl) {
    var newNode = new Node(newEl);
    var currNode = this.find(oldEl);
    if (currNode) {
        newNode.next = currNode.next;
        currNode.next = newNode;
    } else {
        throw new Error('未找到指定要插入节点位置对应的值！');
    }
}

5. display：展示链表元素节点

CLink.prototype.display = function () {
    var currNode = this.head.next;
    while (currNode && currNode != this.head) {
        console.log(currNode.el);
        currNode = currNode.next;
    }
}

6. 根据给定值寻找前一个节点

CLink.prototype.findPrev = function (el) {
    var currNode = this.head;
    while (currNode.next && currNode.next.el !== el) {
        currNode = currNode.next;
    }
    return currNode;
}

7. 删除给定值对应的节点

CLink.prototype.remove = function (el) {
    var prevNode = this.findPrev(el);
    if (prevNode.next != null) {
        prevNode.next = prevNode.next.next;
        prevNode.next.next = null;
    } else {
        throw new Error('找不到要删除的节点');
    }
}

循环链表（CLink）类测试

var circleLink = new CLink ();
circleLink.append(1);
circleLink.append(2);
circleLink.append(4);
circleLink.display();
console.log('---------------------------');
circleLink.insert(3, 2);
circleLink.display();
console.log('---------------------------');
circleLink.remove(4);
circleLink.display();

运行结果：

1
2
4
---------------------------
1
2
3
4
---------------------------
1
2
3

链表实战

题目： 传说在公元 1 世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的 40 个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案。他们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将 n 个人围成一圈，并且第 m 个人会被杀掉，计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。

题解：

function survival (n, m) {
    if (n <= 2) {
        return;
    }
    var clink = new CLink();
    for (var i = 1; i <= n; i++) {
        clink.append(i);
    }
    var p = clink.head,
        count = 0;
    while (n > 2) {
        p = p.next;
        if (p === clink.head) {
            continue;
        }
        count++;
        if (count === m) {
            clink.remove(p.el);
            count = 0;
            n--;
        }
    }
    console.log('幸存者：');
    clink.display();
}

测试：

survival(10, 3);

运行结果：

幸存者：
4
10

解析：

首先，我们把 n 个人按1-n的序号排好，然后按照每第 m 个人死亡来循环遍历循环链表，直到剩下两个人为止。

1 2 3 4 5 6 7 8 9 10
    x     x     x  
  x         x       
x             x    
        x