Почему мы хотим инициализировать список по индексу i в объявлении Listграфик

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);

Вы только что создали экземпляр ArrayList с начальной емкостью из n, но список пуст (т. Е. adjList.size() == 0),Емкость ArrayList - это размер внутреннего массива. Когда вы добавляете элементы в ArrayList, если массив недостаточно велик для размещения другого элемента, необходимо создать новый массив большего размера и скопировать содержимое старого массива. Это может быть дорого;если вы знаете необходимую емкость, вы можете указать начальную емкость, чтобы попытаться избежать «изменения размера» внутреннего массива.

Если List должен иметь определенное количество элементов, для начала вам нужно добавитьсначала их, что и делает цикл:

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

Вот документация List#add(int,E):

Вставляет указанный элемент в указанную позициюв этом списке (необязательная операция). Смещает элемент, находящийся в данный момент в этой позиции (если есть), и любые последующие элементы вправо (добавляет один к их индексам).

Поскольку вы начинаете с пустого List и выполняете итерацию с 0к n вы просто добавляете элемент в конец List каждой итерации. Это будет эквивалентно вызову List#add(E) каждую итерацию. После завершения цикла у вас будет непустой List с размером, равным n.

---

Что если я объявлю массив следующим образом? Будет ли это иметь значение для цикла?

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

1. Это просто использование оператора diamond . Оператор diamond удаляет шаблон при использовании универсальных типов.
2. Это не скомпилируется;левая сторона - список списков, а правая - список списков.