Coleções Java

O Java possui APIs úteis para o desenvolvimento e uma delas é a API Collections. A API de coleções do java é algo que você usará todo o dia, mesmo que não perceba.

Agrupar valores relacionados é algo comum no desenvolvimento, como notas de alunos, eventos que ocorreram em um certo dia ou uma lista de tarefas para serem feitas.

Esse agrupamento pode ser feitos de várias formas e o java collections fornece a API necessária para isso no java.

Array

A forma mais simples de agrupar valores é usando um Array. O array é uma estrutura de dados homogenia, ou seja, todos os valores possuem o mesmo tipo.

O Array deve ter tamanho fixo que pode ser declarado definindo os valores na inicialização ou definindo um tamanho usando new.

public class Main {
    public static void main(String[] args) {
        int[] notas = { 10, 8, 9, 7 };

        String[] tarefas = {
                "Dar like no post",
                "Comentar algo",
                "Compartilhar o post"
        };

        String[] diasDaSemana = new String[7];
        diasDaSemana[0] = "Domingo";
        diasDaSemana[1] = "Segunda-feira";
        diasDaSemana[2] = "Terça-feira";
        diasDaSemana[3] = "Quarta-feira";
        diasDaSemana[4] = "Quinta-feira";
        diasDaSemana[5] = "Sexta-feira";
        diasDaSemana[6] = "Sábado";
    }
}

O array é alocado de forma contígua na memória. Isso significa que os espaços para cada dado no array é seguido um após o outro. O array notas estaria mais ou menos assim na memória.

A desvantagem é que caso não houver um o espaço contíguo na memória o array não conseguiria ser criado.

A vantagem disso é permitir um acesso instantâneo O(1) a qualquer valor do array. O programa faz uma conta simples para o acesso aos valores:

endereço = endereço_da_variavel_array + tamanho_do_tipo_de_dado * indice_do_array

Por exemplo, vamos pegar o array notas, o tamanho de um int no java é 4 bytes, o índice de um array inicia em 0 e vamos imaginar que notas está no endereço 0x100 (256 em hexadecimal). Então a conta para acessar seria:

// acessando o índice 0 (primeiro índice)
x = 0x100 + 0x4 * 0x0
x = 0x100 + 0x0
x = 0x100 // 200 em hexadecimal que é o endereço onde está o primeiro valor

E se quisermos o último valor? O último índice é 3 já que os índices vão de 0 até o tamanho do array - 1.

// acessando o índice 3 (último índice)
x = 0x100 + 0x4 * 0x3
x = 0x100 + 0xC
x = 0x10C // 268 em hexadecimal que é o endereço onde está o último valor

Por isso o array é uma ótima estrutura para acessar valores.

Coleções

O array é a forma mais simples de agrupar valores. O java possui uma API completa para isso chamada Java Collections.

Essa API possui várias classes e interfaces para diferentes tipos de agrupamentos de valores e métodos para manipulação desses agrupamentos.

Abaixo temos a hierarquia das interfaces dessa API.

List

List é uma interface que defini operações para uma coleção de lista de valores, com ordem e índices. Temos duas principais implementações dessa interface, ArrayList e LinkedList.

ArrayList

O ArrayList uma implementação da interface List. Essa classe armazena os dados em um formato de array. O ArrayList pode aumentar ou diminuir o seu tamanho, diferente do array convencional que tem tamanho fixo.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> linguagens = new ArrayList<>();

        linguagens.add("Java");
        linguagens.add("Python");
        linguagens.add("C++");

        linguagens.remove(1); // Remove "Python"

        linguagens.forEach(System.out::println); // imprimi os elementos
    }
}

O ArrayList resolve o problema de tamanho fixo de um array. Internamente ele cria um array com um tamanho inicial de 10 por padrão.

A medida que você adiciona elementos com o método add() o ArrayList cria um novo array internamente e copia os dados para esse novo array.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // internamente é um array de tamanho 10: Integer[] notas = new Integer[10];
        List<Integer> notas = new ArrayList<>();

        notas.add(10);
        notas.add(8);
        notas.add(9);
        notas.add(7);

        Integer nota = 6;
        notas.add(nota);

        // remoção por referência ao objeto
        notas.remove(nota); // Remove o objeto nota da lista
        System.out.println(notas); // [10, 8, 9, 7]

        // adiciona mais elementos no ArrayList
        // Internamente o ArrayList cria um novo array com mais capacidade e copia os elementos para ele
        for (int i = 0; i < 10; i++) {
            notas.add(i);
        }

        System.out.println(notas); 
        // [10, 8, 9, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

