算法系列（二）-双向链表

其实之前版本的链表实现是比较中规中矩的，nodejs中有一个链表实现方式，用简单的几十行就实现了一个双向链表。

可以访问这里看看这个链表是怎么实现的。

对于Node至关重要的timer中，链表就大有用武之地，在node的timer中，这些操作都得到了优化：

新增一个定时器（insert）
移除一个已存在的定时器（remove）
处理定时器超时 (timeout)

下面我打算分析一下nodejs的源码中这个精简优雅的链表实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


'use strict';

//初始化一个链表，利用对象的属性当成节点，把Object当成链表
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) {
	//如果item存在后继节点，则把item的后续节点的prev指针指向item的前继节点
  if (item._idleNext) {
	item._idleNext._idlePrev = item._idlePrev;
  }
// 如果item存在前继节点，这需要把item的前继节点的next指针指向item的后续节点
  if (item._idlePrev) {
	item._idlePrev._idleNext = item._idleNext;
  }
// 断开item的所有指针
  item._idleNext = null;
  item._idlePrev = null;
}

// Remove an item from its list and place at the end.挂载
function append(list, item) {
// 如果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.很符合直觉的append，把原有的list的指向数据给了item，为接下来item挂载到list做准备
  item._idleNext = list._idleNext;
  item._idlePrev = list;

  // The list _idleNext points to tail (newest) and _idlePrev to head (oldest). list 的_idleNext 指向tail，_idlePrev指向head，list的_idleNext指向item，成功挂载
  list._idleNext._idlePrev = item;
  list._idleNext = item;
}

function isEmpty(list) {
  return list._idleNext === list;
}

Contents