遍历链表需要的时间

bandaotidejia

设计定时器，需要每1s或1ms遍历全局链表，然后计算每个节点剩余秒数，但是假如链表很长，遍历是不是需要花很久时间。

如果说遍历链表不需要太多时间，为何有关链表遍历的时间复杂度问题面试时频出？

folklore

介个在Linux内核中有实现啊， 就是给定时器排序， 并保持时间为差值， 这样就只要Check第一个节点就好了， 不用遍历。

bandaotidejia

不太明白啊，为何只check第一个，其他的会自动减1？

bandaotidejia

哦，是不是这样：
每次减一直对第一个节点操作，然后移除第一个节点的时候，后面节点减少n。的确快了很多，但是每次移除一个节点，依然要遍历后面的所有节点。

folklore

回复 5# bandaotidejia


   

folklore

你马的中国的网络现在吃了我好多回复了。

保存的是差值， 比如 现在对列是 2 4 6 10 sec到期的。
现在队列将是：
2 2 2 4
要插入一个5sec到期的。
则新结点分别和 前两个结点比较， 大于则减去比较值
得
2 2 [1] 2 4， 因为剩余值1比2小， 所以找到插入位置。
再将后结点减去插入结点的值， 得：
2 2 1 1 4
就是最后结果。如果再插入一全5sec到期的， 可能就最成：
2 2 1 0 1 4