What is the most efficient way to store an adjacency matrix without knowing its size?

Question

I need to store a non directed graph with multiple nodes (unknown to the size.. can be vast) on an adjacency matrix. Would a 2D arrayList be an efficient way to store this? If not, what is a better way to store this data? Any comment is appreciated.

Answer 1

I would definitely go for a 2d ArrayList. You can add rows/columns in O(n) time (n is the number of rows), if inserting at the end (which make sense). Access to the list is O(1), and removing an arbitrary row will be O(n²).

The other option is to use a doubly linked list. In this case, insertion to the ends will be O(n) time, access is O(n), and removing a row is O(n²).

So it seems that for a matrix, the ArrayList is best, but only because of more efficient access.