《算法基础》——3.4　有序链表

3.4　有序链表

有时，让链表中的项保持有序是十分方便的。当将一个新项加入有序链表时，需要搜索链表来找到该项所属位置，并更新相应的链接来插入该项。
下面的伪代码显示了在一个有序链表中插入一个项的算法：

在最坏的情况下，该算法可能需要遍历整个链表为新项找到正确的位置。因此，如果该链表保存N个单元格，其运行时间为O(N)。虽然不能提高理论运行时间，但是可以通过添加底端哨兵使算法更简单而且在实际运行中更加快速。如果将底部哨兵的Value设定成一个比单元格中任意可能存储的Value值都大的值，就可以删除对top.Next!=null的测试。可以这样做是因为这个代码最终会为新的单元格找到一个合适的位置，即使该位置就在底部哨兵之前。
例如，如果单元格中的Value为使用ASCII字符表示的名字，可以设置底部哨兵的Value为“~”因为“~”字符在所有可用的字符中排名最后。如果单元格的Value为整数，就可以以最大可能的整数值来设置底部哨兵的Value。 （在大多数的32位系统中，该值为2 147 483 647。）
下面的伪代码显示了修改后的算法，并假设链表具有一个拥有最大值的底部哨兵：