使用链表和数组构造具有邻接列表的图之间存在巨大的性能差异

Question

我正在做一个关于大型图的赋值，我必须通过读取一个几乎有50亿行的.txt文件来构建主图（作为邻接列表）。实际上，图由870k个顶点组成。不管怎样，我意识到第一次和第二次实现之间有巨大的时间差（超过2个小时）。我很好奇为什么这两种实现之间存在如此不可忽略的差异。在这里，您可以看到关于读取txt文件和构建图形的主要简单代码；

public class KosarajusSCC {
    private int t; // for finishing times in 1st pass
    private int s; // for leaders in 2nd pass
    private static final int N = 875714;
    private LinkedList<Vertex> mainList;
    public KosarajusSCC(){
        this.t = 0;
        this.s = 0;
        this.mainList = new LinkedList<>();
    }
    public void contructMainGraph() throws FileNotFoundException{
        Scanner reader = new Scanner(new File("src\Assignment4\SCC.txt"));
        for (int i = 1; i <= N; i++) {
            mainList.add(new Vertex(i));
        }
        StringTokenizer tokenizer;
        String str;
        int counter = 0;
        // construct the adjaceny list of vertices
        while(reader.hasNextLine()){
            str = reader.nextLine();
            tokenizer = new StringTokenizer(str);
            int tailVertex = Integer.parseInt(tokenizer.nextToken());
            int headVertex = Integer.parseInt(tokenizer.nextToken());
            mainList.get(tailVertex-1).getAdjacencyList().add( mainList.get(headVertex-1));
        }
        reader.close();
    }

}

因此，这个contructMainGraph()方法需要2个多小时，但是，如果我使用一个大小为N的数组，而不是LinkedList，比如；

Vertex[] mainArray = new Vertex[N];
for (int i = 0; i < mainArray.length; i++) {
    mainArray[i] = new Vertex(i+1);
}

如果我用更改while循环的最后一个语句；

mainArray[tailVertex-1].getAdjacencyList().add(mainArray[headVertex-1]);

然后一切都在不到10秒内完成。那么那里发生了什么呢？。如果你能帮忙，我将不胜感激，无论如何都要感谢

编辑：我忘记分享顶点类：）

public class Vertex {
    private int finishTime;
    private int leader;
    private boolean marked;
    private int vertexID;
    private LinkedList<Vertex> adjacencyList;
    public Vertex(int vertexID){
        this.vertexID = vertexID;
        this.marked = false;
        this.finishTime = 0;
        this.leader = 0;
        this.adjacencyList = new LinkedList<>();
    }
    // getters and setters here
   }

Answer 1

因为你正在对它进行索引。这是链表上的O（n）运算，但数组上的O是1。

Answer 2

我认为这归结为时间复杂性。

数组的读取时间复杂度为O（1）。但是当你使用双链接列表时，它的时间复杂度是O（n）。

我会推荐我一直以来最喜欢的ArrayList。