我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。


当前回答

嗯,我猜数组列表可以用在以下情况下:

您无法确定将会出现多少个元素 但是您需要通过索引随机访问所有元素

例如,您需要导入并访问联系人列表中的所有元素(您不知道其大小)

其他回答

到目前为止,数组是使用最广泛的数据结构。然而,链表以其独特的方式被证明是有用的,而数组是笨拙的——或者至少可以说是昂贵的。

链表在大小可变的情况下,对于实现堆栈和队列非常有用。链表中的每个节点都可以被推送或弹出,而不会影响大多数节点。在中间插入/删除节点也是如此。然而,在数组中,所有元素都必须移动,这在执行时间方面是一项昂贵的工作。

二叉树、二叉搜索树、哈希表和try是其中的一些数据结构——至少在C语言中——你需要链表作为构建它们的基本成分。

但是,在期望链表能够通过其索引调用任何任意元素的情况下,应该避免使用链表。

在现实中,内存局部性对实际处理的性能有很大的影响。

与随机访问相比,磁盘流在“大数据”处理中的使用越来越多,这表明围绕它构建应用程序可以在更大范围内显著提高性能。

如果存在按顺序访问数组的方法,则这是迄今为止性能最好的方法。如果性能很重要,那么至少应该考虑将此作为设计目标。

这个问题的简单答案可以用以下几点来给出:

当需要类似类型的数据元素集合时,将使用数组。而链表是混合类型数据链接元素(称为节点)的集合。 在数组中,可以在O(1)时间内访问任何元素。然而,在链表中,我们需要遍历整个链表,从头到所需的节点,花费O(n)时间。 对于数组,需要在初始时声明特定的大小。但是链表的大小是动态的。

嗯,我猜数组列表可以用在以下情况下:

您无法确定将会出现多少个元素 但是您需要通过索引随机访问所有元素

例如,您需要导入并访问联系人列表中的所有元素(您不知道其大小)

To add to the other answers, most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O(1) time. When the capacity of an array list is exceeded, a new, larger array is allocated internally, and all the old elements are copied over. Usually, the new array is double the size of the old one. This means that on average, adding new elements to the end of an array list is an O(1) operation in these implementations. So even if you don't know the number of elements in advance, an array list may still be faster than a linked list for adding elements, as long as you are adding them at the end. Obviously, inserting new elements at arbitrary locations in an array list is still an O(n) operation.

访问数组列表中的元素也比访问链表快,即使访问是顺序的。这是因为数组元素存储在连续的内存中,可以很容易地缓存。链表节点可能分散在许多不同的页面上。

如果知道要在任意位置插入或删除项,我建议只使用链表。数组列表在其他方面会更快。