JavaScript数据结构（3）：单向链表与双向链表

梦里梦外; 2022-06-11 00:47 272阅读 0赞

> **翻译**：疯狂的技术宅  
> **说明**：本文翻译自系列文章《Data Structures With JavaScript》，总共为四篇，原作者是在美国硅谷工作的工程师 Cho S. Kim 。这是本系列的第三篇。  
> **英文**：[https://code.tutsplus.com/articles/data-structures-with-javascript-singly-linked-list-and-doubly-linked-list–cms-23392][https_code.tutsplus.com_articles_data-structures-with-javascript-singly-linked-list-and-doubly-linked-list_cms-23392]

计算机科学中最常见的两种数据结构是单链表和双链表。

在我学习这些数据结构的时候，曾经问我的同伴在生活中有没有类似的概念。我所听到的例子是购物清单和火车。但是我最终明白了，这些类比是不准确的，购物清单更类似队列，火车则更像是一个数组。

随着时间的推移，我终于发现了一个能够准确类比单链表和双向链表的例子：寻宝游戏。 如果你对寻宝游戏和链表之间的关系感到好奇，请继续往下读。

# **单链表** #

在计算机科学中，单链表是一种数据结构，保存了一系列链接的节点。 每个节点中包含数据和一个可指向另一个节点的指针。

单链列表的节点非常类似于寻宝游戏中的步骤。 每个步骤都包含一条消息（例如“您已到达法国”）和指向下一步骤的指针（例如“访问这些经纬度坐标”）。 当我们开始对这些单独的步骤进行排序并形成一系列步骤时，就是在玩一个寻宝游戏。

现在我们对单链表有了一个基本的概念，接下来讨论单链表的操作

## **单链表的操作** ##

因为单链表包含节点，这两者的构造函数可以是两个独立的构造函数，所以我们需要些构造函数：`Node` 和 `SinglyList`

### **Node** ###

*  `data` 存储数据
 *  `next` 指向链表中下一个节点的指针

### **SinglyList** ###

*  `_length` 用于表示链表中的节点数量
 *  `head` 分配一个节点作为链表的头
 *  `add(value)` 向链表中添加一个节点
 *  `searchNodeAt(position)` 找到在列表中指定位置 n 上的节点
 *  `remove(position)` 删除指定位置的节点

## **单链表的实现** ##

在实现时，我们首先定义一个名为`Node`的构造函数，然后定义一个名为`SinglyList`的构造函数。

`Node` 的每个实例都应该能够存储数据并且能够指向另外一个节点。 要实现此功能，我们将分别创建两个属性：`data`和`next`。

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

下一步我们定义`SinglyList`:

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

`SinglyList` 的每个实例有两个属性：`_length`和`head`。前者保存链表中的节点数，后者指向链表的头部，链表前面的节点。由于新创建的`singlylist`实例不包含任何节点，所以`head`的默认值是`null`，`_length`的默认值是 `0`。

### **单链表的方法** ###

我们需要定义可以从链表中添加、查找和删除节点的方法。先从添加节点开始。

#### 方法1/3: `add(value)` ####

太棒了，现在我们来实现将节点添加到链表的功能。

SinglyList.prototype.add = function(value) { 
        var node = new Node(value),
            currentNode = this.head;
    
        // 1st use-case: an empty list 
        if (!currentNode) {
            this.head = node;
            this._length++;
    
            return node;
        }
    
        // 2nd use-case: a non-empty list
        while (currentNode.next) {
            currentNode = currentNode.next;
        }
    
        currentNode.next = node;
    
        this._length++;
    
        return node;
    };

把节点添加到链表会涉及很多步骤。先从方法开始。 我们使用`add(value)`的参数来创建一个节点的新实例，该节点被分配给名为`node`的变量。我们还声明了一个名为`currentNode`的变量，并将其初始化为链表的`_head`。 如果链表中还没有节点，那么`head`的值为`null`。

实现了这一点之后，我们将处理两种情况。

第一种情况考虑将节点添加到空的链表中，如果`head`没有指向任何节点的话，那么将该`node`指定为链表的头，同时链表的长度加一，并返回`node`。

第二种情况考虑将节点添加到飞空链表。我们进入`while`循环，在每次循环中，判断`currentNode.next`是否指向下一个节点。（第一次循环时，`CurrentNode`指向链表的头部。）

如果答案是否定的，我们会把`currentnode.next`指向新添加的节点，并返回`node`。

如果答案是肯定的，就进入`while`循环。 在循环体中，我们将`currentNode`重新赋值给`currentNode.next`。 重复这个过程，直到`currentNode.next`不再指向任何。换句话说，`currentNode`指向链表中的最后一个节点。

`while`循环结束后，使`currentnode.next`指向新添加的节点，同时`_length`加1，最后返回`node`。

#### 方法2/3: `searchNodeAt(position)` ####

现在我们可以将节点添加到链表中了，但是还没有办法找到特定位置的节点。下面添加这个功能。创建一个名为`searchNodeAt(position)` 的方法，它接受一个名为 `position` 的参数。这个参数是个整数，用来表示链表中的位置n。

SinglyList.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;
    };

