java - 为什么我们要在声明 List> 图中的索引 i 处初始化列表

Question

考虑这样一种情况，我们可以借助 List<List<Integer>> 来定义图形。其中索引 0 处的列表将是顶点 0 的邻接列表，依此类推，对于 1、2、3 及更多。

现在，如果我声明这样的邻接列表，

// initialize adjacency list
        List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);

既然如此，为什么我需要按如下方式初始化每个列表，

        // initialize vertices
        for (int i = 0; i < n; i++)
            adjList.add(i, new ArrayList<Integer>());

此循环仅在每个索引 i 处添加一个新列表，其中 n = 图中的顶点数。

初始声明是否意味着主列表将在索引 0 处有一个列表，然后在索引 1 处又有另一个列表，依此类推？

我的意思是，如果我在列表数组的帮助下声明一个图形，如下所示，我可以理解这个循环的用法，

ArrayList[] graph = new ArrayList[n];

那么在这种情况下，是的，我肯定需要一个循环来初始化每个顶点的邻接列表，但为什么我们也需要在这种初始情况下进行初始化？

如果我按如下方式声明数组会怎样？这对循环有什么影响吗？

1. List<List<Integer>> adjList = new ArrayList<>(n);
2. List<List<Integer>> adjList = new ArrayList<List<List<Integer>>(n);

请帮助我，我在理解这一点时犯的概念错误是什么？

Answer 1

当你有:

List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);

您仅实例化了一个初始容量为n的ArrayList，但列表为空(即adjList.size () == 0)。 ArrayList 的容量是其内部数组的大小。当您向 ArrayList 添加元素时，如果数组不够大，无法容纳另一个元素，则必须创建一个更大的新数组，并且必须复制旧数组的内容。这可能会很昂贵；如果您知道所需的容量，您可以指定初始容量，以避免必须“调整”内部数组的大小。

如果List必须有一定数量的元素才能开始，您必须首先添加它们，这就是循环的作用:

for (int i = 0; i < n; i++)
    adjList.add(i, new ArrayList<Integer>());

这是 List#add(int,E) 的文档:

Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

由于您从一个空的 List 开始并从 0 迭代到 n，因此您只需将一个元素添加到 的末尾>列出每次迭代。这相当于调用 List#add(E)每次迭代。循环完成后，您将得到一个大小等于n的非空List。

<小时/>

What if I declare the array as follows? Would that make any difference with the loop?

1. List<List<Integer>> adjList = new ArrayList<>(n);
2. List<List<Integer>> adjList = new ArrayList<List<List<Integer>>(n);

1. 这只是使用 diamond operator 。使用泛型类型时，菱形运算符会删除样板文件。
2. 这不会编译；左侧是列表的列表，但右侧是列表的列表。