当使用链表对数组/数组列表？ [英] When to use a linked list over an array/array list?

问题描述

我用了很多列表和数组，但我还没有遇到其中数组列表不能一样容易使用的情况下，如果不是，链表容易。我希望有人可以给我当链表特别是更好的一些例子。

I use a lot of lists and arrays but I have yet to come across a scenario in which the array list couldn't be used just as easily as, if not easier than, the linked list. I was hoping someone could give me some examples of when the linked list is notably better.

推荐答案

链表超过数组preferable时：

a）您需要恒定的时间插入/缺失从列表（如实时计算，时间predictability绝对是至关重要的）

a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

二）你不知道有多少项目会在列表中。使用数组，你可能需要重新申报，并复制内存，如果数组增长得太大。

b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

c）您不需要任何元素随机访问

c) you don't need random access to any elements

四）要能够在列表中（中间插入件如优先级队列）

d) you want to be able to insert items in the middle of the list (such as a priority queue)

数组是preferable时：

a）您需要的元素的索引/随机访问

a) you need indexed/random access to elements

b）您知道数组提前中的元素的数量，以便可以分配的存储器的正确量为阵列

b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

c）您通过序列中所有元素时，需要的速度。可以使用阵列上指针数学访问每个元件，而需要的基础上，指针在链表的每个元素，这可能导致页面故障可能导致性能命中来查找节点

c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

D）的内存，值得关注。填充阵列占用比链表更少的内存。数组中的每个元素仅仅是数据。每个链接列表节点要求数据以及一个（或多个）指针在链表中的其他元素。

d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.

数组列表（像那些在.NET）给你数组的好处，但动态地分配资源，为你，让你不必担心列表大小太多，你可以删除任何索引的项目没有任何努力或重新洗牌体周围。性能方面，是的ArrayList比生数组慢。

Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

这篇关于当使用链表对数组/数组列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！