使用 LinkedList 或 ArrayList 进行迭代

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

之前已经讨论过ArrayList和LinkedList之间的性能权衡，但简而言之：对于大多数现实生活中的使用场景，ArrayList往往更快。 ArrayList将导致更少的内存碎片，并且与垃圾回收器一起使用会更好，它将占用更少的内存并允许更快的迭代，并且对于列表末尾发生的插入会更快。

因此，只要列表中的插入总是出现在最后一个位置，就没有理由选择LinkedList - ArrayList是明显的赢家。

好的，

它已经回答了，但我仍然会尝试提出我的观点。 ArrayList迭代速度比LinkedList快。原因是一样的，因为arrayList是由数组支持的。让我们尝试了解 whay 数组迭代比 linkedList 更快。

有两个因素对它有用

数组存储为 contiguous memory locations (你可以说
什么？
系统缓存比访问内存快得多

但是您可以问缓存如何适合这里。好吧，检查一下这里，CPU试图通过将数据存储在缓存中来利用缓存。它使用引用位置。现在有 2 种技术是

参考文献参考位置

时间位置 如果在某一时刻引用了特定的内存位置，则很可能在近期。相邻之间存在时间上的接近性对同一内存位置的引用。在这种情况下，通常努力将引用数据的副本存储在特殊内存中存储，可以更快地访问。时间位置是一个特殊的空间位置的情况，即当预期位置与现在的位置相同。
空间位置 如果在特定时间引用了特定的存储位置，则附近的内存位置很可能是在不久的将来引用。在这种情况下，通常会尝试猜测当前参考周围区域的大小和形状值得准备更快的访问。

因此，如果一次访问一个阵列位置，它也会在缓存中加载相邻的内存位置。但是等待它不会全部加载。这取决于CACHE_LINES。好吧CACHE_LINES定义一次可以在缓存中加载多少位。

所以在进一步潜水之前，以免提醒我们所知道的

数组contiguous memory locations
当相邻访问数组的一个内存位置时，也会加载到内存中
中加载的阵列内存位置量由CACHE-LINES容量定义

因此，每当 CPU 尝试访问内存位置时，它都会检查该内存是否已在缓存中。如果它存在，它与它cache miss匹配。

因此，据我们所知，在数组的情况下，与linked list中的random memory locations相比，cache_miss会更少。所以这是有道理的

最后从这里Array_data_structure来自维基百科，它说

在元素大小为 k 的数组中和具有缓存行的计算机上 B 字节的大小，遍历 n 个元素的数组需要最小上限 (NK/B( 缓存未命中，因为它的元素占用连续的内存位置。这大约是 B/k 更好的一个因素比随机访问 n 个元素所需的缓存未命中数内存位置。因此，对数组进行顺序迭代在实践中明显比对许多其他数据的迭代快结构，称为引用位置的属性

我想这回答了你的问题。

对于迭代，两者在迭代时将具有相同的 O(n( 复杂性，ArrayList 将占用更少的内存 BTW。

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);
}

数组列表用于获取随机位置值，链接列表可用于插入，删除操作。上面的代码将显示linkedlist比ArrayList快得多，在删除函数linkedlist中比arraylist快1000倍，天哪!!

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

相关内容

最新更新

热门标签：