为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的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.
为什么是链表而不是数组?有些人已经说过,插入和删除的速度更快。
但也许我们不需要生活在两者的限制下,同时获得两者的优点……是吗?
对于数组删除,您可以使用'Deleted'字节来表示一行已被删除的事实,因此不再需要重新组织数组。为了减轻插入或快速更改数据的负担,可以使用链表。然后,在引用它们的时候,让你的逻辑先搜索一个,再搜索另一个。因此,将它们结合使用可以使您获得两者的最佳效果。
If you have a really large array, you could combine it with another, much smaller array or linked list where the smaller one hold thes 20, 50, 100 most recently used items. If the one needed is not in the shorter linked list or array, you go to the large array. If found there, you can then add it to the smaller linked list/array on the presumption that 'things most recently used are most likey to be re-used' ( and yes, possibly bumping the least recently used item from the list ). Which is true in many cases and solved a problem I had to tackle in an .ASP security permissions checking module, with ease, elegance, and impressive speed.
使用链表的唯一原因是插入元素很容易(删除也很容易)。
缺点可能是指针占用大量空间。
关于编码就更难了: 通常你不需要代码链表(或只需要一次)他们包括在内 STL 如果你还是要做的话,它就不那么复杂了。
链表比数组的维护开销更大,它还需要额外的内存存储,所有这些都是一致的。但是有一些事情是数组做不到的。在很多情况下,假设你想要一个长度为10^9的数组你无法得到它,因为必须有一个连续的内存位置。链表可能是这里的救世主。
假设你想用数据存储多个东西,那么它们可以很容易地扩展到链表中。
STL容器通常在后台有链表实现。
快速插入和删除确实是链表的最佳参数。如果您的结构是动态增长的,并且不需要对任何元素进行固定时间的访问(例如动态堆栈和队列),链表是一个很好的选择。