何时在数组/数组列表上使用链表? [英] 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.

推荐答案

在以下情况下，链表优于数组:

1. 您需要从列表中恒定时间插入/删除(例如在时间可预测性绝对至关重要的实时计算中)

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

您不知道列表中有多少项目.对于数组，如果数组变得太大，您可能需要重新声明和复制内存

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

你不需要随机访问任何元素

you don't need random access to any elements

您希望能够在列表中间插入项目(例如优先级队列)

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

在以下情况下最好使用数组:

1. 你需要索引/随机访问元素

1. you need indexed/random access to elements

提前知道数组中元素的数量，以便为数组分配正确的内存量

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

按顺序迭代所有元素时需要速度.您可以在数组上使用指针数学来访问每个元素，而您需要根据链表中每个元素的指针查找节点，这可能会导致页面错误，从而导致性能下降.

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.

内存是一个问题.填充数组比链表占用更少的内存.数组中的每个元素只是数据.每个链表节点都需要数据以及一个(或多个)指向链表中其他元素的指针.

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 中的列表)为您提供数组的好处，但为您动态分配资源，因此您无需过多担心列表大小，并且您可以毫不费力地删除任何索引处的项目或重新洗牌周围的元素.在性能方面，数组列表比原始数组慢.

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屋！