数据结构JavaScript描述（二）

摘要：在上一篇文章中，我们了解了队列和栈的描述，现在让我们来了解一下单链表和双向链表的实现。单链表和双向链表具有以下特点可动态分配空间，但不能随机访问。

在上一篇文章中，我们了解了队列和栈的JavaScript描述，现在让我们来了解一下 单链表 和双向链表 的实现。本文的代码并非所有都由本人所写，只是出于学习目的，在此分享出来，并加上一定的解释，便于大家学习。

</>复制代码 
本系列文章的代码可在https://github.com/HolyZheng/...找到。

我们直入话题：

单链表 是存储结构的一种，它具有以下特点：

单链表不可随机访问

单链表不需要占连续的存储空间，可动态分配

插入与删除操作不需要移动多个元素

每个节点既存储数据，又同时存储指向下一节点的地址

现在我们创建一个单链表，并给它添加add、searchNode、remove 三个方法。
创建一个单链表：

</>复制代码 
//单链表
function SinglyList () {
    this._length = 0;
    this.head = null;
}

这个单链表暂时又两个属性： _length 链表的长度，head 链表头节点。

每一个节点需要存储数据，还要指向下一节点，所以为每个节点创建一个node类：

</>复制代码 
//结点
function Node (data) {
    this.data = data;
    this.next = null;
} 

node类 具有两个属性，data 存储数据，next 指向下一节点。
现在我们为它添加几个基本的方法：add、searchNode 和 remove 函数。我们先实现 add 方法，给单链表添加节点。在 add 方法中我们需要考虑两中情况，分别为：单链表为空和单链表不为空。

</>复制代码 
//add方法
SinglyList.prototype.add = function (value) {
    var node = new Node(value),
        currentNode = this.head;
        
        //1st：当单链表为空时
        if (!currentNode) {
            this.head = node;
            this._length++;
            return node;
        }
        //2nd：单链表不为空
        while (currentNode.next) {
            currentNode = currentNode.next;
        }
        currentNode.next = node;
        this._length++;
        return node;
}

可以看到在代码中，我们先定义了一个 currentNode 变量，指向 this.head ，然后判断如果当前链表为空，直接将新节点赋值给 this.head ，如果不为空，先将currentNode指向最后的节点，然后再执行 currentNode.next = node将新节点添加到链表的末尾。
再来实现 searchNode 方法：
searchNode方法的作用是搜索特定位置的节点

</>复制代码 
//searchNode方法
SinglyList.prototype.searchNode = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"};
    
    //1st：位置position非法
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    } 
    //2nd：位置position合法
    for (var i = 1; i < position; i++) {
        currentNode = currentNode.next;
    }
    return currentNode;
}

我们很简单就实现了这个方法，先检测链表是否为空和查询的位置是否合法，不为空且位置合法的话，利用一个循环，将currentNode指向特定的position，然后就可以访问到需要的节点了。

我们现在来看一下最后的一个方法： remove。 remove方法比起前两个方法的话，要复杂一点，因为要考虑删减了一个元素之后，还要保持整个链表的连续性。

</>复制代码 
//remove方法
SinglyList.prototype.remove = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"},
        beforeNodeToDelete = null,
        nodeToDelete = null;
    
    //1st 位置position非法
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
    //2nd 位置position为 1
    if (position === 1) {
        this.head = currentNode.next;
        nodeToDelete = currentNode;
        currentNode = null;
        this._length--;
        return nodeToDelete;
    }
    //3rd position为其他位子
    for(var i = 1; i < position; i++) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        
        currentNode = currentNode.next;
    }
    beforeNodeToDelete.next = nodeToDelete.next;
    currentNode = null;
    this._length--;
    return nodeToDelete;
}

首先检查 position 的值是否合法，然后看position的值是否为 1，如果为 1 那就好办了，将 this.head 指向原this.head.next，然后长度减 1 即可。如果position为其他位置，那就要先拿到 要删除节点的前一节点 <和 要删除的节点 然后将前一节点的next指向要删除节点的next，以保持删除节点后，链表的连续。理解了这点，那就基本可以理解代码了。

双向链表就是在单链表的基础上，添加了一个指向当前结点的前驱的变量，这样就可以方便的由后继来找到其前驱，就可以双向的访问链表。
同样我们先来创建一个 结点类 ：

</>复制代码 
//节点类
function Node (value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}

可以看到这里多了一个 this.previous ，作用就是指向它的前驱。

然后再来看一下双向链表这个类：

</>复制代码 
function DoublyList () {
    this._length = 0;
    this.head = null;
    this.tail = null;
}

比起 单链表， 双向链表 多了一个指向尾结点的 this.tail。
同样，在这里我们实现 add、searchNode 和 remove 三个方法。先来看 add 方法：

</>复制代码 
//add方法
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;
}

在插入新结点的时候我们一如既往的需要检查链表是否为空，如果链表为空，就将 this.head 和 this.tail 都指向新结点，如果不为空，那就将新结点添加到链表末尾，并将新结点的 previous 指向原 this.tail 。这样就完成了 add 方法。

searchNode方法：

</>复制代码 
//searchNode
DoublyList.prototype.searchNode = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"};
    if(length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    for (var i = 1; i < position; i++) {
        currentNode = currentNode.next;
    }
    return currentNode;
}

双向链表的searchNode方法和单链表的差不多，都是借助循环直接拿到要访问的结点。

最后是最复杂的remove方法

</>复制代码 
//remove方法
DoublyList.prototype.remove = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        afterNodeToDelete = null;
    
    //1st: 位置position非法
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    //2nd 位置为第一个节点
    if (position === 1) {
        nodeToDelete = this.head;
        this.head = currentNode.next;
        if (this.head) {
            this.head.previous = null;
        } else {
            this.tail = null;
        }
    //3rd 位置为最后一个节点
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    //4th 位置为其他节点
    } else {
        for (var i = 1; i < position; i++) {
            currentNode = currentNode.next;
        }
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
    }
    this._length--;
    return nodeToDelete;
}

remove方法要对传进来的 position 进行判断，分成 4 种情况，

分别为：

position非法，抛出错误。

position为 1，将this.head 指向下一个结点，然后将this.head.previous = null，这时要判断一下 this.head 是否为空，如果为空就表明这个双向链表原本只有一个结点，所以 remove 后 需要把 this.tail = null 。

当 position 为最后一个结点时，我们把 this.tail 前移this.tail = this.tail.previous，此时 this.tail 指向倒数第二个结点，再执行this.tail.next = null，就把最后一个结点remove掉了

最复杂的情况，position 为其他位置，我们先定位到要remove掉的结点，然后将要删除结点的前一结点与要删除结点的后一结点链接起来，就把要删除的结点remove掉了，既beforeNodeToDelete.next = afterNodeToDelete ; afterNodeToDelete.previous = beforeNodeToDelete

单链表和双向链表，为存储结构的一种。

单链表和双向链表具有以下特点：

可动态分配空间，但不能随机访问。

插入和删除操作不需要移动多个元素

每个节点既存储数据，又同时存储指向下一节点的地址

双向链表为在单链表的基础上，添加了一个指向当前结点的前驱的变量，这样就可以方便的由后继来找到其前驱，就可以双向的访问链表。