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

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

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

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


当前回答

It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size. As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow. Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory. As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

其他回答

除了在列表中间进行添加和删除之外,我更喜欢链表,因为它们可以动态地增长和收缩。

It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size. As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow. Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory. As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

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

这只是一个原因——如果你需要一个链表数据结构,而你所使用的编程语言不支持指针。

两件事:

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

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

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

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

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

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

在数组中,您有权限在O(1)时间内访问任何元素。所以它适用于二进制搜索、快速排序等操作。链表则适合于插入删除,因为它在O(1)时间内。两者都有优点和缺点,选择一种而不是另一种归结为您想要实现什么。

—更大的问题是,我们能有一个两者的混合体吗?类似于python和perl实现的列表。