这些是最常用的Collection实现。

数组列表:

插入/删除在结尾一般O(1)最坏情况O(n) 中间插入/删除O(n) 检索任意位置O(1)

LinkedList:

在任何位置O(1)插入/删除(注意你是否引用了元素) 中间检索O(n) 检索第一个或最后一个元素O(1)

向量:不要用。它是一个类似于ArrayList的旧实现，但所有方法都是同步的。对于多线程环境中的共享列表，这不是正确的方法。

HashMap

在O(1)中按键插入/删除/检索

TreeSet 插入/删除/包含O(log N)

HashSet 在O(1)中插入/删除/包含/大小

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

数组列表适用于写一次读多次或追加程序，但不适用于从前面或中间进行添加/删除。

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

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

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

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

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

使用链表对数组和多项式操作进行基数排序。

这完全取决于你在迭代时所做的操作类型，所有数据结构都在时间和内存之间进行权衡，我们应该根据需要选择正确的DS。有些情况下，LinkedList比数组快，反之亦然。考虑数据结构上的三个基本操作。

搜索

由于array是基于索引的数据结构，搜索array.get(index)将花费O(1)时间，而linkedlist不是索引DS，因此您将需要遍历到index，其中index <=n, n是链表的大小，因此array在随机访问元素时比链表更快。

那么，这背后有什么好处呢?

As Arrays are contiguous memory blocks, large chunks of them will be loaded into the cache upon first access this makes it comparatively quick to access remaining elements of the array,as much as we access the elements in array locality of reference also increases thus less catch misses, Cache locality refers to the operations being in the cache and thus execute much faster as compared to in memory,basically In array we maximize the chances of sequential element access being in the cache. While Linked lists aren't necessarily in contiguous blocks of memory, there's no guarantee that items which appear sequentially in the list are actually arranged near each-other in memory, this means fewer cache hits e.g. more cache misses because we need to read from memory for every access of linked list element which increases the time it takes to access them and degraded performance so if we are doing more random access operation aka searching , array will be fast as explained below.

插入

这是简单和快速的LinkedList的插入是O(1)操作在LinkedList (Java)阵列相比,考虑数组充满的情况下,我们需要将内容复制到新数组如果数组完全使一个元素插入ArrayList O (n)在坏的情况下,而ArrayList还需要更新其指数年底如果你插入一些除了数组,链表的我们不必调整它,你只需要更新指针。

删除

它的工作原理类似于插入，在LinkedList中比在array中更好。