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

疯狂的技术宅

发布于 2019-03-28 15:30:37

6920

发布于 2019-03-28 15:30:37

文章被收录于专栏：京程一灯

翻译：疯狂的技术宅说明：本文翻译自系列文章《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

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

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

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

单链表

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

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

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

单链表的操作

因为单链表包含节点，这两者的构造函数可以是两个独立的构造函数，所以我们需要些构造函数：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)涉及三种情况：

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

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

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

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

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

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

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

单向链表的完整实现

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

function Node(data) {
    this.data = data;
    this.next = null;}
 function SinglyList() {
    this._length = 0;
    this.head = null;}
 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;};
 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;};
 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;
};

请等待本系列的第三篇文章：《JavaScript 数据结构（3）：单向链表与双向链表》

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

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

编程算法

node.js

数据结构

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

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

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

编程算法

node.js

数据结构

登录后参与评论

0 条评论

热度