java - 数组列表与列表链表

Question

因此，我的任务是比较 LinkedLists 和 ArrayLists 的两个不同事物。

第 1 部分)随机选择列表内的位置，并为每种列表类型将这些值增加 1

第 2 部分)通过添加随机位置将每个列表大小加倍，然后立即删除相同数量的随机位置，将列表缩小到原始大小。

我觉得我已经很好地完成了这一点，但我的老师说第 1 部分 ArrayList 应该更快(它在我的代码中)。他说 LinkedList 在第 2 部分中应该更快，这对我来说完全相反......它的速度更慢......我在不同位置添加了 SYSO's验证列表是否已正确修改以及所有内容，但无法弄清楚为什么它没有按照他所说的方式工作。

任何人都可以发现我做错了什么(如果有的话？)。非常感谢

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import javax.swing.JOptionPane;

public class LinkedListVersusArrayList {

public static void main(String[] args) {

    long startTime, endTime, duration;
    List<Double> LL = new LinkedList<Double>();
    ArrayList<Double> AL = new ArrayList<Double>();
    int size = Integer.parseInt(JOptionPane.showInputDialog("Pick a list size (whole number only please)"));

    //fills the Linked List with random doubles
    for (int i = 0; i < size; i++){
        LL.add(Math.random());
    }
    //fills the ArrayList with random doubles
    for (int i = 0; i < size; i++){
        AL.add(Math.random());
    }

    //
    //Part 1
    //
    System.out.println("\nPART 1:\nBoth lists are now full of random numbers. \nI will now cycle through "
            + "and incremiment random locations " +size+ " times for each list.\n");

    //testing the LinkedList first for random access
    startTime = System.nanoTime();
    for (int i = 0; i < size; i++){
        int x = (int)(LL.size()*Math.random());
        double y = LL.get(x);
        LL.set(x, y+1);
    }
    endTime = System.nanoTime();
    duration = (endTime - startTime);
    System.out.println("Linked List took: " +(duration/1000000) +" milli seconds");

    //testing the ArrayList now for random access
    startTime = System.nanoTime();
    for (int i = 0; i < size; i++){
        int x = (int)(AL.size()*Math.random());
        double y = AL.get(x);
        AL.set(x, y+1);
    }
    endTime = System.nanoTime();
    duration = (endTime - startTime);
    System.out.println("Array List took: " +(duration/1000000) +" milli seconds");

    //
    //Part 2
    //
    System.out.println("\nPART 2:\nBoth lists will now get "+size+" slots added to them in random locations.\n"
            + "After this is complete, we will remove "+size+" slots from each list at random\n");

    //testing the LinkedList first for random adding/subtracting
    startTime = System.nanoTime();
    //add
    for (int i = 0; i < size; i++){
        int x = (int)(LL.size()*Math.random());
        LL.add(x, 1.0);
    }
    //delete
    for (int i = 0; i < size; i++){
        int x = (int)(LL.size()*Math.random());
        LL.remove(x);
    }
    endTime = System.nanoTime();
    duration = (endTime - startTime);
    System.out.println("Linked List took: " +(duration/1000000) +" milli seconds");

    //testing the ArrayList now for random adding/subtracting
    startTime = System.nanoTime();
    //add
    for (int i = 0; i < size; i++){
        int x = (int)(AL.size()*Math.random());
        AL.add(x, 1.0);
    }
    //delete
    for (int i = 0; i < size; i++){
        int x = (int)(AL.size()*Math.random());
        AL.remove(x);
    }
    endTime = System.nanoTime();
    duration = (endTime - startTime);
    System.out.println("Array List took: " +(duration/1000000) +" milli seconds");
}

}

Answer 1

除了您的代码无法控制的所有微基准测试问题之外，您的老师对案例 2 的期望也是错误的。他忽略了访问 LinkedList 的随机元素的成本(在该位置插入的先决条件)，并高估了插入 ArrayList 的成本。复制连续内存块的成本远低于追踪长指针链的成本，而这是访问 LinkedList 的随机元素所需的成本。

实际上，LinkedList 的应用范围非常狭窄，它比 ArrayList 没有任何改进。例如，您可以尝试仅在列表前面附近插入。这样，您将强调在 ArrayList 中移动元素的成本，而不强调访问 LinkedList 成员的成本。