Why would we want to initialize a list at an index i in a declaration List> graph

Question

Consider a case where we can define a graph with the help of a List<List<Integer>> where list at index 0 will be the adjacency list of vertex 0 and so on for 1,2,3 and further.

Now if I declare such adjacency list as follows,

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

In this case, why do I need to initialize each list as follows,

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

This loop is only adding a new list at each index i, where n = number of vertices in a graph.

Doesn't the initial declaration mean that the main list will have a list at index 0 and then again another list at index 1 and so on?

I mean, I can understand the use of this loop, if I am declaring a graph with the help of an array of lists as follows,

ArrayList[] graph = new ArrayList[n];

then in this case, yes, I will definitely need a loop to initialize each vertex's adjacency list but why do we need to initialize in this initial case as well?

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

Please help me, what is the conceptual error that I am making to understand this?

It is not necessary to do `adjList.add(i, new ArrayList());` – you could instead do this inside your loop: `adjList.add(new ArrayList<>());`. — kaan, Oct 08 '19 at 18:53
I would listen to what Kaan said. add the arrayList inside your loop — RevCarl, Oct 08 '19 at 19:12
thanks for the reply, but my question is why would we even want that loop in the first place. — Nachiket Joshi, Oct 08 '19 at 20:11

Slaw · Accepted Answer · 2019-10-08T19:06:39.113

When you have:

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

You've only instantiated an ArrayList with an initial capacity of n but the list is empty (i.e. adjList.size() == 0). The capacity of an ArrayList is how large its internal array is. As you add elements to an ArrayList, if the array is not large enough to hold another element then a new, larger array must be created and the old array's contents must be copied over. This can be expensive; if you know the needed capacity you can specify an initial capacity to try and avoid having to "resize" the internal array.

If the List must have a certain number of elements to start with you have to add them first, which is what the loop does:

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

Here's the documentation of 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).

Since you start with an empty List and iterate from 0 to n you are simply adding an element to the end of the List each iteration. This would be equivalent to calling List#add(E) every iteration. After the loop completes you will have a non-empty List with a size equal to n.

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

This is simply using the diamond operator. The diamond operator removes boilerplate when using generic types.
This wouldn't compile; the left side is a list-of-lists but the right side is a list-of-list-of-lists.

thank you so much for this answer, this clears a lot of my doubts. Thank you sooooo much for taking the efforts and explaining. — Nachiket Joshi, Oct 08 '19 at 20:07

Why would we want to initialize a list at an index i in a declaration List> graph

1 Answers1