Arraylist of 2 dimensions

Question

I recently started working with ArrayList, but my question is how to create a matrix of ArrayList.

Answer 1

The ArrayList (or more exactly, the interface List, there is a programming principle that says you should code for an interface, not an implementation) is often used as a replacement for arrays. Use a List rather than an array has several advantages:

• Mixing arrays and generic types is somewhat problematic. Using List with generic types is much easier and convenient.
• Arrays have fixed size. List has a variable size. In particular, adding an element to the List, she grows up.
• List already comes with several useful methods to manipulate the data in various ways, no arrays.

However, for matrix cases, there is no good substitute for the List. To understand why and how to solve this situation, let’s think a little about what are matrices.

• A matrix is conceptually a grid of m × n elements, where m and n are the dimensions. Matrices can also have more than two dimensions.
• In Java (and most C descending languages), matrices are represented as arrays.
• Since Lists have variable size, when transporting this concept to matrices, it is not clear what occurs. When adding an element to a matrix of variable size, in which row or column would it be added? By the way, variable size matrices make some sense after all?

A possible approach would be to exchange a matrix X[][] by a list ArrayList<ArrayList<X>> (or better, List<List<X>>). However, this approach has a serious problem, which is not giving out by assigning elements directly in it such as could be done with an array based on arrays. For example:

String[][] a = new String[10][10];
a[0][0] = "abc"; // Funciona ok.

List<List<String>> b = new ArrayList<>();
b.get(0).set(0, "abc"); // NullPointerException!

The problem here is that the lists corresponding to matrix lines have not been properly instantiated.

Another problem with this approach is that you can’t guarantee that all rows in the matrix will have the same length. For example:

List<List<String>> c = new ArrayList<>();
c.add(new ArrayList<>());
c.add(new ArrayList<>());
c.get(0).add("a");
c.get(0).add("b");
c.get(0).add("c");
c.get(1).add("x");

In this example, the first line of the "matrix" had three elements while the second line had one. Matrices with distinct lines of size are an aberration and should not exist. However, this same aberration can also occur in the case of arrays:

String[][] d = {{"a", "b", "c"}, {"x"}};

This problem comes from the fact that we are representing arrays as arrays of arrays or as lists, where each list or internal array represents a row and there is no guarantee that all rows will be the same size.

On the other hand, there is a possible mathematical trick to represent elements arranged in several dimensions in a single dimension. We can represent a matrix of m × n elements with an array or list of m × n and determine that each block of n elements constitutes a line, with a total of m blocks in the array or list. However, this concept of matrix is a type of object, and therefore it is convenient to place it in a class. Moreover, this trick used to store the elements constitutes an internal rule of operation of our definition of our matrix, and if it is an internal rule, it must be encapsulated. So:

public class Matriz2<V> {
    private final int linhas;
    private final int colunas;
    private final List<V> elementos;

    public Matriz2(int linhas, int colunas) {
         this.linhas = linhas;
         this.colunas = colunas;
         elementos = new ArrayList<>(linhas * colunas);
    }

    public boolean posicaoValida(int linha, int coluna) {
        return linha >= 0 && linha < linhas && coluna >= 0 && coluna < colunas;
    }

    private int posicaoNaLista(int linha, int coluna) {
        if (!posicaoValida(linha, coluna)) throw new IllegalArgumentException();
        return linha * colunas + coluna;
    }

    private int linhaDaPosicao(int posicao) {
        return posicao / colunas;
    }

    private int colunaDaPosicao(int posicao) {
        return posicao % colunas;
    }

    public void set(int linha, int coluna, V elemento) {
        if (!posicaoValida(linha, coluna)) throw new IllegalArgumentException();
        elementos.set(posicaoNaLista(linha, coluna), elemento);
    }

    public V get(int linha, int coluna) {
        if (!posicaoValida(linha, coluna)) throw new IllegalArgumentException();
        return elementos.get(posicaoNaLista(linha, coluna));
    }
}

You can add the methods you prefer in this class. The complexity of converting from a set [linha, coluna] for a position in the list is given by the method posicaoNaLista. Since this is an internal rule of our matrix representation, this method is private. The methods linhaDaPosicao and colunaDaPosicao are used for reverse mapping.

You can also apply this same concept to three dimensions:

public class Matriz3<V> {
    private final int linhas;
    private final int colunas;
    private final int paginas;
    private final List<V> elementos;

    public Matriz3(int linhas, int colunas, paginas) {
         this.linhas = linhas;
         this.colunas = colunas;
         this.paginas = paginas;
         elementos = new ArrayList<>(linhas * colunas * paginas);
    }

    public boolean posicaoValida(int linha, int coluna, int pagina) {
        return linha >= 0 && linha < linhas && coluna >= 0 && coluna < colunas && pagina >= 0 && pagina < paginas;
    }

    private int posicaoNaLista(int linha, int coluna, int pagina) {
        if (!posicaoValida(linha, coluna, pagina)) throw new IllegalArgumentException();
        return pagina * linhas * colunas + linha * colunas + coluna;
    }

    private int paginaDaPosicao(int posicao) {
        return posicao / (linhas * colunas);
    }

    private int linhaDaPosicao(int posicao) {
        return (posicao % (linhas * colunas) / colunas;
    }

    private int colunaDaPosicao(int posicao) {
        return posicao % colunas;
    }

    public void set(int linha, int coluna, int pagina, V elemento) {
        if (!posicaoValida(linha, coluna, pagina)) throw new IllegalArgumentException();
        elementos.set(posicaoNaLista(linha, coluna, pagina), elemento);
    }

    public V get(int linha, int coluna, int pagina) {
        if (!posicaoValida(linha, coluna, pagina)) throw new IllegalArgumentException();
        return elementos.get(posicaoNaLista(linha, coluna, pagina));
    }
}