Nodejs中的双向链表模块-linklist

在其他的后端语言中,有一个很重要的概念,就是链表,链表分为很多中,分为单向链表,双向链表,循环链表,在nodejs中,也有这么一个模块,专门来模拟链表的功能,至于这个模块,是实现的哪种链表,就让我们接下来慢慢看一下吧,至于这里为什么要插入这个模块,因为在本来要写的net模块中,牵扯到了一些东西,是基于该模块实现的,如果不能好好的理解这里,那么接下来的学习,可能就会出现一些问题。

概总

还有一个重要的原因是,nodejs的事件循环机制,是如何实现的,当我看到这一章的时候,也在想,事件的循环机制,是不是也有该模块的一些影子在其中呢,这些都是后话,因为我也是在慢慢学习,希望学习完该模块之后,能对这些都有一些简单的了解,能让我后面的学习,变得更加顺利。

该模块就是_linklist模块,这里至于叫做什么模块,我也没有找到它具体的名字,估计是不对外开放的吧,按照我们平常JS的书写模式的话,如果一个函数名是以”_”开头的话,表明该函数或者变量,是一个私有变量,外部使用时,就要注意一下了,所以,这里,关于该模块的命名,就不多说了,就以_linklist命名吧。

关于_linklist

首先,来看下_linklist模块中,支持了哪些方法,用我们常用的示例:


var linklist = require("_linklist");

console.log(linklist)


运行之后,在控制台,就会打印出如下的内容,它的格式如下


{
    init: [Function: init],
    // 初始化一个链表

    peek: [Function: peek],
    // 获取一个节点的前置节点

    shift: [Function: shift],
    // 获取一个节点的前置节点,并把该前置节点,从链表中剔除,返回该前置节点

    remove: [Function: remove],
    // 从链表中,删除该节点

    append: [Function: append],
    // 把一个节点,插入到另外一个节点的后面

    isEmpty: [Function: isEmpty]
    // 判断该节点所在的链表是否只有它本身,如果是,则认为是在一个空链表

}


看下源码

这里,我改变了文章的顺序,先来看下本模块的源码,之后,我们继续去看一些实例,之所以先看源码,是因为本模块的内容,在网络和我自己的Nodejs的书中,是没有提及到的,所以,只能是先看源码,然后来猜测这些方法,到底是实现了哪些功能。


'use strict';

function init(list) {
    // 初始化链表,并给该链表添加两个属性,指向它本身
    // 表示,该对象没有和任何其他对象构成链表
    list._idleNext = list;
    list._idlePrev = list;
}
exports.init = init;

// show the most idle item
function peek(list) {
    // 查看list对象的前置对象,如果是它本身,表示么有前置的链表值
    // 这个时候,直接返回null
    // 如果有,那么返回该节点的前一个节点
    if (list._idlePrev == list) return null;

    return list._idlePrev;
}
exports.peek = peek;

// remove the most idle item from the list
function shift(list) {
    // shift和Array的shift基本类似
    // 把该节点的前一个节点,从当前所在的链表中,剔除
    // 并且返回剔除的该节点数据
    // 一个疑惑,这个时候,为什么没有判断,该前置节点,是不是list本身呢?
    var first = list._idlePrev;

    // 调用remove方法,从所在的链表中,去除first的节点
    remove(first);
    return first;
}
exports.shift = shift;

// remove a item from its list
function remove(item) {
    // 把item从它所在的链表中,去除
    if (item._idleNext) {
        // 先找到item的下一个节点,改变这个节点的前置节点,设置为item的前置节点
        item._idleNext._idlePrev = item._idlePrev;
    }

    if (item._idlePrev) {
        // 找到item的前置节点,那这个节点的后置节点,设置为item的后置节点
        item._idlePrev._idleNext = item._idleNext;
    }

    // 经过前面的设置,那么在item的链表中,就无法循环再找到item的节点了

    // 把item的前置和后置节点都置为null,则item也无法再找到它原本所在的节点了
    item._idleNext = null;
    item._idlePrev = null;
}
exports.remove = remove;

// remove a item from its list and place at the end.
function append(list, item) {
    // 把item的节点,插入到list的后面去

    // 先去掉item节点本身所在的节点,以方该item在其他的节点
    // append的方法,和原生JS中的appendChild方法类似,都会把原来的数据给删除掉
    remove(item);

    // item的后置节点,设置为list的后置节点
    item._idleNext = list._idleNext;

    // list原本的后置节点的前置节点,设置为item
    list._idleNext._idlePrev = item;

    // item的前置节点,设置为list
    item._idlePrev = list;

    // list的新的后置节点,设置为item
    list._idleNext = item;
}
exports.append = append;

function isEmpty(list) {
    // 判断是否为空链表
    return list._idleNext === list;
}
exports.isEmpty = isEmpty;


上述的步伐内容,是linklist模块的所有代码,它不基于任何其他的模块,只是单纯的一些基础操作,属于比较简单的操作,从上面的注释中,应该也能想象到这些方法的使用了,那么接下来,我们就继续去看一些例子吧,都是比较简单的示例。

_linklist部分的示例


var linklist = require("_linklist");

var list1 = {"value":1},
    list2 = {"value":2},
    list3 = {"value":3};

// 初始化list1为初始链表
linklist.init(list1);

// 把list2插入到list1之后
linklist.append(list1,list2);
console.log(list2);

// 把list3插入到list1之后
linklist.append(list1,list3);
console.log(list3);

// 把list3的前置链表返回
console.log(linklist.peek(list3));

// 把list3的前置链表删除,并返回删除的链表
console.log(linklist.shift(list3));
console.log(list3);

// 删除list2节点
linklist.remove(list2);
console.log(list3);


该示例中,包含了该模块中的所有的使用方法,append的一个使用示例,这里没有包含到,如果您记得源码中的注释,那么,应该记得一点,appendJS中的appendChild方法一样,会把原来所在的删除掉,所有,如果一个节点原本属于A链表,而之后使用append方法,把这个节点添加到B链表中,那么这个节点也同时,在A链表中被remove掉了。

还有一点,需要注意的,被操作的节点,必须是对象,如果是一个字符串,那么久会出问题,这个示例就不在这里举例了。

并且,从上面的源码以及示例中,也可以看到一个情况,该链表属于双向循环链表。

总结

本篇文章,不属于Nodejs的一个模块,只能算是其中的一个常用方法,其定义为基本的私有模块的意思,估计也是因为,这个模块,可能不会被Nodejs的使用者用到。

至于,文章开头说的,该模块,是否和Nodejs的事件循环机制有一定的联系,暂时不知道,希望以后通过学习,能更深入的了解Nodejs

个人理解,如果有什么错误,请指出。

参考:Nodejs源码

本文地址:http://www.zhangyunling.com/?p=450

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>