JavaScript数据结构(3-2)：单向链表与双向链表——双向链表篇

疯狂的技术宅

发布于 2019-03-28 11:16:23

5970

发布于 2019-03-28 11:16:23

分类：教程，数据结构，JavaScript 难度：★★★☆ 翻译：疯狂的技术宅英文：https://code.tutsplus.com/articles/data-structures-with-javascript-singly-linked-list-and-doubly-linked-list–cms-23392 说明：本文翻译自系列文章《Data Structures With JavaScript》，总共为四篇，原作者是在美国硅谷工作的工程师 Cho S. Kim 。由京程一灯老编疯狂的技术宅翻译。今天为大家奉上本系列的第三篇的下半部分。

《JavaScript 数据结构》系列回顾：

第一篇：JavaScript 数据结构（1）：什么是数据结构？

第二篇：JavaScript 数据结构（2-1）：栈与队列-栈篇

第三篇：JavaScript 数据结构（2-2）：栈与队列-队列篇

第四篇：JavaScript数据结构(3-1)：单向链表与双向链表——单向链表篇

从单链表到双链表

我们已经完整的实现了单链表，这真是极好的。现在可以在一个占用费连续的空间的链表结构中，进行添加、删除和查找节点的操作了。

然而现在所有的操作都是从链表的起始位置开始，并运行到链表的结尾。换句话说，它们是单向的。

可能在某些情况下我们希望操作是双向的。如果你考虑了这种可能性，那么你刚才就是描述了一个双向链表。

双向链表

双向链表具有单链表的所有功能，并将其扩展为在链表中可以进行双向遍历。换句话说，我们可从链表中第一个节点遍历到到最后一个节点；也可以从最后一个节点遍历到第一个节点。

在本节中，我们将重点关注双向链表和单链列表之间的差异。

双向链表的操作

我们的链表将包括两个构造函数：Node和DoublyList。看看他们是怎样运作的。

Node

data 存储数据。
next 指向链表中下一个节点的指针。
previous 指向链表中前一个节点的指针。

DoublyList

_length 保存链表中节点的个数
head 指定一个节点作为链表的头节点
tail 指定一个节点作为链表的尾节点
add(value) 向链表中添加一个节点
searchNodeAt(position) 找到在列表中指定位置 n 上的节点
remove(position) 删除链表中指定位置上的节点

双向链表的实现

现在开始写代码！

在实现中，将会创建一个名为Node的构造函数：

function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}

想要实现双向链表的双向遍历，我们需要指向链表两个方向的属性。这些属性被命名为previous和next。

接下来，我们需要实现DoublyList并添加三个属性：_length，head和tail。

与单链表不同，双向链表包含对链表开头和结尾节点的引用。由于DoublyList刚被实例化时并不包含任何节点，所以head和tail的默认值都被设置为null。

function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}

双向链表的方法

接下来我们讨论以下方法：add(value), remove(position), 和 searchNodeAt(position)。所有这些方法都用于单链表; 然而，它们必须备重写为可以双向遍历。

方法1/3 `add(value)`

DoublyList.prototype.add = function(value) {
    var node = new Node(value);
 
    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }
 
    this._length++;
     
    return node;
};

在这个方法中，存在两种可能。首先，如果链表是空的，则给它的head和tail分配节点。其次，如果链表中已经存在节点，则查找链表的尾部并把心节点分配给tail.next；同样，我们需要配置新的尾部以供进行双向遍历。换句话说，我们需要把tail.previous设置为原来的尾部。

方法2/3 `searchNodeAt(position)`

searchNodeAt(position)的实现与单链表相同。如果你忘记了如何实现它，请通过下面的代码回忆：

DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};
 
    // 1st use-case: an invalid position 
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position 
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};

方法3/3 `remove(position)`

理解这个方法是最具挑战性的。我先写出代码，然后再解释它。

DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
 
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
 
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }
 
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
 
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }
 
    this._length--;
 
    return message.success;
};

remove(position) 处理以下四种情况：

如果remove(position)的参数传递的位置存在, 将会抛出一个错误。
如果remove(position)的参数传递的位置是链表的第一个节点（head），将把head赋值给deletedNode，然后把head重新分配到链表中的下一个节点。此时，我们必须考虑链表中否存在多个节点。如果答案为否，头部将被分配为null，之后进入if-else语句的if部分。在if的代码中，还必须将tail设置为null —— 换句话说，我们返回到一个空的双向链表的初始状态。如果删除列表中的第一个节点，并且链表中存在多个节点，那么我们输入if-else语句的else部分。在这种情况下，我们必须正确地将head的previous属性设置为null —— 在链表的头前面是没有节点的。
如果remove(position)的参数传递的位置是链表的尾部，首先把tail赋值给deletedNode，然后tail被重新赋值为尾部之前的那个节点，最后新尾部后面没有其他节点，需要将其next值设置为null。
这里发生了很多事情，所以我将重点关注逻辑，而不是每一行代码。一旦CurrentNode指向的节点是将要被remove(position)删除的节点时，就退出while循环。这时我们把nodeToDelete之后的节点重新赋值给beforeNodeToDelete.next。相应的，把nodeToDelete之前的节点重新赋值给afterNodeToDelete.previous。——换句话说，我们把指向已删除节点的指针，改为指向正确的节点。最后，把nodeToDelete赋值为null。

最后，把链表的长度减1，返回deletedNode。

双向链表的完整实现

以下是单向链表的完整实现：

function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}
 function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}
 DoublyList.prototype.add = function(value) {
    var node = new Node(value);
 
    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }
 
    this._length++;
 
    return node;
};
 DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};
 DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
 
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
 
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }
 
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
 
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }
 
    this._length--;
 
    return message.success;
};

总结

本文中已经介绍了很多信息。如果其中任何地方看起来令人困惑，就再读一遍并查看代码。如果它最终对你有所帮助，我会感到自豪。你刚刚揭开了一个单链表和双向链表的秘密，可以把这些数据结构添加到自己的编码工具弹药库中！

请等待下一篇：《JavaScript数据结构(4)：树》

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2017-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

数据结构

javascript

node.js

本文分享自京程一灯微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度