Java Collections Framework: interfaces de coleção

As interfaces garantem a flexibilidade do collections framework

Java Collections Framework: interfaces de mapa

Map faz parte do Collections Framework, mas não herda de Collection.

Java Collections Framework: principais classes

As classes do collections framework estão disponíveis no pacote java.util.

java.util.ArrayList: principais métodos

• add(E e): adiciona um elemento ao final da lista.
• get(int i): retorna o elemento armazenado em uma posição.
• set(int i, E e): substitui o elemento de uma posição.
• remove(int i): remove o elemento localizado em uma posição.
• contains(Object o): verifica se a lista contém determinado elemento.
• indexOf(Object o): retorna a posição da primeira ocorrência ou -1.
• size(): retorna a quantidade de elementos na lista.
• isEmpty(): indica se a lista está vazia.
• clear(): remove todos os elementos da lista.
• getFirst() / getLast(): acessa o primeiro ou o último elemento da lista.

java.util.ArrayList: iteração

Formas comuns de percorrer uma ArrayList:

ArrayList<String> nomes =
    new ArrayList<>();

nomes.add("Ana");
nomes.add("Bruno");
nomes.add("Carla");

for (int i = 0; i < nomes.size(); i++) {
    System.out.println(nomes.get(i));
}

for (String nome : nomes) {
    System.out.println(nome);
}

nomes.forEach(System.out::println);

Iterator<String> it = nomes.iterator();

while (it.hasNext()) {
    String nome = it.next();

    if (nome.startsWith("B")) {
        it.remove();
    }
}

java.util.LinkedList: hierarquia

• Lista duplamente encadeada
• Usada como lista, fila ou pilha
  • List, Queue e Deque
• Mantém a ordem de inserção
• Permite elementos duplicados
• Permite valores null
• Consome mais memória
  • cada elemento aponta para o próximo e para o anterior
• Complexidade das operações
  • acesso por índice: O(n)
  • inserção/remoção nas extremidades: O(1)
  • busca até uma posição no meio: O(n)

java.util.LinkedList: principais métodos

• add(E e): adiciona um elemento ao final da lista.
• addFirst(E e): adiciona um elemento no início.
• addLast(E e): adiciona um elemento no fim.
• get(int i): retorna o elemento armazenado em uma posição.
• getFirst() / getLast(): acessa o primeiro ou o último elemento.
• remove(int i): remove o elemento localizado em uma posição.
• removeFirst() / removeLast(): remove o primeiro ou o último elemento.
• peek(): consulta o primeiro elemento sem removê-lo.
• poll(): remove e retorna o primeiro elemento, ou null se estiver vazia.
• push(E e) / pop(): usa a lista como pilha.

java.util.LinkedList: iteração

LinkedList<String> nomes =
    new LinkedList<>();

nomes.add("Ana");
nomes.add("Bruno");
nomes.add("Carla");

for (String nome : nomes) {
    System.out.println(nome);
}

nomes.forEach(System.out::println);

Iterator<String> it = nomes.iterator();

while (it.hasNext()) {
    if (it.next().startsWith("B")) {
        it.remove();
    }
}

Iterator<String> inverso =
    nomes.descendingIterator();

java.util.ArrayDeque: hierarquia

• Fila de duas pontas baseada em array redimensionável
• Implementa Deque
• Pode ser usada como fila ou pilha
• Não permite valores null
• Não é thread-safe
• Complexidade das operações
  • inserção/remoção nas extremidades: O(1) amortizado
  • busca por elemento: O(n)

java.util.ArrayDeque: principais métodos

• add(E e): adiciona um elemento ao final.
• addFirst(E e): adiciona um elemento no início.
• addLast(E e): adiciona um elemento no fim.
• offer(E e): tenta adicionar um elemento ao final.
• getFirst() / getLast(): acessa o primeiro ou o último elemento.
• peek() / peekFirst() / peekLast(): consulta elementos sem remover.
• remove() / removeFirst() / removeLast(): remove elementos.
• poll() / pollFirst() / pollLast(): remove ou retorna null se vazia.
• push(E e) / pop(): usa o deque como pilha.
• size() / isEmpty() / clear(): consulta ou limpa a coleção.

java.util.ArrayDeque: iteração

ArrayDeque<String> tarefas =
    new ArrayDeque<>();

tarefas.addLast("A");
tarefas.addLast("B");
tarefas.addFirst("Urgente");

for (String tarefa : tarefas) {
    System.out.println(tarefa);
}

tarefas.forEach(System.out::println);

Iterator<String> inverso =
    tarefas.descendingIterator();

while (inverso.hasNext()) {
    System.out.println(inverso.next());
}

while (!tarefas.isEmpty()) {
    System.out.println(tarefas.poll());
}

