为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
除了在列表中间进行添加和删除之外,我更喜欢链表,因为它们可以动态地增长和收缩。
其他回答
没有人再编写自己的链表了。那太愚蠢了。使用链表需要更多代码的前提是错误的。
如今,构建链表只是学生们的一个练习,以便他们能够理解这个概念。相反,每个人都使用预先构建的列表。在c++中,根据我们问题中的描述,这可能意味着stl向量(#include <vector>)。
因此,选择链表还是数组完全是权衡每个结构相对于应用程序需求的不同特征。克服额外的编程负担应该对决策没有任何影响。
这里有一个快速的方法:移除物品更快。
两件事:
毫无疑问,编写链表比使用数组要多一些工作,他想知道如何才能证明这些额外的工作是合理的。
使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由,因为大多数数据结构都已经实现了。
至于数组和链表之间的实际区别,对我来说最重要的是你计划如何使用这种结构。我将使用术语向量,因为这是c++中可调整大小的数组的术语。
对链表进行索引很慢,因为必须遍历链表才能找到给定的索引,而向量在内存中是连续的,可以使用指针数学方法到达那里。
添加到链表的末尾或开头是很容易的,因为你只需要更新一个链接,而在向量中,你可能需要调整大小并复制内容。
从列表中删除一个项目很容易,因为您只需要断开一对链接,然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢,这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快,而移动它之后的所有内容较慢,但保持顺序。
根据你的语言,可以考虑以下一些缺点和优点:
C编程语言:当使用链表(通常是通过结构指针)时,必须特别注意不要泄漏内存。正如前面提到的,链表很容易洗牌,因为我们所做的只是改变指针,但是我们会记得释放所有的东西吗?
Java: Java具有自动垃圾收集功能,因此内存泄漏不会成为问题,但是对于高级程序员来说,隐藏了链表的实现细节。从列表中间删除节点等方法的过程比该语言的一些用户所期望的要复杂得多。
当集合不断增加和减少时,链表尤其有用。例如,很难想象尝试使用数组实现一个Queue(添加到末尾,从前面删除)—您将花费所有时间向下移动内容。另一方面,对于链表来说,这是微不足道的。