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.

Answer 2

You say that the adjacency list could be "vast." If it is also sparse, you may be better off with some sort of sparse matrix representation. It might even be that, because of a vastly reduced memory footprint, it outperforms a 2d ArrayList.

Answer 3

I think it would be easier if you would also store the size of the graph in the first line of the file. That way the allocation and whole process would be much more efficient, without a bit loss in anything else.

In case you need to do allocations as you increase the matrix, you should start with a reasonable size for the domain in question, and thing increase it with a multiplier of 2, so that along the time, the ammount of allocations tends to stabilize and you do not have to reallocate and recopy the contents as many times.

Hopes that helps!