Ordenação: Comparable e Comparator

Algumas coleções precisam comparar elementos para decidir prioridade ou posição.

class Aluno implements Comparable<Aluno> {
    private String nome;
    private double nota;

    public int compareTo(Aluno outro) {
        return Double.compare(this.nota, outro.nota);
    }
}

Comparator<Aluno> porNome =
    Comparator.comparing(Aluno::nome);

Comparator<Aluno> porNotaDesc =
    Comparator.comparing(Aluno::nota).reversed();

java.util.PriorityQueue: hierarquia

• Fila baseada em prioridade
• Implementa Queue
• Mantém a cabeça da fila conforme ordem natural ou Comparator
• A cabeça da fila é o elemento de maior prioridade
  • na ordem natural, é o menor elemento
• A iteração não garante percorrer em ordem de prioridade
• Não permite valores null
• Não é thread-safe
• Complexidade das operações
  • inserção e remoção da cabeça: O(log n)
  • consulta da cabeça: O(1)
  • busca por elemento: O(n)

java.util.PriorityQueue: principais métodos

• add(E e): insere um elemento na fila de prioridade.
• offer(E e): insere um elemento na fila de prioridade.
• peek(): consulta a cabeça da fila sem remover.
• element(): consulta a cabeça; lança exceção se estiver vazia.
• poll(): remove e retorna a cabeça, ou null se estiver vazia.
• remove(): remove e retorna a cabeça; lança exceção se estiver vazia.
• remove(Object o): remove uma ocorrência específica, se existir.
• comparator(): retorna o comparador usado, ou null se usa ordem natural.
• contains(Object o): verifica se a fila contém determinado elemento.
• size() / isEmpty() / clear(): consulta ou limpa a coleção.

java.util.PriorityQueue: iteração

PriorityQueue<Integer> senhas =
    new PriorityQueue<>();

senhas.offer(30);
senhas.offer(10);
senhas.offer(20);

for (Integer senha : senhas) {
    System.out.println(senha);
}

while (!senhas.isEmpty()) {
    System.out.println(senhas.poll());
}

10
20
30

ArrayList, LinkedList, ArrayDeque e PriorityQueue

Igualdade e hash

Coleções baseadas em hash dependem de equals() e hashCode() para identificar elementos ou chaves.

class Aluno {
    private String matricula;
    private String nome;

    // construtor, getters, equals e hashCode
}

Set<Aluno> alunos = new HashSet<>();

alunos.add(new Aluno("001", "Ana"));
alunos.add(new Aluno("001", "Ana"));

System.out.println(alunos.size()); //1

java.util.HashSet: hierarquia

• Conjunto baseado em tabela hash
• Implementa Set
• Não permite elementos duplicados
• Não garante ordem de iteração
• Permite um valor null
• Não é thread-safe
• Complexidade das operações
  • add, remove, contains e size: O(1), em média
  • iteração depende do tamanho e da capacidade interna

java.util.HashSet: principais métodos

• add(E e): adiciona o elemento se ele ainda não existir.
• remove(Object o): remove o elemento, se estiver presente.
• contains(Object o): verifica se o elemento pertence ao conjunto.
• iterator(): percorre os elementos, sem ordem garantida.
• size(): retorna a quantidade de elementos.
• isEmpty(): indica se o conjunto está vazio.
• clear(): remove todos os elementos.
• toArray(): converte o conjunto para um array.

java.util.HashSet: iteração

HashSet<String> linguagens =
    new HashSet<>();

linguagens.add("Java");
linguagens.add("Python");
linguagens.add("JavaScript");

for (String linguagem : linguagens) {
    System.out.println(linguagem);
}

linguagens.forEach(System.out::println);

Iterator<String> it =
    linguagens.iterator();

while (it.hasNext()) {
    String linguagem = it.next();

    if (linguagem.startsWith("J")) {
        it.remove();
    }
}

java.util.LinkedHashSet: hierarquia

• Conjunto baseado em hash e lista encadeada
• Implementa SequencedSet
• Não permite elementos duplicados
• Mantém ordem de inserção
• Permite um valor null
• Não é thread-safe
• Complexidade das operações
  • add, remove e contains: O(1), em média
  • iteração segue a ordem de inserção

java.util.LinkedHashSet: principais métodos

• add(E e): adiciona o elemento se ele ainda não existir.
• addFirst(E e): adiciona ou move o elemento para o início.
• addLast(E e): adiciona ou move o elemento para o fim.
• getFirst() / getLast(): acessa o primeiro ou o último elemento.
• removeFirst() / removeLast(): remove o primeiro ou o último elemento.
• reversed(): retorna uma visão na ordem inversa.
• contains(Object o): verifica se o elemento pertence ao conjunto.
• size() / isEmpty() / clear(): consulta ou limpa o conjunto.

