Esse curso foi montado ao longo dos 4 anos que ministramos o curso de Estrutura de Dados e Algoritmos em Java nos cursos de verão da USP.

Todos os tipos de aplicações (desktop, web, distribuída ou mobile) guardam dados para processá-los. O desempenho dessas aplicações depende muito da forma que os dados são armazenados. O conhecimento sobre as diversas estruturas de dados é de uso fundamental para o bom desenvolvedor. Esse curso apresenta o funcionamento interno das principais estruturas de dados e os algoritmos para manipulá-las. O foco é mostrar quais são as vantagens e desvantagens de cada estrutura e em que situações usá-las.

O curso também aborda o framework de Collections do Java, onde há implementações semelhantes das diversas estrutura de dados apresentadas. Desta forma, o desenvolvedor apenas precisa ter o discernimento para escolher qual estrutura usar dependendo do tipo de problema que ele está resolvendo. Esse discenimento é obtido através do conhecimento mais profundo dessas estruturas.

Vamos do Vector e ArrayList até o HashSet e HashMap, passando por tópicos como equals e hashCode, comparando a performance dos algoritmos em relação ao consumo de tempo. Todas essas estruturas de dados serão implementadas do zero, de maneira similiar às que existem no java.util. Problemas comuns em que as soluções usam destas estruturas são apresentados e dicutidos. Boas práticas de OO, como o uso de interface, generics e encapsulamento, são vistas no decorrer da criação das estruturas

Pré-requisitos: Curso FJ-11 ou: linguagem Java, variáveis primitivas e orientação a objetos, tratamento de erro, conhecimentos fundamentais de Java SE.

Posts relacionados no blog

Prefácio

Introdução

1. Introdução
2. Algoritmo e Implementação
3. Estrutura de Dados
4. Sobre este texto

Armazenamento Sequencial

1. Motivação
2. O problema da listagem de alunos
3. Listas
4. Modelagem
5. Exercícios: Armazenamento

Vetores

1. Os testes primeiro
2. Operações em vetores
3. Adicionar no fim da Lista
4. O método toString() para o Vetor
5. Informar o tamanho da Lista
6. Verificar se um aluno está presente no vetor
7. Pegar o aluno de uma dada posição do array
8. Adicionar um aluno em uma determinada posição do array
9. Remover um aluno de uma dada posição
10. Alocação Dinâmica
11. Generalização
12. API do Java
13. Exercícios: Vetores
14. Exercícios opcionais

Listas Ligadas

1. Solução clássica de Lista Ligada
2. Célula e Lista Ligada
3. Definindo a interface
4. Testes
5. Operações sobre uma Lista
6. Adicionando no começo da Lista
7. Adicionando no fim da Lista
8. Percorrendo nossa Lista
9. Adicionando em qualquer posição da Lista
10. Pegando um elemento da Lista
11. Removendo do começo da Lista
12. Removendo do fim da Lista
13. Removendo de qualquer posição
14. Verificando se um elemento está na Lista
15. O tamanho da Lista
16. Lista Duplamente Ligada
17. Adicionando no começo da Lista
18. Adicionando no fim da Lista
19. Adicionando em qualquer posição da Lista
20. Removendo do começo da Lista
21. Removendo do fim da Lista ou de qualquer posição
22. API
23. Exercícios: Lista Ligada

Pilhas

1. Introdução
2. Solução do problemas das Peças
3. Operações em pilhas
4. Inserir uma peça
5. Remover uma peça
6. Informar se a pilha está vazia
7. Generalização
8. API do Java
9. Escapando do Labirinto
10. Exercícios: Pilha

Filas

1. Introdução
2. Interface de uso
3. Operações em Fila
4. Inserir uma aluno
5. Remover um aluno
6. Informar se a Fila está vazia
7. Generalização
8. API do Java
9. Exercícios: Fila

Armazenamento sem repetição com busca rápida

1. Motivação
2. O problema do vocabulário
3. Conjuntos

Tabelas de Espalhamento

1. Introdução
2. Tabela de Espalhamento
3. Função de Espalhamento
4. Operações necessárias
5. Adicionar uma palavra
6. Remover uma palavra
7. Verificar se uma palavra está ou não no Conjunto
8. Recuperar todas as palavras do Conjunto
9. Informar o tamanho do Conjunto de palavras
10. Exercícios: Tabela de Espalhamento 1
11. Diminuindo Colisões
12. Espalhando Melhor
13. Exercícios: Tabela de Espalhamento 2
14. Tabela Dinâmica
15. Exercícios: Tabela de Espalhamento 3
16. Generalização
17. equals e hashCode
18. Parametrizando o Conjunto
19. API do Java
20. Exercícios: Tabela de Espalhamento 4

Armazenamento Associativo

1. Motivação
2. Mapa
3. Exercícios: Armazenamento Associativo

Mapas com Lista

1. Introdução
2. Operações em mapas
3. Adicionar uma associação
4. Recuperar o valor associado a uma dada chave
5. Remover a associação que contem uma determinada chave
6. Verificar se uma dada chave está em alguma associação
7. Informar o tamanho do Mapa
8. Exercícios: Mapas

Mapas com Espalhamento

1. Introdução
2. Operações
3. Verificando se uma chave existe
4. Removendo uma associação dado uma chave
5. Adicionando uma associação dado uma chave
6. Recuperando o valor associado a uma determinada chave
7. Performance das operações
8. Generalização e Parametrização
9. API do Java