以下是ArrayList和LinkedList以及CopyOnWrite ArrayList中的Big-O符号：

阵列列表

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

链表

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite阵列列表

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

基于这些，您必须决定选择什么。：）

我应该何时使用LinkedList？大多数情况下使用堆栈时，或使用缓冲区时。我应该何时使用ArrayList？只有在使用索引时，否则您可以将HashTable与链接列表一起使用，那么您将得到：

哈希表+链接列表

通过密钥O（1）访问，通过键O（1）插入，通过键O（1）拆除在使用版本控制时，使用O（1）实现RemoveAll/SetAll有一个技巧

这似乎是一个很好的解决方案，在大多数情况下，你应该知道：HashTable占用了大量磁盘空间，所以当您需要管理1000000个元素列表时，它可能会变得很重要。这可能发生在服务器实现中，但在客户端中很少发生。

还可以看看红黑树

随机访问日志（n），插入日志（n），删除日志（n）

让我们将LinkedList和ArrayList与以下参数进行比较：

1.实施

ArrayList是列表接口的可调整大小的数组实现，而LinkedList是列表接口的双重链接列表实现。

2.性能

get（int索引）或搜索操作ArrayList get（int索引）操作在恒定时间内运行，即O（1）而LinkedList get（int索引）操作运行时间为O（n）。ArrayList比LinkedList更快的原因是ArrayList对其元素使用基于索引的系统，LinkedList不为其元素提供基于索引的访问，因为它从开始或结束（以较近者为准）迭代以检索指定元素索引处的节点。insert（）或add（Object）操作与ArrayList相比，LinkedList中的插入通常很快。在LinkedList中，添加或插入是O（1）操作。在ArrayList中，如果数组已满（即最坏情况），则调整数组大小并将元素复制到新数组会产生额外的成本，这使得ArrayList的加法运算运行时为O（n），否则为O（1）。删除（int）操作LinkedList中的移除操作通常与ArrayList相同，即O（n）。在LinkedList中，有两个重载的移除方法。一个是remove（），没有任何参数，它会删除列表的头部，并在恒定时间O（1）内运行。LinkedList中的另一个重载remove方法是remove（int）或remove（Object），它删除作为参数传递的Object或int。此方法遍历LinkedList，直到找到Object并将其从原始列表中取消链接。因此，该方法运行时为O（n）。在ArrayList中，remove（int）方法涉及将元素从旧数组复制到新的更新数组，因此其运行时为O（n）。

3.反向迭代器

LinkedList可以使用descendingIterator（）反向迭代，同时ArrayList中没有descendingIterator（），因此我们需要编写自己的代码以反向遍历ArrayList。

4.初始容量

如果构造函数没有重载，那么ArrayList将创建一个初始容量为10的空列表，而LinkedList只构建没有任何初始容量的空列表。

5.内存开销

与ArrayList相比，LinkedList中的内存开销更大，因为LinkedList的节点需要维护下一个和上一个节点的地址。虽然在ArrayList中，每个索引仅保存实际对象（数据）。

来源

我在这里看到的一个测试只进行一次测试。但我注意到的是，您需要多次运行这些测试，最终它们的时间会收敛。基本上JVM需要预热。对于我的特定用例，我需要向列表中添加/删除项目，该列表将增加到大约500个项目。在我的测试中，LinkedList的发布速度更快，LinkedList约为50000 NS，ArrayList约为90000NS。。。给予或索取。请参见下面的代码。

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

这是一个效率问题。LinkedList添加和删除元素很快，但访问特定元素很慢。ArrayList访问特定元素的速度很快，但添加到两端的速度可能很慢，尤其是删除在中间的速度慢。

Array vs ArrayList vs LinkedList vs Vector更深入，同样如此链接列表。

您可以根据对该特定列表执行的操作的时间复杂性，使用一个而不是另一个。

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|