java.util.LinkedHashSet: iteração

LinkedHashSet<String> nomes =
    new LinkedHashSet<>();

nomes.add("Bruno");
nomes.add("Ana");
nomes.add("Carla");

for (String nome : nomes) {
    System.out.println(nome);
}

Bruno
Ana
Carla

for (String nome : nomes.reversed()) {
    System.out.println(nome);
}

Iterator<String> it = nomes.iterator();

while (it.hasNext()) {
    if (it.next().startsWith("A")) {
        it.remove();
    }
}

java.util.TreeSet: hierarquia

• Conjunto ordenado baseado em árvore
• Implementa NavigableSet
• Não permite elementos duplicados
• Ordena por ordem natural ou Comparator
• Com ordem natural, não aceita null
• Com Comparator, null só funciona se o comparador tratar esse caso
• Não é thread-safe
• Complexidade das operações
  • add, remove e contains: O(log n)
  • navegação por menor/maior elemento: O(log n)
• A ordenação deve ser consistente com equals

java.util.TreeSet: principais métodos

• add(E e): adiciona o elemento se ele ainda não existir.
• remove(Object o): remove o elemento, se estiver presente.
• contains(Object o): verifica se o elemento pertence ao conjunto.
• first() / last(): acessa o menor ou o maior elemento.
• lower(E e) / higher(E e): navega para vizinhos estritos.
• floor(E e) / ceiling(E e): navega para vizinhos inclusivos.
• pollFirst() / pollLast(): remove o menor ou o maior elemento.
• descendingSet(): retorna uma visão em ordem decrescente.
• comparator(): retorna o comparador, ou null se usa ordem natural.

java.util.TreeSet: iteração

TreeSet<String> nomes =
    new TreeSet<>();

nomes.add("Bruno");
nomes.add("Ana");
nomes.add("Carla");

for (String nome : nomes) {
    System.out.println(nome);
}

Ana
Bruno
Carla

for (String nome : nomes.descendingSet()) {
    System.out.println(nome);
}

SortedSet<String> trecho =
    nomes.subSet("Ana", "Carla");

HashSet, LinkedHashSet e TreeSet

java.util.HashMap: hierarquia

Map faz parte do Java Collections Framework, mas não é uma subinterface de Collection.

• Mapa baseado em tabela hash
• Implementa Map
• Associa chaves a valores
• Não permite chaves duplicadas
• Não garante ordem de iteração
• Permite uma chave null e múltiplos valores null
• Não é thread-safe
• Complexidade das operações
  • get e put: O(1), em média
  • iteração depende do tamanho e da capacidade interna

java.util.HashMap: principais métodos

• put(K k, V v): associa uma chave a um valor.
• get(Object k): retorna o valor associado à chave.
• getOrDefault(Object k, V padrao): retorna valor ou padrão.
• remove(Object k): remove o par associado à chave.
• containsKey(Object k): verifica se a chave existe.
• containsValue(Object v): verifica se algum valor existe.
• keySet(): retorna uma visão das chaves.
• values(): retorna uma visão dos valores.
• entrySet(): retorna uma visão dos pares chave-valor.
• size() / isEmpty() / clear(): consulta ou limpa o mapa.

java.util.HashMap: iteração

HashMap<String, Aluno> alunos =
    new HashMap<>();

alunos.put("001", new Aluno("Ana"));
alunos.put("002", new Aluno("Bruno"));

for (String matricula : alunos.keySet()) {
    System.out.println(matricula);
}

for (Aluno aluno : alunos.values()) {
    System.out.println(aluno);
}

for (Map.Entry<String, Aluno> entrada
        : alunos.entrySet()) {
    System.out.println(
        entrada.getKey()
        + ": "
        + entrada.getValue()
    );
}

java.util.LinkedHashMap: hierarquia

• Mapa baseado em hash e lista encadeada
• Implementa SequencedMap
• Mantém ordem de inserção por padrão
• Pode ser criado com ordem de acesso
  • útil em estratégias do tipo LRU
• Permite uma chave null e múltiplos valores null
• Não é thread-safe
• Complexidade das operações
  • get e put: O(1), em média
  • iteração segue a ordem definida

java.util.LinkedHashMap: principais métodos

• put(K k, V v): associa uma chave a um valor.
• putFirst(K k, V v): posiciona a entrada no início.
• putLast(K k, V v): posiciona a entrada no fim.
• get(Object k): retorna o valor associado à chave.
• firstEntry() / lastEntry(): acessa primeira ou última entrada.
• pollFirstEntry() / pollLastEntry(): remove primeira ou última entrada.
• reversed(): retorna uma visão na ordem inversa.
• keySet() / values() / entrySet(): visões do mapa.
• size() / isEmpty() / clear(): consulta ou limpa o mapa.

