使用LinkedList或ArrayList进行迭代

Question

如果我要向列表中添加未知数量的元素，并且该列表只会被迭代，那么在特定实例中 LinkedList 是否会比 ArrayList 更好（使用 Java，如果有任何相关性的话）

Answer 1

之前

已经讨论过

ArrayList

和

LinkedList之间的性能权衡，但简而言之：对于大多数实际使用场景来说，ArrayList

往往更快。

ArrayList

 将导致更少的内存碎片，并且与垃圾收集器配合得更好，它将使用更少的内存并允许更快的迭代，并且在列表末尾发生的插入会更快。

因此，只要列表中的插入始终发生在最后一个位置，就没有理由选择

LinkedList

ArrayList

 是明显的赢家。

Answer 2

好的，已经回答了，但我仍然会尝试表达我的观点。

ArrayList

 的迭代速度比

LinkedList

 更快。原因是相同的，因为

arrayList

 有数组支持。让我们尝试了解为什么数组迭代比

linkedList

 更快。

有2个因素起作用

contiguous memory locations
```
 （你可以说
```
什么？）

但是你可以问 Cache 是如何适合这里的。请检查

here，CPU 尝试通过将数据存储在缓存中来利用缓存。它使用参考局部性。现在有两种技术

参考

参考地点

时间局部性如果某个特定的内存位置被引用，那么很可能同一位置将在不远的将来。相邻的数据之间存在时间上的接近性对同一内存位置的引用。在这种情况下，常见的是努力将引用数据的副本存储在特殊内存中存储，可以更快地访问。时间局部性是一个特殊的空间局部性的情况，即当预期位置是与当前位置相同。

空间局部性如果在特定时间引用特定存储位置，则附近的存储位置很可能会被引用近期会参考。在这种情况下，通常会尝试猜测当前参考周围区域的大小和形状准备更快的访问是值得的。

因此，如果一次访问一个数组位置，它也会加载缓存中的相邻内存位置。但请稍等，它不会加载全部。这取决于

CACHE_LINES。那么CACHE_LINES

定义一次可以在缓存中加载多少位。

因此，在进一步深入之前，让我们提醒一下我们所知道的事情

contiguous memory locations
CACHE-LINES
```
容量定义
```

SO 每当 CPU 尝试访问内存位置时，它都会检查该内存是否已在缓存中。如果它存在，则它匹配，否则它的

cache miss

。

因此，据我们所知，在数组的情况下，与

cache_miss

 中的

random memory locations

 相比，

linked list

 会更少。所以说得很有道理

最后从这里

维基百科的数组数据结构它说

在元素大小为 k 的数组中以及具有缓存行的机器上 B 字节大小，迭代 n 个元素的数组需要缓存未命中上限（nk/B）的最小值，因为它的元素占用连续的内存位置。这大约是 B/k 的更好倍数比随机访问 n 个元素所需的缓存未命中次数记忆位置。因此，对数组进行顺序迭代在实践中明显比对许多其他数据进行迭代要快结构，一种称为参考局部性的属性

我想这回答了你的问题。

Answer 3

对于迭代，两者都具有相同的 O(n) 迭代复杂度，顺便说一句，ArrayList 将占用更少的内存。

Answer 4

public List<Integer> generateArrayList(int n) {
    long start = System.nanoTime();
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        result.add(i);
    }
    System.out.println("generateArrayList time: " + (System.nanoTime() - start));
    return result;
}

public List<Integer> generateLinkedList(int n) {
    long start = System.nanoTime();
    List<Integer> result = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        result.add(i);
    }
    System.out.println("generateLinkedList time: " + (System.nanoTime() - start));
    return result;
}

public void iteratorAndRemove(List<Integer> list) {
    String type = list instanceof ArrayList ? "ArrayList" : "LinkedList";
    long start = System.nanoTime();
    Iterator<Integer> ite = list.iterator();
    while (ite.hasNext()) {
        int getDataToDo = ite.next();
        ite.remove();
    }
    System.out.println("iteratorAndRemove with " + type + " time: " + (System.nanoTime() - start));
}

@org.junit.Test
public void benchMark() {
    final int n = 500_000;
    List<Integer> arr = generateArrayList(n);
    List<Integer> linked = generateLinkedList(n);
    iteratorAndRemove(linked);
    iteratorAndRemove(arr);

}

Arraylist 用于获取随机位置值，linkedlist 用于插入、删除操作。上面的代码将比ArrayList更快地显示linkedlist，在删除函数中linkedlist比arraylist快1000倍，OMG!!!

generateArrayList time: 15997000
generateLinkedList time: 15912000
iteratorAndRemove with LinkedList time: 14188500
iteratorAndRemove with ArrayList time: 13558249400

使用LinkedList或ArrayList进行迭代

问题描述投票：0回答：4

4个回答

最新问题

使用LinkedList或ArrayList进行迭代

问题描述 投票：0回答：4

4个回答

最新问题

问题描述投票：0回答：4