目录
示例代码托管在：http://www.github.com/dashnowords/blogs
博客园地址：《大史住在大前端》原创博文目录
华为云社区地址：【你要的前端打怪升级指南】
一.概述
Timer模块相关的逻辑较为复杂，不仅包含java script层的实现，也包括C++编写的与底层libuv协作的代码，想要完整地看明白是比较困难的，本章仅以setTimeout这个API的实现机制为主线，讲述源码中的java script相关的实现部分，这部分只需要一些数据结构的基本知识就可以理解。
二. 数据结构
setTimeout这个API的实现基于两类基本数据结构，我们先来复习一下相关的特点。对数据结构知识比较陌生的小伙伴可以参考【野生前端的数据结构基础练习】系列博文自行学习，所有的章节都有示例代码。
2.1 链表
链表是一种物理存储单元上非连续的存储结构，存储元素的逻辑顺序是由链表中的指针链接次序来决定的。每一个节点包含一个存放数据的数据域和存放下一个节点的指针域（双向链表中指针数量为2）。链表在插入元素时的时间复杂度为O(1)（因为只影响插入点前后的节点，无论链表有多大），但是由于空间不连续的特点，访问一个未排序链表的指定节点时就需要逐个对比，时间复杂度为O(n)，比数组结构就要慢一些。链表结构也可以根据指针特点分为单向链表,双向链表和循环链表，Timer模块中使用的链表结构就是双向循环链表,Node.js中源码的底层数据结构实现都是独立的，链表的源码放在lib/internal/linkedlist.js：
'use strict';
function init(list) {
list._idleNext = list;
list._idlePrev = list;
}
// Show the most idle item.
function peek(list) {
if (list._idlePrev === list) return null;
return list._idlePrev;
}
// Remove an item from its list.
function remove(item) {
if (item._idleNext) {
item._idleNext._idlePrev = item._idlePrev;
}
if (item._idlePrev) {
item._idlePrev._idleNext = item._idleNext;
}
item._idleNext = null;
item._idlePrev = null;
}
// Remove an item from its list and place at the end.
function append(list, item) {
if (item._idleNext || item._idlePrev) {
remove(item);
}
// Items are linked with _idleNext -> (older) and _idlePrev -> (newer).
// Note: This linkage (next being older) may seem counter-intuitive at first.
item._idleNext = list._idleNext; //1
item._idlePrev = list;//2
// The list _idleNext points to tail (newest) and _idlePrev to head (oldest).
list._idleNext._idlePrev = item;//3
list._idleNext = item;//4
}
function isEmpty(list) {
return list._idleNext === list;
}链表实例初始化了两个指针，初始时均指向自己，_idlePrev指针将指向链表中最新添加进来的元素，_idleNext指向最新添加进来的元素，实现的两个主要操作为remove和append。链表的remove操作非常简单，只需要将删除项前后的元素指针加以调整，然后将被删除项的指针置空即可，就像从一串锁链中拿掉一节，很形象。
源码中的
idlePrev和idleNext很容易混淆，建议不用强行翻译为“前后”或者“新旧”，（反复记忆N次都记不住我也很无奈），直接按对应位置来记忆就可以了，爱翻译成什么就翻译成什么。
源码中的链表实现并没有提供指定位置插入的方法，append( )方法默认只接收list和item两个参数，新元素会被默认插入在链表的固定位置，这与它的使用方式有关，所以没必要实现完整的链表数据结构。append稍微复杂一些，但是源码中也做了非常详细的注释。首先需要确保插入的元素是独立的（也就是prev和next指针都为null），然后再开始调整，源码中的链表是一个双向循环链表，我们调整一下源码的顺序会更容易理解，其实插入一个元素就是要将各个元素的prev和next两个指针调整到位就可以了。先来看_idlePrev指针链的调整， 也就是指针调整代码中标记为2和3的语句：
item._idlePrev = list;//2
list._idleNext._idlePrev = item;//3这里可以把list看作是一个prev指针连接起来的单向链表，相当于将新元素item按照prev指针的指向添加到list和原本的list._idleNext指向的元素中间，而1和4语句是调整了反方向的next指针链：
item._idleNext = list._idleNext; //1
list._idleNext = item;//4调整后的链表以next指针为依据就可以形成反方向的循环链表，然后只需要记住list._idleNext指针指向的是最新添加的项就可以了。
如上图所示，next和prev分别可以作为链表的逻辑顺序形成循环链。
2.2 二叉堆
源码放在lib/internal/priority_queue.js中，一些博文也直接翻译为优先队列，它们是抽象结构和具体实现之间的关系，特性是一致的。二叉堆是一棵有序的完全二叉树，又以节点与其后裔节点的关系分为最大堆和最小堆。完全二叉树的特点使其可以很容易地转化为一维数组来存储，且不需要二外记录其父子关系，索引为i的节点的左右子节点对应的索引为2i+1和2i+2(当然左右子节点也可能只有一个或都不存在)。Node.js就使用一维数组来模拟最小堆。源码基本上就是这一数据结构和“插入”，“删除”这些基本操作的实现。
堆结构的使用最主要的是为了获得堆顶的元素，因为它总是所有数据里最大或最小的，同时堆结构是一个动态调整的数据结构，插入操作时会将新节点插入到堆底，然后逐层检测和父节点值的相对大小而“上浮”直到整个结构重新变为堆；进行移除操作（移除堆顶元素也是移除操作的一种）时，需要将堆尾元素置换到移除的位置，以维持