AULA 09
MÓDULO 2
coleções java
⏱ 60 min
Coleções e Big-O
ArrayList não serve para tudo. Tabela completa de complexidade: ArrayList, LinkedList, HashMap, TreeMap. Generics e type erasure. Conexão com ED1/ED2.
ArrayListLinkedListHashMapTreeMapBig-OGenericsCollection Framework
O custo que ArrayList esconde
Usar ArrayList para tudo é o erro mais comum de quem não estudou Estrutura de Dados. Você já viu em ED1 que lista encadeada e array têm complexidades diferentes. Hoje mapeamos isso para as coleções Java.
conexão com ED1 e ED2
Estrutura de Dados 1: lista encadeada (O(1) inserção no início), lista com array (O(1) acesso por índice). ED2: tabela de dispersão (O(1) médio para busca), árvore BST (O(log n)). Tudo isso está nas coleções Java!Collection Framework — tabela de complexidade
| Coleção | Estrutura interna | get(i) | add(fim) | remove(meio) | contains |
|---|---|---|---|---|---|
| ArrayList | Array dinâmico | O(1) | O(1)* | O(n) | O(n) |
| LinkedList | Lista dupla | O(n) | O(1) | O(1) | O(n) |
| HashSet/Map | Array de buckets | — | O(1)* | O(1)* | O(1)* |
| TreeSet/Map | Árvore rubro-negra | — | O(log n) | O(log n) | O(log n) |
(*) amortizado — pode ser pior em casos de rehash/redimensionamento
regra de ouro
Operação dominante define a coleção. Acesso aleatório frequente → ArrayList. Inserções/remoções no meio → LinkedList. Busca por chave → HashMap. Ordenado + busca → TreeMap.Generics — segurança em tempo de compilação
Sem generics: List lista aceita qualquer Object — erros de tipo aparecem em runtime. Com generics: List<Aluno> — erros aparecem em compilação.
erasure
Em runtime, os generics são apagados (type erasure). List
java
// Collection Framework — escolha certa para cada cenário // ArrayList: acesso por índice rápido, remoção no meio cara List<Aluno> turma = new ArrayList<>(); turma.add(new Aluno("Ana", 9.0)); turma.add(new Aluno("Bob", 7.5)); Aluno a = turma.get(0); // O(1) — acesso por índice turma.remove(0); // O(n) — desloca todos! // LinkedList: inserção/remoção nas pontas O(1) Deque<String> fila = new LinkedList<>(); fila.addLast("cliente1"); // O(1) String atender = fila.pollFirst(); // O(1) // HashMap: busca por chave O(1) médio Map<String, Aluno> porMatricula = new HashMap<>(); porMatricula.put("2024001", new Aluno("Ana", 9.0)); Aluno encontrado = porMatricula.get("2024001"); // O(1) médio // TreeMap: ordenado por chave — O(log n) Map<String, Aluno> ordenado = new TreeMap<>(); ordenado.put("2024003", new Aluno("Carlos", 8.0)); ordenado.put("2024001", new Aluno("Ana", 9.0)); // iteração já sai em ordem de matrícula ordenado.forEach((k, v) -> System.out.println(k + ": " + v)); // Collections.sort() com Comparable Collections.sort(turma); // Aluno precisa implementar Comparable
quiz · aula 09
Teste seus conhecimentos em Java
0/3 respondidas
QUESTÃO 01
Para uma fila de atendimento onde removemos sempre do início e inserimos sempre no final, qual coleção usar?
QUESTÃO 02
Por que não usar ArrayList para uma agenda telefônica onde você busca por nome?
QUESTÃO 03
O que é 'erasure' de generics em Java?
0/3