为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
两件事:
毫无疑问,编写链表比使用数组要多一些工作,他想知道如何才能证明这些额外的工作是合理的。
使用c++时不要编写链表。使用STL即可。实现的难度不应该成为选择一种数据结构而不是另一种数据结构的理由,因为大多数数据结构都已经实现了。
至于数组和链表之间的实际区别,对我来说最重要的是你计划如何使用这种结构。我将使用术语向量,因为这是c++中可调整大小的数组的术语。
对链表进行索引很慢,因为必须遍历链表才能找到给定的索引,而向量在内存中是连续的,可以使用指针数学方法到达那里。
添加到链表的末尾或开头是很容易的,因为你只需要更新一个链接,而在向量中,你可能需要调整大小并复制内容。
从列表中删除一个项目很容易,因为您只需要断开一对链接,然后将它们重新连接在一起。从向量中移除一个项目可以更快也可以更慢,这取决于您是否关心顺序。在你想要删除的项目上面交换最后一项更快,而移动它之后的所有内容较慢,但保持顺序。
其他回答
根据你的语言,可以考虑以下一些缺点和优点:
C编程语言:当使用链表(通常是通过结构指针)时,必须特别注意不要泄漏内存。正如前面提到的,链表很容易洗牌,因为我们所做的只是改变指针,但是我们会记得释放所有的东西吗?
Java: Java具有自动垃圾收集功能,因此内存泄漏不会成为问题,但是对于高级程序员来说,隐藏了链表的实现细节。从列表中间删除节点等方法的过程比该语言的一些用户所期望的要复杂得多。
除了在列表中间进行添加和删除之外,我更喜欢链表,因为它们可以动态地增长和收缩。
为什么有人想要使用链表而不是数组?
这只是一个原因——如果你需要一个链表数据结构,而你所使用的编程语言不支持指针。
使用链接列表的人必须阅读。人们会再次爱上数组的。 它谈到了 无序执行,硬件预取,内存延迟等。
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。