java - 隣接リストを使用してグラフを作成するために、リンクリストと配列を使用する場合のパフォーマンスの大きな違い

Question

私は巨大なグラフに関する課題に取り組んでおり、50 億行近くある .txt ファイルを読み取ってメイン グラフ (隣接リストとして) を作成する必要があります。実際、グラフは 870k の頂点で構成されています。いずれにせよ、最初の実装と 2 番目の実装の間に大きな時間差 (2 時間以上) があることに気付きました。これら 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()ただし、LinkedListの代わりにサイズNの配列を使用すると、このメソッドは2時間以上かかります。

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
   }