为什么有人想要使用链表而不是数组?

毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。

我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?

这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。


当前回答

使用链表的唯一原因是插入元素很容易(删除也很容易)。

缺点可能是指针占用大量空间。

关于编码就更难了: 通常你不需要代码链表(或只需要一次)他们包括在内 STL 如果你还是要做的话,它就不那么复杂了。

其他回答

这实际上是一个效率问题,在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的,即操作本身是O(1),而不是O(n)。如果您大量操作数据列表,这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型,并为所使用的算法选择最有效的数据类型。

两件事:

毫无疑问,编写链表比使用数组要多一些工作,他想知道如何才能证明这些额外的工作是合理的。

使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由,因为大多数数据结构都已经实现了。

至于数组和链表之间的实际区别,对我来说最重要的是你计划如何使用这种结构。我将使用术语向量,因为这是c++中可调整大小的数组的术语。

对链表进行索引很慢,因为必须遍历链表才能找到给定的索引,而向量在内存中是连续的,可以使用指针数学方法到达那里。

添加到链表的末尾或开头是很容易的,因为你只需要更新一个链接,而在向量中,你可能需要调整大小并复制内容。

从列表中删除一个项目很容易,因为您只需要断开一对链接,然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢,这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快,而移动它之后的所有内容较慢,但保持顺序。

当集合不断增加和减少时,链表尤其有用。例如,很难想象尝试使用数组实现一个Queue(添加到末尾,从前面删除)—您将花费所有时间向下移动内容。另一方面,对于链表来说,这是微不足道的。

这里有一个快速的方法:移除物品更快。

由于数组本质上是静态的,因此所有的操作 比如内存分配发生在编译的时候 只有。因此处理器必须在运行时投入更少的精力。