何时应使用链接列表的真实示例是什么?

2022-09-01 11:05:43

另一位程序员提到,在他的职业生涯中,他们没有发现在任何专业软件中使用链表数据结构的用例。我想不出任何好的例子。他主要是C#和Java开发人员。

任何人都可以举一些例子,说明这是解决特定现实世界问题的正确数据结构?

相关:什么是实际的、现实世界中的链接列表示例?


答案 1

与可比较的数据结构(如静态或动态扩展数组)相比,链表具有多项优势。

  1. LinkedLists不需要连续的内存块,因此可以帮助减少内存碎片
  2. LinkedList支持有效删除元素(动态数组通常强制所有元素发生偏移)。
  3. LinkedLists支持元素的高效添加(如果特定添加超过当前容量,动态数组可能会导致重新分配+复制)

任何这些优势对程序具有重大价值的地方(LinkedList的缺点可以忽略不计)都将是使用LinkedList的地方。


答案 2

一个实际的例子是FIFO队列。一个简单的基于数组的列表对此非常糟糕,因为您需要在一端添加并在另一端删除,其中一个操作将是O(n)和基于数组的列表(除非您添加额外的逻辑来处理开始和结束索引),而两者都是带有链接列表的O(1),而无需额外的努力。


推荐