教科书说，链表在末尾插入需要O（n），因为我们只保留一个指向起始节点的指针，并且必须从开始遍历到最后一个节点。但是，为什么不通过每次在链表中插入新项时更新来存储最后一个节点指针呢？它是在链表设计中定义的吗？
这正是一些标准库所做的事情。例如，在STL（C++）std::list中，在列表末尾附加一个元素或访问最后一个元素需要恒定的时间。虽然STL中的std::list是双链表，但一些细节请参阅std:：list。
您可以有一个尾随指针，但这取决于链表是否有序。如果你有一个排序的链表，你必须为链表的顶部保留一个指针，因为你可能需要在那里插入一个项目。在排序的链表中没有必要有一个尾随指针，但这会有所帮助。就链表的big-O表示法而言，您可能会遇到第一个元素是要查找的元素的情况，最好的情况是O（1），然而，链表的平均情况和最坏情况将是O（n）