ArrayList index out of bound but HashSet has no issue

Question

I have a simple Graph class, which tracks which elements are linked to eachother using an array of Lists.

I am getting IndexOutOfBoundsException when removing an element from the list. My error is given below the code.

But if I change the collection from ArrayList<Integer> to HashSet<Integer>, it works fine.

Why does Arraylist<Integer> type not work here but HastSet<Integer> works?

And what is the internal mechanism of removing elements of these collections?

class Graph {
    int v;

    ArrayList<Integer>[] connections;

    Graph(int v) {
        this.v = v;
        connections = new ArrayList[v];
        for (int i = 0; i < v; i++) {
            connections[i] = new ArrayList<>();
        }
    }

    void addConnection(int u, int v) {
        connections[u].add(v);
        connections[v].add(u);
    }

    void removeConnection(int u, int v) {
        connections[u].remove(v);
        connections[v].remove(u);
    }
}

class Main{
  
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> result = new ArrayList<>();
        Graph graph = new Graph(n);
     
        for (List<Integer> connection : connections) {
            graph.addConnection(connection.get(0), 
            connection.get(1));

    for (List<Integer> connection : connections) {
         graph.removeConnection(connection.get(0), 
         connection.get(1));
         graph.addConnection(connection.get(0), 
         connection.get(1));
    }
}

---

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
    at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
    at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
    at java.base/java.util.Objects.checkIndex(Objects.java:372)

Answer 1

Your problem is the method signature:

void removeConnection(int u, int v) { // <-- These should be Integer, not int
    connections[u].remove(v);
    connections[v].remove(u);
}

The reason is List has two remove methods:

1. remove(int index) that removes the element at index index
2. remove(Object object) that finds and removes object

and you are calling version 1, but you want version 2.

Set however does not have the remove(int index) method, so java auto-boxes the int to an Integer and the method works as intended (as you discovered).

By changing the method signature to

void removeConnection(Integer u, Integer v)

the correct version of remove() is called. If an int is passed to the method, it will be auto-boxed to an Integer, so your usage of this method does not need to change.

---

This is situation is a corner case; it only occurs when the collection type is Integer and when autoboxing is being attempted. However, it comes up often enough that this special case is worth keeping in the back of your mind, due to the puzzlement and it's hard to pick up even if carefully debugging.