在一个单独链接列表中实现定时回弹

我想知道它是否有可能（它应该是std :: list似乎是这样做的）在单个链表上实现PopBack（）操作时间长短又如何？在一个单独链接列表中实现定时回弹

我假设我们存储头部和尾部指针。在这种情况下，PushBack（），PushFront（），PopFront（）可以很容易地在常量中实现。但不能想到用相同的运行时间来实现PopBack（）的方式。

2014-01-27 Arun

'std :: list'是双向链接的。 'std :: forward_list'，单独链接，没有'pop_back'方法。 –

您不能在一个固定时间内为单个链接列表实现pop_back。要做到这一点，你需要知道前一个元素，最后一个元素应该包含对前一个元素的引用。如果是这样，那么你将有一个双链表。

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

2014-01-27 21:20:31

Aaah .... ofcourse and that must the case with std :: list..it现在看起来像一个愚蠢的问题...我应该睡觉，它的3:00在印度这里！ – Arun

如果执行此操作，那么容器将具有双向迭代器。但是单个链表不能有双向迭代器。 –

回答