JavaScript 链表

808 阅读8分钟

原文链接

前言

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

背景

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

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

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

定义

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

default

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

default

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

default

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

default

链表节点(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

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

双向链表

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

default

双向链表节点(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:向链表结尾添加一个节点

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:查找给定的节点

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: 向链表节点增加一个元素

DLink.prototype.append = function (el) {
    var currNode = this.head;
    while (currNode.next != null && currNode.next != this.head) {
        currNode = currNode.next;
    }
    var newNode = new Node(el);
    newNode.next = currNode.next;
    newNode.prev = currNode;
    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