LinkedList

O ArrayList resolve o problema de ter um array de tamanho fixo, mas ainda temos o problema de precisar ter espaço contíguo na memória para array, mesmo usando um ArrayList.

Para esse tipo de problema temos uma outra implementação da interface List chamada LinkedList. Essa classe é uma lista encadeada, onde cada valor é um nó da lista que aponta para o nó anterior e posterior. Se usarmos um LinkedList para armazenar aquele array de notas ficaria algo parecido com isso:

A desvantagem desse tipo de implementação é que o acesso a um valor é linear O(n). Ou seja, se eu quiser o terceiro valor na lista, eu preciso acessar o primeiro e o segundo elemento até chegar no terceiro.

A vantagem desse tipo de implementação é que adicionar e remove valores é menos custoso já que é apenas necessário mudar o valor dos campos próximo e anterior dos nós o que é uma complexidade linear O(1).

Como LinkedList implementa a interface List podemos continuar com o código anterior e mudar apenas a classe ArrayList para LinkedList.

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> notas = new LinkedList<>(); // Alterando a implementação para LinkedList

        notas.add(10);
        notas.add(8);
        notas.add(9);
        notas.add(7);

        Integer nota = 6;
        notas.add(nota);

        // remoção por referência ao objeto
        notas.remove(nota); // Remove o objeto nota da lista
        System.out.println(notas); // [10, 8, 9, 7]

        for (int i = 0; i < 10; i++) {
            notas.add(i);
        }

        System.out.println(notas);
        // [10, 8, 9, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

Set

O Set é outra interface que pertence ao java collections e representa uma estrutura de conjunto. Os conjuntos guardam elementos sem um índice ou ordem, como fazia com List, e não permite elementos duplicados.

Algumas implementações da interface Set são HashSet, TreeSet e LinkedHashSet.

HashSet

O HashSet implementa a interface Set usando um tabela hash através da classe HashMap. Assim, quando você adiciona um valor ao HashSet ele cria um registro no HashMap interno com a chave sendo o valor que você adicionou e um Object para preencher o valor do HashMap

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> linguagens = new HashSet<>();

        String java = "Java";
        String javascript = "JavaScript";

        // internamente: HashMap: { "Java": Object }
        linguagens.add(java);

        // adicionar o mesmo valor faz apenas recriar a chave no HashMap
        linguagens.add(java);

        // internamente: HashMap: { "Java": Object, "JavaScript": Object }
        linguagens.add(javascript);

        /*
         * internamente:
         * HashMap: {
         * "Java": Object,
         * "C": Object,
         * "Typescript": Object,
         * "JavaScript": Object
         * }
         */
        linguagens.add("Typescript");
        linguagens.add("C");

        System.out.println(linguagens); // [Java, C, Typescript, JavaScript]

        linguagens.remove(javascript); // Remove "JavaScript" do conjunto

        System.out.println(linguagens); // [Java, C, Typescript]
    }
}

Esse tipo de implementação permite um acesso constante O(1) já que acessar um valor na tabela hash é acesso constante.

Note que mesmo adicionando a string "C" por último, ela foi impressa como sendo a segunda. Isso, porque o Set não garante uma ordem dos elementos.

LinkedSet

Essa implementação do Set utiliza uma lista duplamente encadeada para manter a ordem dos elementos e um HashMap para implementar os métodos da interface Set.

import java.util.LinkedHashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> linguagens = new LinkedHashSet<>(); // Trocando para LinkedHashSet

        String java = "Java";
        String javascript = "JavaScript";

        /*
         * internamente:
         * HashMap: { "Java": Object }
         * LinkedList: head <-> "Java" <-> tail
         */
        linguagens.add(java);

        // adicionar o mesmo valor faz apenas recriar a chave no HashMap
        linguagens.add(java);

        /*
         * internamente:
         * HashMap: { "Java": Object, "JavaScript": Object }
         * LinkedList: head <-> "Java" <-> "JavaScript" <-> tail
         */
        linguagens.add(javascript);

        /*
         * internamente:
         * HashMap: {
         * "Java": Object,
         * "JavaScript": Object,
         * "Typescript": Object,
         * "C": Object
         * }
         * LinkedList: head <-> "Java" <-> "JavaScript" <-> "Typescript" <-> "C" <-> tail
         */
        linguagens.add("Typescript");
        linguagens.add("C");

        System.out.println(linguagens); // [Java, JavaScript, Typescript, C]

        linguagens.remove(javascript); // Remove "JavaScript" do conjunto

        System.out.println(linguagens); // [Java, Typescript, C]
    }
}