java.util.LinkedHashMap: iteração

LinkedHashMap<String, String> capitais =
    new LinkedHashMap<>();

capitais.put("DF", "Brasília");
capitais.put("BA", "Salvador");
capitais.put("SP", "São Paulo");

for (var entrada : capitais.entrySet()) {
    System.out.println(entrada);
}

for (var entrada
        : capitais.reversed().entrySet()) {
    System.out.println(entrada);
}

for (String uf : capitais.keySet()) {
    System.out.println(uf);
}

java.util.TreeMap: hierarquia

• Mapa ordenado por chave
• Implementa NavigableMap
• Baseado em árvore rubro-negra
• Ordena por ordem natural ou Comparator
• Não permite chaves duplicadas
• Com ordem natural, não aceita chave null
• Valores null são permitidos
• Não é thread-safe
• Complexidade das operações
  • containsKey, get, put e remove: O(log n)
• A ordenação deve ser consistente com equals

java.util.TreeMap: principais métodos

• put(K k, V v): associa uma chave a um valor.
• get(Object k): retorna o valor associado à chave.
• remove(Object k): remove o par associado à chave.
• containsKey(Object k): verifica se a chave existe.
• firstKey() / lastKey(): acessa menor ou maior chave.
• lowerKey(K k) / higherKey(K k): navega para chaves vizinhas.
• floorKey(K k) / ceilingKey(K k): navega com inclusão.
• firstEntry() / lastEntry(): acessa menor ou maior entrada.
• descendingMap(): retorna uma visão em ordem decrescente.
• keySet() / values() / entrySet(): visões do mapa.

java.util.TreeMap: iteração

TreeMap<String, Integer> notas =
    new TreeMap<>();

notas.put("Bruno", 8);
notas.put("Ana", 10);
notas.put("Carla", 9);

for (var entrada : notas.entrySet()) {
    System.out.println(entrada);
}

for (var entrada
        : notas.descendingMap().entrySet()) {
    System.out.println(entrada);
}

for (String nome : notas.keySet()) {
    System.out.println(nome);
}

HashMap, LinkedHashMap e TreeMap

java.util.Collections

A classe Collections reúne métodos estáticos que operam sobre coleções ou retornam coleções especializadas.

Exemplos de uso:

• ordenar, embaralhar, inverter e buscar em listas;
• encontrar mínimo e máximo;
• contar frequência de elementos;
• criar coleções vazias, imutáveis ou com cópias repetidas;
• criar views sincronizadas, não modificáveis ou com checagem dinâmica de tipo.

java.util.Collections: principais algoritmos

java.util.Collections: wrappers e fábricas

Estudo de caso 1: cadastro de alunos

Cenário: uma coordenação precisa registrar alunos na ordem em que foram cadastrados.

Coleção escolhida: List<Aluno> com ArrayList.

Implementação

1. Crie uma classe Aluno com atributos nome e matricula.
2. Implemente construtor e métodos de acesso.
3. Declare a variável pela interface: List<Aluno> alunos.
4. Instancie com new ArrayList<>().
5. Cadastre alunos com add().
6. Liste em ordem de cadastro com for-each.
7. Conte o total com size().

Verifique: alunos com o mesmo nome são permitidos; a ordem de inserção é preservada.

Estudo de caso 2: inscrições únicas

Cenário: uma atividade complementar não pode receber a mesma matrícula duas vezes.

Coleção escolhida: Set<String>, primeiro com HashSet, depois com LinkedHashSet.

Implementação

1. Declare Set<String> matriculas.
2. Instancie com new HashSet<>().
3. Insira matrículas com add().
4. Insira uma matrícula repetida e observe o retorno de add().
5. Exiba o total com size().
6. Troque para new LinkedHashSet<>() e compare a ordem de iteração.

Verifique: a duplicidade continua bloqueada; a diferença está na previsibilidade da ordem.

Estudo de caso 3: índice por matrícula

Cenário: a secretaria precisa localizar rapidamente um aluno pela matrícula.

Coleção escolhida: Map<String, Aluno> com HashMap.

Implementação

1. Crie uma classe Aluno com atributos nome e matricula.
2. Implemente construtor e métodos de acesso.
3. Declare Map<String, Aluno> alunosPorMatricula.
4. Instancie com new HashMap<>().
5. Cadastre usando put(matricula, aluno).
6. Busque com get(matricula).
7. Percorra pares com entrySet().
8. Teste uma matrícula repetida e observe a substituição do valor.

Verifique: a chave é única; o acesso deixa de depender da posição do aluno.