大话数据结构 java版-java大话设计模式

分类：教程，数据结构，JavaScript

难度：★★★☆

翻译：疯狂的技术宅

英文：–cms-23392

说明：本文翻译自系列文章《Data Structures With JavaScript》，总共为四篇，原作者是在美国硅谷工作的工程师 Cho S. Kim 。由京程一灯老编 疯狂的技术宅 翻译。今天为大家奉上本系列的第三篇的下半部分。

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

第一篇：

第二篇：

第三篇：

第四篇：

从单链表到双链表

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

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

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

双向链表

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

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

双向链表的操作

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

NodeDoublyList双向链表的实现

现在开始写代码！

在实现中，将会创建一个名为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/3add(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/3searchNodeAt(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/3remove(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。——换句话说大话数据结构 java版，我们把指向已删除节点的指针，改为指向正确的节点。最后，把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)：树》

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

第一篇：

第二篇：

第三篇：

第四篇：

往日精选文章：