TreeSet

O TreeSet é um implementação da interface NavigableSet que extende o SortedSet que é um interface que extende o Set. O SortedSet são conjuntos ordenados. Internamente o TreeSet usa uma Árvore Rubro-Negra que é uma árvore binária de busca auto balanceada, um tipo de estrutura de dados, para guarda os valores ordenados.

O TreeSet ordena os valores que podem ser comparados, ou seja, que implementam a interface Comparable. Caso o valor não implemente a interface Comparable, pode ser passado um Comparator no construtor do TreeSet para que a classe saiba como ordenar os valores.

A impressão dos valores utiliza o algoritmo de percurso "em ordem" das árvores binárias.

import java.util.Set;
import java.util.TreeSet;

public class Main {
    static record Product(String name, double price) {
    }

    static class ProductCompable implements Comparable<ProductCompable> {
        String name;
        double price;

        public ProductCompable(String name, double price) {
            this.name = name;
            this.price = price;
        }

        @Override
        public int compareTo(ProductCompable other) {
            return Double.compare(this.price, other.price);
        }
    }

    public static void main(String[] args) {
        // Passando um Comparable
        Set<ProductCompable> productSetComparable = new TreeSet<>();

        // Passando um Comparator através de uma expressão lambda para ordenar
        Set<Product> productSet = new TreeSet<>((p1, p2) -> Double.compare(p1.price, p2.price));

        productSet.add(new Product("Laptop", 999.99));
        productSet.add(new Product("Smartphone", 499.99));
        productSet.add(new Product("Tablet", 299.99));
        productSet.add(new Product("Headphones", 199.99));
        productSet.add(new Product("Smartwatch", 199.50));
        productSet.add(new Product("Camera", 599.99));

        // Imprime os produtos usando o percurso "em ordem" de árvores binárias de busca
        productSet.forEach(System.out::println);
        /* 
         Product[name=Smartwatch, price=199.5]
         Product[name=Headphones, price=199.99]
         Product[name=Tablet, price=299.99]
         Product[name=Smartphone, price=499.99]
         Product[name=Camera, price=599.99]
         Product[name=Laptop, price=999.99]
        */
    }
}

A árvore gerada pelo código acima seria algo assim:

Queue e Deque

Outra interface que pertence ao Java Collection é a Queue. Essa interface representa uma estrutura de fila.

Filas tem a propriedade de FIFO (Fisrt In Last Out), o primeiro elemento a entrar na fila será sempre o primeiro a sair dela.

A Deque é um tipo especialmente de fila, uma "fila de duas pontas". Ela permite inserir e excluir da fila pelo inicio (head) ou final (tail).

Deque adiciona métodos com sufixo Fist e Last para manipular a fila como addFirst() e addLast.

Algumas classes que implementam a interface Queue e Deque são LinkedList, PriorityQueue e ArrayDeque.

PriorityQueue

A PriorityQueue é uma fila de prioridade. Ela usa um array para armazenar os valores, mas ela também usa a interface Comparable para definir a prioridade dos elementos adicionados.

Caso a classe que a PriorityQueue guarda não implemente Comparable, pode ser passado um Comparator no construtor para definir o critério de prioridade que será usado.

import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    record Person(String name, int age) {
    }

    public static void main(String[] args) {
        Person jose = new Person("José", 30);
        Person zezinho = new Person("Zezinho", 25);
        Person seuZe = new Person("Seu Zé", 65);
        Person maria = new Person("Maria", 70);

        // Prioridade de atendimento: pessoas mais velhas têm prioridade
        Queue<Person> atendimento = new PriorityQueue<>((p1, p2) -> Integer.compare(p2.age(), p1.age()));

        // Adicionando a fila. Sempre no final da fila
        atendimento.add(jose);
        atendimento.add(maria);
        atendimento.add(zezinho);
        atendimento.add(seuZe);

        System.out.println("Fila de atendimento: " + atendimento.stream().map(Person::name).toList());
        // Fila de atendimento: [Maria, Seu Zé, Zezinho, José]

        // Removendo o primeiro da fila. Sempre o primeiro da fila
        Person atendido = atendimento.poll();
        System.out.println("Atendido: " + atendido.name()); // Atendido: Maria

        System.out.println("Fila após o atendimento: " + atendimento.stream().map(Person::name).toList());
        // Fila após o atendimento: [Seu Zé, Zezinho, José]

        // Verificando o primeiro da fila sem removê-lo
        System.out.println("Primeiro da fila: " + atendimento.peek().name()); // Primeiro da fila: Seu Zé
    }
}

