7

像链表这样的数据结构是纯粹用于实际编程的学术性的东西,还是你真的使用它们?它们是泛型涵盖的东西,因此您不需要构建它们(假设您的语言具有泛型)?我不是在争论理解它们是什么的重要性,只是在学术界之外使用它们。我从前端网络、后端数据库的角度提问。我敢肯定有人在某个地方建造了这些。我是从我的上下文中问的。

谢谢你。

编辑:泛型是不是让您不必构建链接列表等?

4

12 回答 12

4

这取决于您使用的语言和框架。大多数现代语言和框架不会让你重新发明这些轮子。相反,他们会提供类似List<T>HashTable 之类的东西。

编辑:

我们可能一直在使用链表,但没有意识到这一点。我们不必自己编写链表的实现,因为我们使用的框架已经为我们编写了它们。

您可能还对“泛型”感到困惑。您可能指的是通用列表类,例如List<T>. 这与非泛型类 List 相同,但元素始终是 type T。它可能实现为链表,但我们不必关心它。

我们也不必担心物理内存的分配、中断如何工作或如何创建文件系统。我们有操作系统可以为我们做到这一点。但我们可能在学校里同样被教导这些信息。

于 2009-06-22T14:29:10.343 回答
3

当然。现代语言中的许多“列表”实现实际上是链表,有时结合数组或哈希表进行直接访问(通过索引而不是迭代)。

链表(尤其是双向链表)在“现实世界”数据结构中非常常用。

我敢说每一种通用语言都有一个预构建的链表实现,或者作为语言原语、本地模板库(例如 C++)、本地库(例如 Java)或某些第 3 方实现(可能是开源的)。

话虽如此,在过去有几次,在为复杂的数据结构创建基础架构代码时,我自己从头开始编写了一个链表实现。有时完全控制实现是个好主意,有时您需要为经典实现添加“扭曲”以满足您的特定要求。只要您了解替代方案和权衡取舍,是否编写自己的实现代码就没有对错。在大多数情况下,当然在像 C# 这样的非常现代的语言中,我会避​​免使用它。

另一点是何时应该使用列表与数组/向量或哈希表。根据您的问题,我知道您知道这里的权衡,所以我不会过多讨论,但基本上,如果您的主要用途是按顺序遍历列表,并且列表大小可能会有很大差异,那么列表可能成为一个可行的选择。另一个考虑因素是插入的类型。如果一个常见的用例是“在中间插入”,那么列表比数组/向量具有显着优势。我可以继续,但这些信息在经典的 CS 书籍中:)

澄清:我的回答与语言无关,并且与泛型没有具体关系,据我所知,泛型具有链表实现。

于 2009-06-22T14:29:21.293 回答
2

单链表是获得内存高效的不可变列表的唯一方法,可以组合它来“改变”它。看看 Erlang 是如何做到的。它可能比数组支持的列表稍慢,但它在多线程和纯功能实现中具有非常有用的属性。

于 2009-06-22T15:06:17.757 回答
1

是的,现实世界中有使用链表的应用程序,有时我必须维护一个非常使用链表的巨大应用程序。

是的,链表包含在从 C++/STL 到 .net 的几乎所有类库中。

我希望它改用数组。

在现实世界中,由于分页和 CPU 缓存大小等因素,链表速度很慢(链表往往会传播数据,这使得您更有可能需要从不同的内存区域访问数据,而这在今天要慢得多计算机而不是使用将所有数据存储在一个序列中的数组)。

谷歌“参考地点”了解更多信息。

于 2009-06-22T14:33:47.150 回答
1

除了大学的家庭作业,从不使用手工制作的清单。

于 2009-06-22T14:36:10.157 回答
1

根据使用情况,链表可能是最佳选择。链表从列表前面删除比数组列表快得多。

在我维护的一个 Java 程序中,分析表明我可以通过从一个 ArrayList 移动到一个 LinkedList 来提高性能,这个 List 在开始时有很多删除。

于 2009-06-22T16:40:36.220 回答
0

多年来,我一直在开发业务线应用程序 (.NET),我只能想到一个使用链表的实例,即使这样我也不必创建对象。

这只是我的经验。

于 2009-06-22T14:29:38.827 回答
0

我会说这取决于使用情况,在某些情况下它们比典型的随机访问容器更快。

另外我认为它们被一些库用作底层集合类型,所以看起来像非链表的东西实际上可能是下面的一个。

于 2009-06-22T14:30:13.677 回答
0

在我上一家公司开发的 C/C++ 应用程序中,我们一直使用双向链表。它们对我们正在做的事情至关重要,即实时 3D 图形。

于 2009-06-22T14:31:23.007 回答
0

是的,各种数据结构在日常软件开发中都非常有用。在我知道的大多数语言(C/C++/Python/Objective-C)中,都有实现这些数据结构的框架,因此您不必重新发明轮子。

是的,数据结构不仅适用于学者,它们非常有用,没有它们你将无法编写软件(取决于你做什么)。

您在消息队列、数据映射、哈希表、保持数据有序、快速访问/删除/插入等中使用数据结构取决于需要做什么。

于 2009-06-22T14:42:16.837 回答
0

是的,我愿意。这一切都取决于情况。如果我不会在其中存储大量数据,或者特定应用程序需要 FIFO 结构,我会毫不犹豫地使用它们,因为它们实现起来很快。

但是,在我认识的其他开发人员的应用程序中,有时链表会非常适合,除非局部性差会导致大量缓存未命中。

于 2009-06-22T16:18:14.840 回答
0

我无法想象有很多程序不处理列表。当您需要处理不止一件事物时,就需要各种形式和形状的列表,因为您需要在某个地方存储这些事物。该列表可能是一个单/双链表、一个数组、一个集合、一个哈希表(如果您需要基于键索引您的事物)、一个优先级队列(如果您需要对其进行排序)等。

通常,您会将这些列表存储在数据库系统中,但您需要在某个地方从数据库中获取它们,将它们存储在您的应用程序中并对其进行操作,即使检索您填充到下拉列表中的一些事物列表很简单-向下组合框。

如今,在 C#、Python、Java 等语言中,您通常可以从必须实现自己的列表中抽象出来。这些语言带有大量抽象的容器,您可以在其中存储内容。通过标准库或内置于语言中。

您仍然可以学习这些主题,例如,如果您正在使用 C#,您想知道 ArrayList 是如何工作的,以及您是否会选择 ArrayList 或其他取决于您添加/插入/的需要搜索/随机索引这样的列表。

于 2009-06-22T16:44:25.033 回答