2-Dimensional ArrayList

-1

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

    
asked by anonymous 09.05.2017 / 17:10

1 answer

1
The ArrayList (or rather, the List interface, there is a programming principle that says you should code for an interface, not an implementation) is often used as a substitute for the arrays. Using List instead of 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 variable length. In particular, when you add an element in List , it grows.
  • List already comes with several useful methods for manipulating data in many ways, not arrays.

However, for arrays, there is no good substitute for List . To understand why and how to solve this situation, let's think a little bit about what are arrays.

  • An array is conceptually a grid of m × n elements, where m and n are the dimensions. Arrays can also have more than two dimensions.
  • In Java (and in most of the descendant languages of C), arrays are represented as array arrays.
  • Since List s has variable size, when carrying this concept to matrices, it is not clear what happens. When adding an element into a variable-sized array, in what row or column would it be appended? In fact, do variable size matrices make any sense at all?

One possible approach would be to exchange a X[][] array with a ArrayList<ArrayList<X>> (or rather, List<List<X>> ) list. However, this approach has a serious problem, which is to not give out by assigning elements directly in it as could be done with an array based array. 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 the array rows were not properly instantiated.

Another problem with this approach is that you can not guarantee that all rows in the array 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 "array" has three elements while the second line has one. Matrices with distinct size lines 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 arises from the fact that we are representing arrays of arrays or lists of 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 mathematical trick possible to represent elements arranged in several dimensions in a single dimension. We can represent an array of m × n elements with an array or list of m × n elements and determine that each block of n elements constitutes a row, with a total of m blocks in the array or list. However, this concept of matrix is a type of object, so it is convenient to place it in a class. In addition, this trick used to store the elements is an internal rule of operation of our definition of our matrix, and if it is an internal rule, it must be encapsulated. Therefore:

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 any methods you prefer in this class. The complexity of converting from [linha, coluna] to a position in the list is given by the posicaoNaLista method. Since this is an internal rule of our array representation, this method is private. The linhaDaPosicao and colunaDaPosicao methods are used to reverse map.

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));
    }
}
    
09.05.2017 / 18:24