Implementação de Listas em Programação

Prévia do material em texto

Prof. Me. Marcos Frazão
LISTAS
• Listas são conjuntos de elementos, objetos,
variáveis, tarefas, ou qualquer coisa que se
possa enumerar e formar um conjunto;
• As listas estão presentes em nossa vida, desde
o nosso nascimento, por exemplo, com a lista
de compras que nossos pais tiveram que fazer
para nós.
LISTAS
• Exemplo de Lista de Compras:
– 5Kg de farinha;
– 2Kg de açucar;
– 500g de carne moída;
– 2Kg de arroz;
– 4L de leite;
– 1Kg de feijão;
– Etc..
LISTAS
• Exemplo de Lista Telefônica:
– Asdf de Zxcv: (44) 4444-4444
– Beutrano Cruz: (33) 3333-3333
– Ciclano da Silva: (22) 2222-2222
– Fulano de Tal: (11) 1111-1111
COMPORTAMENTO DE UMA LISTA
• Lista: Vazia!
COMPORTAMENTO DE UMA LISTA
• Lista:
– Inserir “C”
C
COMPORTAMENTO DE UMA LISTA
• Lista:
C
COMPORTAMENTO DE UMA LISTA
• Lista:
– Inserir “D”
C
D
COMPORTAMENTO DE UMA LISTA
• Lista:
C
D
COMPORTAMENTO DE UMA LISTA
• Lista:
– Inserir “B”
B
C
D
COMPORTAMENTO DE UMA LISTA
• Lista:
B
C
D
COMPORTAMENTO DE UMA LISTA
• Lista:
– Inserir “F”
B
C
D
F
COMPORTAMENTO DE UMA LISTA
• Lista:
B
C
D
F
COMPORTAMENTO DE UMA LISTA
• Lista:
– Inserir “E”
E
B
C
D
F
COMPORTAMENTO DE UMA LISTA
• Lista:
B
C
D
E
F
COMPORTAMENTO DE UMA LISTA
• Lista:
B
C
D
E
F
COMPORTAMENTO DE UMA LISTA
• Lista:
– Remover “B”
B
C
D
E
F
COMPORTAMENTO DE UMA LISTA
• Lista:
– Remover “B”
B
C
D
E
F
COMPORTAMENTO DE UMA LISTA
• Lista:
C
D
E
F
COMPORTAMENTO DE UMA LISTA
• Lista:
– Remover “F”
C
D
E
F
COMPORTAMENTO DE UMA LISTA
• Lista:
– Remover “F”
C
D
E
F
COMPORTAMENTO DE UMA LISTA
• Lista:
C
D
E
COMPORTAMENTO DE UMA LISTA
• Lista:
– Remover “D”
C
D
E
COMPORTAMENTO DE UMA LISTA
• Lista:
– Remover “D”
C
D
E
COMPORTAMENTO DE UMA LISTA
• Lista:
C
E
LISTAS
• Implementando as listas:
– As listas podem ser implementadas de
várias formas, mas num aspecto mais geral
podemos separar em duas principais:
• Em Arrays; ou
• Encadeadas.
LISTAS EM ARRAYS
• Em Arrays:
– Imagine que a lista anterior
tinha posições fixas e pré-
determinadas:
• Um array é uma estrutura com
posições fixas, cada elemento
da lista deve ser colocado em
uma posição no array;
• Ao inserir ou excluir um
elemento, talvez seja necessário
realocar todos os demais
elementos.
LISTAS EM ARRAYS
de qualquer tamanho é
• Prós:
– Criar um array 
muito simples;
– Não há necessidade de compreender 
ponteiros ou referências;
• Contras:
– Limitações quanto ao tamanho de memória;
– Custo computacional maior;
– Alocação de memória exagerada.
LISTAS ENCADEADAS
• Encadeado, Dicionário Houaiss:
– adjetivo
– 1. disposto ou ligado por ou como por 
cadeias; ordenado, junto;
– 2. preso, submetido;
LISTAS ENCADEADAS
• Prós:
– Extremamente eficiente no custo de 
memória e de processamento;
– Nunca acarreta em movimentar todos os 
elementos;
• Contras:
– Envolve conceitos mais avançados de 
programação:
• Ponteiros ou Referências.
LISTAS ENCADEADAS
• Para criarmos uma lista encadeada, precisamos
primeiro definir o que será armazenado nela;
• Por exemplo, para criarmos uma lista de
contatos, gostaríamos de armazenar os nomes,
telefones e e-mails de diversas pessoas:
• Exemplo de elemento “Contato” da lista:
LISTAS ENCADEADAS
Contato 
string Nome; 
long Telefone; 
string Email;
LISTAS ENCADEADAS
• Exemplo da Idéia de Encadeamento:
• Mas como fazer isto?
Contato 
string Nome; 
long Telefone; 
string Email;
Contato 
string Nome; 
long Telefone; 
string Email;
Contato 
string Nome; 
long Telefone; 
string Email;
LISTAS ENCADEADAS
• Conforme vamos criando elementos na
do computador, estes 
vão ficando espalhados e
memória 
elementos 
desconexos;
• Para criar listas encadeadas precisamos
criar elementos que façam referência a
outro elemento, ou seja, indiquem onde
podemos encontrar um outro elemento.
• Exemplo de elemento encadeado:
LISTAS ENCADEADAS
Contato 
string Nome; 
long Telefone; 
string Email;
Contato Proximo;
LISTAS ENCADEADAS
• Exemplo com Elemento Encadeado:
Contato 
string Nome = “abc” 
long Telefone = 123 
string Email = ”a@b” 
Contato Proximo =
Contato 
string Nome = “zxy” 
long Telefone = 987 
string Email = “c@d” 
Contato Proximo =
Contato
string Nome = “qwe”
long Telefone = 546
string Email = “r@f”
Contato Proximo =
LISTAS ENCADEADAS
• Exemplo Duplamente Encadeado:
Contato 
string Nome = “abc” 
long Telefone = 123 
string Email = ”a@b” 
Contato Proximo = 
Contato Anterior =
Contato 
string Nome = “zxy” 
long Telefone = 987 
string Email = “c@d” 
Contato Proximo = 
Contato Anterior =
Contato
string Nome = “qwe” 
long Telefone = 546 
string Email = “r@f” 
Contato Proximo = 
Contato Anterior =
LISTAS ENCADEADAS
• Iniciando uma lista vazia:
– Contato Inicio_Lista = null;
– Contato Fim_Lista = null;
• O “valor” de referência null é usado para
quando ainda não existe um objeto na memória
para qual a variável irá fazer referência;
• O último elemento da lista aponta para null.
• Iniciando uma lista com 1 elemento:
– Contato Inicio_Lista = new Contato();
LISTAS ENCADEADAS
– Criando a Lista:
• Contato Inicio_Lista = new Contato();
• Contato Fim_Lista = Inicio_Lista;
• Inicio_Lista.Nome = “abc”;
• Inicio_Lista.Telefone = 123;
• Inicio_Lista.Email = “a@b”;
• Inicio_Lista.Proximo = null;
Contato 
string Nome = “abc” 
long Telefone = 123 
string Email = ”a@b” 
Contato Proximo =
LISTAS ENCADEADAS
– Adicionando um segundo elemento:
• Contato novo = new Contato();
• novo.Nome = “zxy”;
• novo.Telefone = 987;
• novo.Email = “c@d”;
• novo.Proximo = null;
• Fim_Lista.Proximo = novo;
• Fim_Lista = novo;
Contato 
string Nome = “abc” 
long Telefone = 123 
string Email = ”a@b” 
Contato Proximo =
Contato 
string Nome = “zxy” 
long Telefone = 987 
string Email = “c@d” 
Contato Proximo =
LISTAS ENCADEADAS
• Percorrendo a lista:
Contato aux = Inicio_Lista;
while (aux != null) {
//Faz alguma tarefa com o elemento aux
aux = aux.Proximo;
}
LISTAS ENCADEADAS
• Removendo o elemento “zxy”:
– Inicio_Lista.Proximo = null;
Contato 
string Nome = “abc” 
long Telefone = 123 
string Email = ”a@b” 
Contato Proximo =
Contato 
string Nome = “zxy” 
long Telefone = 987 
string Email = “c@d” 
Contato Proximo =
▪Todas as linguagens de programação
possuem alguma forma de representar
grupos de dados em comum.
▪A mais popular a todas as linguagens, são
os arrays ou vetores.
▪Assim, muitos programadores costumam
resumir seu arsenal a apenas um único
dado ou então, um array.
▪No entanto, existem várias outras opções
para "estruturar" esses dados.
LISTAS EM JAVA
Em Java, as estruturas de
dados estão representadas na
linguagem no Java
Collections Framework
ARRAY EM JAVA
• Array é uma estrutura linear onde dados 
homogêneos são armazenados em espaços 
contínuos da memória. 
• O acesso a cada elemento é feito através de um 
índice.
• Como parte da modernização que Java vem 
passando, os organizadores da linguagem 
adicionaram ao Collections Framework classes 
utilitárias que seguem o esquema de 
nomenclatura: Array -> Arrays, Collection -> 
Collections, File -> Files
LINKED LIST
Existe um elemento "raiz", logo, cada elemento 
está ligado a outro. O tamanho é dinâmico e a 
lista pode ser "espalhada" pela memória.
Essa estrutura costuma ser negligenciada devido 
suas semelhanças com ArrayList (a interface Java 
java.util.List implementada como um array). 
LINKED LIST
No entanto, a principal vantagem está em listas 
com tamanho dinâmico que costumam crescer 
quando necessário. 
Enquanto no melhor caso da operação de adição, 
ambas tem custo O(1) (em notação Big O, caso 
seja necessário redimensionar o array, o custo 
será O(log(n)).
STACK
Representa uma pilha (como um baralho de cartas ou 
livros empilhados), seguindo o algoritmo LIFO. 
As quatro operações principais são: push(e) - insere 
um elemento no topo; pop() - remove o elemento do 
topo; isEmpty() -informa verdadeiro/falso se a pilha 
está vazia; peek() - acessa o elemento do topo (sem 
remover).
Essa estrutura é muito usada para representações de 
estado ou histórico de navegação, onde o mais 
recente está sempre no topo.
SET
Representa um grupo de dados homogêneos 
únicos, sem repetições. 
Por isso, deve haver uma forma de comparar os 
elementos de forma a decidir se são iguais ou 
não. 
Em Java, essa comparação é feita pelos métodos 
equals e hashcode. 
As principais classes que implementam a interface 
Set são: HashSet, TreeSet e LinkedHashSet.
HASHMAP
Usa funções hash para determinar a posição de 
cada elemento. 
Uma função hash é um algoritmo que mapeia 
dados de entrada de comprimento variável em 
dados de comprimento fixo. 
Assim, cada elemento a ser inserido na estrutura 
tem o seu endereço calculado. Isso evita "colisões" 
e acelera as operações de leitura.
HASHMAP
No código a seguir, vamos contar a ocorrência de 
cada caractere na frase "estruturas de dados 
Java", desconsiderando os espaços em branco. 
A chave do nosso mapa, key, será o caractere e 
o valor, value, será o contador. Como esperado, a 
saída do programa será "a: 4, r: 2, s: 3, t: 2, d: 3, 
e: 2, u: 2, v: 1, j: 1, o: 1".
Em relação ao tipo de estrutura de dados conhecido como lista ligada ou lista 
encadeada, é correto afirmar que:
Alternativas
a) Um elemento deve entrar por uma extremidade e ser removido pela outra 
extremidade.
b) Não é uma estrutura flexível, pois há necessidade de definição de um tamanho 
máximo de elementos.
c) O primeiro elemento que entrar só poderá ser removido por último, após todos os 
outros elementos serem removidos.
d) É uma estrutura multidimensional e homogênea.
e) A sucessão dos elementos é determinada por um ponteiro que indica a posição do 
próximo elemento.
Exercício
Em relação ao tipo de estrutura de dados conhecido como lista ligada ou lista 
encadeada, é correto afirmar que:
Alternativas
a) Um elemento deve entrar por uma extremidade e ser removido pela outra 
extremidade.
b) Não é uma estrutura flexível, pois há necessidade de definição de um tamanho 
máximo de elementos.
c) O primeiro elemento que entrar só poderá ser removido por último, após todos os 
outros elementos serem removidos.
d) É uma estrutura multidimensional e homogênea.
e) A sucessão dos elementos é determinada por um ponteiro que indica a posição do 
próximo elemento.
•
Exercício
https://www.qconcursos.com/questoes-de-concursos/disciplinas/tecnologia-da-informacao-algoritmos-e-estrutura-de-dados/listas/questoes#question-belt-2469413-teacher-tab
Acerca de estrutura de dados e algoritmos, julgue o item a seguir.
Em uma lista circular ordenada, o acesso ao maior elemento possui 
complexidade de tempo de pior caso O(1).
Alternativas
( ) Certo
( )Errado
Exercício
Acerca de estrutura de dados e algoritmos, julgue o item a seguir.
Em uma lista circular ordenada, o acesso ao maior elemento possui 
complexidade de tempo de pior caso O(1).
Alternativas
( X ) Certo
( )Errado
Exercício
CONCLUSÃO
No desenvolvimento de software precisamos
representar conjuntos de dados.
A disciplina da Ciência da Computação estuda a
melhor forma de estruturar essa informação é
chamada Estrutura de Dados.
Elas são definidas de acordo com a natureza dos
dados e as operações mais comuns pretendidas.
Em Java, as estruturas de dados estão disponíveis no
Java Collection Framework.
Prof. Me. Marcos Frazão
	Slide 1: ED: LISTAS
	Slide 2: Listas
	Slide 3: Listas
	Slide 4: Listas
	Slide 5: Comportamento de uma Lista
	Slide 6: Comportamento de uma Lista
	Slide 7: Comportamento de uma Lista
	Slide 8: Comportamento de uma Lista
	Slide 9: Comportamento de uma Lista
	Slide 10: Comportamento de uma Lista
	Slide 11: Comportamento de uma Lista
	Slide 12: Comportamento de uma Lista
	Slide 13: Comportamento de uma Lista
	Slide 14: Comportamento de uma Lista
	Slide 15: Comportamento de uma Lista
	Slide 16: Comportamento de uma Lista
	Slide 17: Comportamento de uma Lista
	Slide 18: Comportamento de uma Lista
	Slide 19: Comportamento de uma Lista
	Slide 20: Comportamento de uma Lista
	Slide 21: Comportamento de uma Lista
	Slide 22: Comportamento de uma Lista
	Slide 23: Comportamento de uma Lista
	Slide 24: Comportamento de uma Lista
	Slide 25: Comportamento de uma Lista
	Slide 26: Listas
	Slide 27: Listas em Arrays
	Slide 28: Listas em Arrays
	Slide 29: Listas Encadeadas
	Slide 30: Listas Encadeadas
	Slide 31: Listas Encadeadas
	Slide 32: Listas Encadeadas
	Slide 33: Listas Encadeadas
	Slide 34: Listas Encadeadas
	Slide 35: Listas Encadeadas
	Slide 36: Listas Encadeadas
	Slide 37: Listas Encadeadas
	Slide 38: Listas Encadeadas
	Slide 39: Listas Encadeadas
	Slide 40: Listas Encadeadas
	Slide 41: Listas Encadeadas
	Slide 42: Listas Encadeadas
	Slide 43
	Slide 44: LISTAS EM JAVA
	Slide 45: Array EM JAVA
	Slide 46
	Slide 47: Linked list
	Slide 48: Linked list
	Slide 49
	Slide 50: stack
	Slide 51
	Slide 52: set
	Slide 53
	Slide 54: hashmap
	Slide 55: hashmap
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 65: conclusão
	Slide 66: ED: LISTAS