c++ - 在单链表中以恒定时间实现 Popback

Question

我想知道是否有可能(应该像 std::list 那样)在恒定时间内对单向链表执行 PopBack() 操作以及如何实现？

我假设我们存储头指针和尾指针。在这种情况下，PushBack()、PushFront()、PopFront() 可以很容易地在常数时间内实现。但是想不出在运行时间相同的情况下实现PopBack()的方法。

Answer 1

您不能在常数时间内为单个链表实现pop_back。为此，您需要知道最后一个元素之前的前一个元素，即最后一个元素应包含对前一个元素的引用。如果是这样，那么您将有一个双链表。

您可以在恒定时间内执行 push_back。我对 C++ 标准的建议之一是引入将支持 push_back 成员函数的 std::x_forward_list。在这种情况下，您将能够使用这样的单个链表来模拟队列。