为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
使用链表的唯一原因是插入元素很容易(删除也很容易)。
缺点可能是指针占用大量空间。
关于编码就更难了: 通常你不需要代码链表(或只需要一次)他们包括在内 STL 如果你还是要做的话,它就不那么复杂了。
其他回答
这里有一个快速的方法:移除物品更快。
另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是,更改往往是局部的——只影响数据结构局部部分的插入和删除的一两个指针。所以,你可以让多个线程在同一个链表上工作。更重要的是,可以使用cas类型的操作创建无锁版本,并完全避免沉重的锁。
使用链表,迭代器还可以在进行修改时遍历列表。在修改没有冲突的乐观情况下,迭代器可以在没有争用的情况下继续。
对于数组,任何修改数组大小的更改都可能需要锁定数组的很大一部分,事实上,这是在整个数组上没有全局锁的情况下完成的,因此修改会停止全局事务。
链表比数组的维护开销更大,它还需要额外的内存存储,所有这些都是一致的。但是有一些事情是数组做不到的。在很多情况下,假设你想要一个长度为10^9的数组你无法得到它,因为必须有一个连续的内存位置。链表可能是这里的救世主。
假设你想用数据存储多个东西,那么它们可以很容易地扩展到链表中。
STL容器通常在后台有链表实现。
这实际上是一个效率问题,在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的,即操作本身是O(1),而不是O(n)。如果您大量操作数据列表,这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型,并为所使用的算法选择最有效的数据类型。
为什么有人想要使用链表而不是数组?
这只是一个原因——如果你需要一个链表数据结构,而你所使用的编程语言不支持指针。