链表有哪些用途？

Question

链接列表是否具有任何实际用途.许多计算机科学书籍将它们与数组进行比较,并说它们的主要优点是它们是可变的.但是,大多数语言都提供可变版本的数组.链接列表在现实世界中是否有任何实际用途,或者它们只是计算机科学理论的一部分？

Answer 1

它们绝对珍贵(在流行的双链接版本和不太流行的版本,但更简单,更快,适用时!单链接版本).例如,插入(或取出)的一个指定的"随机"点在一个(例如"阵列的可变版本"的新项目std::vector在C++)是O(N)其中N是阵列中的项目数,因为所有遵循(上平均一半)必须转移,这是一个O(N)操作; 在列表中,O(1)如果您已经有例如指向"上一个"项目的指针,那么它就是常量时间.像这样的Big-O差异绝对是巨大的 - 真实世界可用和可扩展程序与玩具,"家庭作业" - 级别之间的区别! - )

Answer 2

链接列表有很多用途.例如,实现最终用户看似可变数组的数据结构.

如果您使用的是提供各种集合实现的编程语言,那么许多集合将使用链接列表实现.使用这些语言进行编程时,您不会经常自己实现链接列表,但理解它们可能是明智的,这样您就可以理解您使用的库所做的权衡.换句话说,"只是计算机科学理论的一部分"的集合包含了您只需要编写可以正常工作的程序时需要知道的元素.

Answer 3

链接列表的主要应用是

• 用于表示多项式它表示两个多项式的加法/减法/乘法.例如:p1 = 2x ^ 2 + 3x + 7且p2 = 3x ^ 3 + 5x + 2 p1 + p2 = 3x ^ 3 + 2x ^ 2 + 8x + 9
• 在动态内存管理中在运行时分配和释放内存.*在Balancing paranthesis中的符号表中
• 代表稀疏矩阵

参考: - http://www.cs.ucf.edu/courses/cop3502h.02/linklist3.pdf

Answer 4

是的，它当然有用，原因有很多。

例如，您希望从列表中高效插入和删除的任何时候。要找到插入位置，您需要进行 O(N) 搜索，但是如果您已经拥有正确的位置，则要进行插入是 O(1)。

此外，您从使用链表中学到的概念可以帮助您学习如何制作基于树的数据结构和许多其他数据结构。

Answer 5

链接列表在现实世界中也有任何实际用途，

可以在建筑物内使用链表（双向）的示例（双重）。
-一个人必须经过所有楼层才能到达顶部（以链表形式显示）。
-一个人永远不能直接进入某个随机楼层（必须经过中间楼层/节点）。
-一个人永远不能超出顶层（在尾节点旁边被分配为null）。
-一个人永远不能超出地面/最后一层（在链表中，头节点之前被分配为空）。