How to make a dynamic 2D array

[Lucas Chang]

I've been trying to make a dynamic 2D array for the adjacency matrix
implementation. One way would be to recopy the row array and every
column array into new arrays of twice the size whenever they run out
of room, but I thought it would be easier to use the Java collections
data structures. I tried using ArrayLists of ArrayLists, but it seems
like ArrayLists don't tolerate null values in between their values.
For example, if I have an ArrayList representing all the edges going
out of the first vertex, and I want to add an edge to the 5th vertex,
it causes an OutOfBoundsException because a List expects the first
value to go in index 0. The only thing i can think of is to fill all
the non-edges with placeholder values so they are not treated as empty
spots, but that doesn't seem like a good solution

[Keith Newman]

This is how I did it:

- Start off with a single ArrayList of size 0 that contains nothing.
- When you add a Vertex, add a new ArrayList to the outer ArrayList
and increment a static counter (one that will, from here on it, keep
track of the number of vertices)
- Fill in the inner ArrayList(s) from 0 to the counter with null
values
- Rinse and repeat (adding a null value to each of the previous
ArrayLists every time you add a new ArrayList to the outer ArrayList)

As for your other problem, I'm not entirely sure what you mean, but
ArrayLists have the method set(index, element) where you can put a
value into any index of the ArrayList that you wish.

[Teddy Ni]

Keep in mind also that the adjacency matrix does have a placeholder
value for edges that don't exist. That's how you get constant time
look up for edges. It's at the expense of extra space to store those
placeholders.

Teddy

[Lucas Chang]

Thanks. Keith, are you sure you want your counter to be static? A
client might create mutliple AdjMatrixGraphs with different numbers of
vertices. I think each graph should maintain its own counter.

[Steve Spagnola]

Yes, it would be a better design choice to not have the variable be
static in case that the client code wants to test with multiple
graphs.

[Keith Newman]

Yeah, I realized that. Thanks!