c++ - ADT链表和链表的区别

Question

ADT 列表实现和链表实现在队列方面有什么（真正的|显着的）区别 ？

此外，您能否推荐任何带有此类列表的视觉示例的网站？

Answer 1

真的很难理解这个问题，但在试图询问实际问题是什么时，我相信已经弄清楚了。所以我的假设是，问题是：“std::list 和 std::queue 有什么区别。@fatai：如果我错了，请纠正我。

std::list 是一个双向链表。列表的每个元素“知道”下一个和前一个元素。列表“知道”它的开始和结束。看这里：http ://www.cplusplus.com/reference/stl/list/

std::queue 是一个列表，具有特殊功能。此功能使您可以轻松地在前面插入元素，并从后面删除元素。看看这里： http ://www.cplusplus.com/reference/stl/queue/

如果你想拥有最少的功能，我会使用队列。队列针对其用途进行了优化。它还可以防止您做一些意外错误的事情（例如从中间删除一个元素）。

我希望这能回答你的（令人困惑的）问题。;-)

Answer 2

使用迭代器擦除和插入列表中间具有 O(n) 复杂性，因为在后台它必须移动所有其他元素。（使用向量 ADT 的特殊模型，但您甚至无法通过索引机制访问列表元素）。

在链表中，擦除和插入列表具有 O(1) 复杂性。它不需要移动操作的元素。即使在链表中搜索元素也像列表 ADT 一样具有 O(n) 复杂度。