LinkedList

Além de implementar a interface List, o LinkedList implementa a interface Deque. Como uma lista encadeada tem um referência para o inicio (head) e para o final (tail) da lista, para funcionar como uma fila dupla é só usar essas referências para inserir e remover no final e remover no inicio da lista encadeada.

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    record Person(String name, int age) {
    }

    public static void main(String[] args) {
        Person jose = new Person("José", 30);
        Person zezinho = new Person("Zezinho", 25);
        Person seuZe = new Person("Seu Zé", 65);
        Person maria = new Person("Maria", 70);

        Deque<Person> atendimento = new LinkedList<>();

        // Adicionando no final da fila
        atendimento.add(jose);
        atendimento.add(zezinho);

        // Adicionando no início da fila
        atendimento.addFirst(seuZe);
        atendimento.addFirst(maria);

        System.out.println("Fila de atendimento: " + atendimento.stream().map(Person::name).toList());
        // Fila de atendimento: [Maria, Seu Zé, José, Zezinho]

        // Removendo o primeiro da fila
        Person atendido = atendimento.poll();
        System.out.println("Atendido: " + atendido.name());
        // Atendido: Maria

        // Removendo o último da fila
        Person person = atendimento.pollLast();
        System.out.println("Desistiu da fila: " + person.name());
        // Desistiu da fila: Zezinho

        System.out.println("Fila de atendimento: " + atendimento.stream().map(Person::name).toList());
        // Fila de atendimento: [Seu Zé, José]

        // Verificando o primeiro da fila sem removê-lo
        System.out.println("Primeiro da fila: " + atendimento.peek().name());
        // Primeiro da fila: Seu Zé
    }
}

ArrayDeque

O ArrayDeque é uma classe que implementa o Deque. Usa internamente um array circular de tamanho 16 para armazenar os valores.

Internamente, o ArrayDeque guarda o índice do inicio (head) e do fim (tail) do array circular. A medida que adicionar valores no fim com o método add(), por exemplo, a classe altera o valor do tail. E quando adicionar no inicio com o método addFist(), por exemplo, a classe altera o head.

Quando não há mais espaço no array, um novo array com mais capacidade é criado e os dados são copiados para esse novo array

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // adiciona no fim e altera o valor de tail
        deque.add(3);
        deque.add(22);
        deque.addLast(10);

        // adiciona no início e altera o valor de head
        deque.addFirst(15);

        System.out.println(deque);
        // [15, 3, 22, 10]

        // Cria um novo array com mais capacidade e copia os elementos do array antigo
        // para o novo array
        for (int i = 0; i < 100; i++) {
            deque.add(i);
        }

    }
}

Iterable e Collection

Subindo ao nível mais genérico, temos as interfaces Collection e Iterable.

O Collection é uma coleção genérica. Todas as classes do Java Collection implementam essa interface. Se, por exemplo, você precisa modificar qualquer tipo de coleção do Java Collection através de um método, você pode usar um Collection como argumento.

O Iterable é um coleção objetos que pode ser ser lida e ser percorrida um objecto por vez. Se, por exemplo, você precisa acessar cada valor de uma coleção de objetos usando um método você pode receber como argumento um Iterable. Cada classe tem uma forma de guardar os valores e por isso cada uma tem sua implementação de Iterable para pode ser navegável de acordo com sua implementação usando um Iterator, um objeto que sabe navegar por um Iterable.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        Deque<Integer> deque = new LinkedList<>();
        Set<Integer> set = new HashSet<>();

        modifyCollection(list);
        modifyCollection(queue);
        modifyCollection(deque);
        modifyCollection(set);

        System.out.print("List:");
        printCollection(list); // List: 42

        System.out.print("Queue:");
        printCollection(queue); // Queue: 42

        System.out.print("Deque:");
        printCollection(deque); // Deque: 42

        System.out.print("Set:");
        printCollection(set); // Set: 42
    }

    static void printCollection(Iterable<Integer> iterable) {
        // Iterables podem ser usados nesse tipo de for
        for (Integer element : iterable) {
            System.out.println(element);
        }
    }

    static void modifyCollection(Collection<Integer> collection) {
        if (collection.isEmpty()) {
            collection.add(42);
        } else {
            collection.remove(collection.iterator().next());
        }
    }
}

推荐订阅源

DEV Community

Array

Coleções

List

ArrayList

LinkedList

Set

HashSet

LinkedSet

TreeSet

Queue e Deque

PriorityQueue

LinkedList

ArrayDeque

Iterable e Collection