为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
为什么有人想要使用链表而不是数组?
这只是一个原因——如果你需要一个链表数据结构,而你所使用的编程语言不支持指针。
其他回答
Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。
链表是一个动态的数据结构,因此它可以在运行时通过分配和释放内存来增长和收缩。所以不需要给出链表的初始大小。插入和删除节点非常容易。
2-链表的大小可以在运行时增加或减少,因此没有内存浪费。在数组的情况下,有很多内存浪费,比如如果我们声明一个大小为10的数组,只存储6个元素,那么4个元素的空间就浪费了。链表中不存在这样的问题,因为只有在需要时才分配内存。
3-数据结构,如堆栈和队列可以很容易地实现使用链表。
数组和链表之间的区别在于,数组是基于索引的数据结构,每个元素都与一个索引相关联,而链表是使用引用的数据结构,每个节点都被引用到另一个节点。在数组大小是固定的,而在链表大小是不固定的。
这实际上是一个效率问题,在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的,即操作本身是O(1),而不是O(n)。如果您大量操作数据列表,这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型,并为所使用的算法选择最有效的数据类型。
这里有一个快速的方法:移除物品更快。