java如何证明arraylist和linkedlist性能之间的差异

Question

我在读LinkedList和ArrayList。我发现很多人说通过ArrayList的迭代比LinkedList快，但同时从LinkedList添加和删除元素比ArrayList快

如何证明这一点

我用Java编写了一个实验，并在调试模式下运行，但我没有看到ArrayList和LinkedList之间有任何区别

你对这个问题的态度是什么？如何证明人们所说的是真的

这是我的代码：

import java.util.ArrayList;
import java.util.LinkedList;

public class List {

    public static void main(String[] args) {

        ArrayList<Integer> arraylist = new ArrayList<Integer>();
        arraylist.add(1);
        arraylist.add(2);
        arraylist.add(3);
        arraylist.add(4);
        arraylist.add(5);

        arraylist.remove(1);
        arraylist.remove(2);

        for(int x: arraylist) {

        System.out.println(x);

        }

        LinkedList<Integer> arraylista = new LinkedList<Integer>();
        arraylista.add(1);
        arraylista.add(2);
        arraylista.add(3);
        arraylista.add(4);
        arraylista.add(5);

        arraylista.remove(1);
        arraylista.remove(2);

        for(int x: arraylista) {

            System.out.println(x);

            }

    }
}

Answer 1

在阅读此答案之前，请注意一点：这些只是潜在的实现，而不是实际的实现，但是背后的原则应该仍然适用

a^ {}使用数组作为其内部结构，考虑此数组：

int[] array = new int[1];

这个数组将包含一个元素。让我们假设我们可以使用ArrayList中定义的方法来添加它，它看起来是这样的：

array.add(0);

当我们必须向这个数组中添加另一个元素时会发生什么？它显然只包含一个项目。嗯，它必须调整大小，一种常见的调整大小的方法是将其容量加倍。让我们这样做：

int[] temp = new int[2];
for(int i = 0; i < array.length; i++) {
    temp[i] = array[i];
}
array = temp;

如果我们再添加两个元素，会发生什么？我们还需要创建另一个临时数组，复制这些值，然后再次插入它们。这是添加到LinkedList更快的原因之一。一个LinkedList不是在底层数组的帮助下构建的

一个LinkedList由所有节点组成，这些节点都包含对上一个和下一个节点的引用，或者只包含对下一个节点的引用，因此，如果保存对LinkedList的最后一个元素的引用，那么插入到它的末尾是非常便宜的

根据您对Java的学习程度，我强烈建议您从头开始实现这些数据结构，了解它们的工作原理非常有帮助

@Makoto和@CommuSoft提到了我没有提到的差异中非常重要的方面，所以也请阅读这些内容