在`if`中检查第一种情况：参数非法。

如果传给searchNodeAt(position)的索引是有效的，那么我们执行第二种情况 —— `while`循环。 在`while`的每次循环中，指向头的`currentNode`被重新指向链表中的下一个节点。

这个循环不断执行，一直到`count`等于`position`。

#### 方法3/3: `remove(position)` ####

最后一个方法是`remove(position)`。

SinglyList.prototype.remove = function(position) { 
        var currentNode = this.head,
            length = this._length,
            count = 0,
            message = {failure: 'Failure: non-existent node in this list.'},
            beforeNodeToDelete = null,
            nodeToDelete = null,
            deletedNode = null;
    
        // 1st use-case: an invalid position
        if (position < 0 || position > length) {
            throw new Error(message.failure);
        }
    
        // 2nd use-case: the first node is removed
        if (position === 1) {
            this.head = currentNode.next;
            deletedNode = currentNode;
            currentNode = null;
            this._length--;
    
            return deletedNode;
        }
    
        // 3rd use-case: any other node is removed
        while (count < position) {
            beforeNodeToDelete = currentNode;
            nodeToDelete = currentNode.next;
            count++;
        }
    
        beforeNodeToDelete.next = nodeToDelete.next;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
        this._length--;
    
        return deletedNode;
    };

我们要实现的`remove(position)`涉及三种情况：

1.  无效的位置作为参数传递。
2.  第一个位置（链表的的\`head）作为参数的传递。
3.  一个合法的位置（不是第一个位置）作为参数的传递。

前两种情况是最简单的处理。 关于第一种情况，如果链表为空或传入的位置不存在，则会抛出错误。

第二种情况处理链表中第一个节点的删除，这也是头节点。 如果是这种情况，就执行下面的逻辑：

1.  头被重新赋值给`currentNode.next`。
2.  `deletedNode`指向`currentNode`。
3.  `currentNode`被重新赋值为null。
4.  将的链表的长度减1。
5.  返回`deletedNode`。

第三种情况是最难理解的。 其复杂性在于我们要在每一次循环中操作两个节点的必要性。 在每次循环中，需要处理要删除的节点和它前面的节点。当循环到要被删除的位置的节点时，循环终止。

在这一点上，我们涉及到三个节点：  
`beforeNodeToDelete`, `nodeToDelete`, 和 `deletedNode`。删除`nodeToDelete`之前，必须先把它的`next`的值赋给`beforeNodeToDelete`的`next`，如果不清楚这一步骤的目的，可以提醒自己有一个节点负责链接其前后的其他节点，只需要删除这个节点，就可以把链表断开。

接下来，我们将`deletedNode`赋值给`nodeToDelete`。 然后我们将`nodeToDelete`的值设置为`null`，将列表的长度减1，最后返回`deletedNode`。

## 单向链表的完整实现 ##

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

# **从单链表到双链表** #

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

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

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

# **双向链表** #

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

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

## **双向链表的操作** ##

我们的链表将包括两个构造函数：`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)` 处理以下四种情况：

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

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

## **双向链表的完整实现** ##

# **总结** #

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

**欢迎扫描二维码关注公众号，每天推送我翻译的技术文章。**

![这里写图片描述][SouthEast]

[https_code.tutsplus.com_articles_data-structures-with-javascript-singly-linked-list-and-doubly-linked-list_cms-23392]: https://code.tutsplus.com/articles/data-structures-with-javascript-singly-linked-list-and-doubly-linked-list--cms-23392
[SouthEast]: /images/20220611/bf10df16c0204a1a90f05d512af17e6a.png