CODEWITHSUNDEEP
javaarrays
user2995645
user2995645

Reputation:

How to dynamically increase size of a 2D array

I already know how to make a fixed array, if I know how many elements I have. For instance, for 7 elements I do something like int array[2][4].

But what if I have 0 elements at start(which means the array will be empty at start) and want to increase the array size as the program runs?

Basicly, how to add a new row or column?

Upvotes: 0

Views: 19357

Answers (6)

Ashot Karakhanyan
Ashot Karakhanyan

Reputation: 2830

Of course you can use Collections(ArrayList for example), but if you want to use 2D Matrix, you can create rows with different size "on the fly". For example the following example create "triangle" matrix :

int[][] matrix = new int[3][];
int count = 0;
for (int i = 0; i < 3; i++) {
    matrix[i] = new int[i];
    for (int j = 0; j < i; j++) {
        matrix[i][j] = ++count;
    }
}

Upvotes: 0

user2975337
user2975337

Reputation:

Here's why resizing isn't possible. Whether you have 1 or 20 dimensions, every dimension of the array is allocated as a contiguous row of data somewhere, and the storage space immediately after any such sequence is fair game for other variables and data to use. For example, an ary = new int[4] might be represented in memory like so:

| ary[0] | ary[1] | ary[2] | ary[3] | otherNearbyData1 | otherData2 | ...

Because of the possibility of other variables immediately after the array data, you have to allocate a new array with the desired size and copy all the elements from the old array to the new one. One strategy is to double the allocation size every time you reach 100% capacity to obtain constant amortized time complexity. This is more or less what ArrayList does, but as Peter Lawrey noted this wastes a TON of space.

One alternative depending on your needs might be a LinkedList, in which every element of data is separately allocated and contains a pointer to the next/previous element. Despite being perfectly compact (no wasted space) and able to grow to any size, linked lists have two major disadvantages:

  • no random access (you can only traverse from one element to the next/previous one).
  • terribly inefficient time-wise -- leaping across the address space just to get to each next element totally knocks the wind out of CPU caches.

Edit: On second thought...even though 2D linked lists are possible, the fact that you need multiple dimensions probably means sequential traversal isn't enough for you. My bad.

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234797

Note that new int[2][4] is an array of int[]; the int[] arrays in the int[][] array are all initially the same length, but there's no requirement that they remain the same length. Any element of the int[][] array can be reassigned an int[] with a different length without affecting the other elements at all. The concept of "rows" and "columns" is a higher-level idea that is not supported by Java arrays.

Using an ArrayList as other answers suggest isn't going to change this. Furthermore, Depending on how you use ArrayList, you may end up with considerable overhead due to autoboxing of int values as Integer objects.

If you want to preserve the rectangular shape of your data, I suggest that you define a Matrix class that keeps all the dimensions consistent. (Or, perhaps better, linearizes the two-dimensional array into a one-dimensional array and does the appropriate subscripting calculations using internally stored row and column sizes. Or, perhaps best, use a well-written matrix library such as JAMA or a primitive collections library like Trove.)

EDIT Here's the start of a simple matrix class that uses a linear storage scheme internally and allows matrix resizing. The data are stored in row-major order and indexing is based at 0.

public class IntMatrix {
    private int rows;
    private int cols;
    private int[] data;

    /**
     * Allocate a matrix with the indicated initial dimensions.
     * @param cols The column (horizontal or x) dimension for the matrix
     * @param rows The row (vertical or y) dimension for the matrix
     */
    public IntMatrix(int cols, int rows) {
        this.rows = rows;
        this.cols = cols;
        data = new int[cols * rows];
    }

    /**
     * Calculates the index of the indicated row and column for
     * a matrix with the indicated width. This uses row-major ordering
     * of the matrix elements.
     * <p>
     * Note that this is a static method so that it can be used independent
     * of any particular data instance.
     * @param col The column index of the desired element
     * @param row The row index of the desired element
     * @param width The width of the matrix
     */
    private static int getIndex(int col, int row, int width) {
        return row * width + col;
    }

    public int get(int col, int row) {
        return data[getIndex(col, row, cols)];
    }

    public void set(int col, int row, int value) {
        data[getIndex(col, row, cols)] = value;
    }

    /**
     * Resizes the matrix. The values in the current matrix are placed
     * at the top-left corner of the new matrix. In each dimension, if
     * the new size is smaller than the current size, the data are
     * truncated; if the new size is larger, the remainder of the values
     * are set to 0.
     * @param cols The new column (horizontal) dimension for the matrix
     * @param rows The new row (vertical) dimension for the matrix
     */
    public void resize(int cols, int rows) {
        int [] newData = new int[cols * rows];
        int colsToCopy = Math.min(cols, this.cols);
        int rowsToCopy = Math.min(rows, this.rows);
        for (int i = 0; i < rowsToCopy; ++i) {
            int oldRowStart = getIndex(0, i, this.cols);
            int newRowStart = getIndex(0, i, cols);
            System.arraycopy(data, oldRowStart, newData, newRowStart,
                colsToCopy
            );
        }
        data = newData;
    }

    . . .
}

Upvotes: 1

Raffaele Rossi
Raffaele Rossi

Reputation: 1109

Java arrays can be dynamically created but cannot dynamically extended. You may want to look at Vector or ArrayList as other suggested.

However, bear in mind that in your example you've created a matrix which is a slightly different thing.

Upvotes: 0

Slate
Slate

Reputation: 3694

ArrayList documentation, and Examples. Enjoy!

Specifically:

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1); // Add 1 to the list.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533530

Create a new array which is bigger, copy the existing elements and add the element you want to add. You can use something like ArrayList but this is expensive and will use about 4x the memory. I would consider using TDoubleArrayList if you don't want to resize the array yourself.

Upvotes: 0

Related Questions