c++ - 在使用链表实现队列时，为什么插入复杂度为 O(1)？

Question

我读了我的书，其中写到使用链接列表从队列中插入和删除都具有 O(1) 复杂性，但我的理解是删除它将是 O(1)，但对于插入它是 O(n)，因为它'将遍历直到结束指针。

标签： c++

Answer 1

当使用链表实现队列时，链表是保存数据的内部数据结构，因为队列是 FIFO（先进先出），唯一的要求是元素需要从头部移除顺序和元素只需要添加到尾部。单链表是一个足够的容器，因为它维护了一个从头到尾通过元素的单向指针路径。包装队列的唯一要求是保存对头部的引用和对尾部的引用。

当一个元素被弹出/删除时，队列使用头指针在 O(1) 时间内删除第一个元素，并使用对下一个元素的链接引用作为新的头指针。当一个元素被推入/添加时，它用一个指向新元素的指针标记尾部元素，以保持一个完整的“队列”，并且还持有对添加元素的引用，以便它可以添加下一个元素 O （1次。