Estrutura de
Dados
Aula 3 - Listas
Professor Luiz José Hoffmann Filho
[email protected]
Introdução
• Um das formas mais usadas para se manter dados
agrupados é a lista
o Lista de compras, itens de estoque, notas de alunos, informações de
funcionários, etc.
o Lista Linear agrupa informações referentes a um conjunto de elementos
que, de alguma forma, se relacionam entre si
Definição de uma lista
• É uma coleção L:{a1, a2, …, an} , n >= 0, cuja
propriedade estrutural baseia-se apenas na
posição relativa dos elementos, que são dispostos
linearmente.
o Se n= 0, a lista L é vazia.
o Caso contrário:
• a1 é o primeiro elemento de L;
• an é o último elemento de L;
• Ak, 1<k<n, é precedido pelo elemento ak-1 e segundo por ak+1 em L
Operação sobre uma lista
• Operações comuns
o Pesquisa, inserção, alteração e remoção de um determinado elemento
da lista
• Outras operações:
o
o
o
o
o
Determinação do número total de elementos da lista;
Ordenamento da lista;
União de duas ou mais listas;
Particionamento de lista e sub-listas;
Etc…
Tipos especiais de listas
• Pilha: lista linear onde todas as inserções e
remoções são realizadas em um único extremo da
lista. Conhecidas também como listas LIFO (lastin/First-out)
• Fila: lista linear onde todas as inserções são
realizadas num determinado extremo da lista e as
remoções, no outro extremo. Conhecidas também
como FIFO (First-In/First-Out)
Tipos especiais de listas
• Fila Dupla: lista linear onde as inserções e remoções
podem ser feitas em qualquer extermo.
o Fila Dupla de Entrada Restrita (FDER): inserção restrita a um único extermo.
o Fila Dupla de Saída Restrita (FDSR): remoção restrita a um único extremo.
Implementações das listas
• Quanto a alocação de memória, a
implementação de listas lineares pode ser:
Estática
Dinâmica
Sequencial
Encadeada
Estática
Sequencial
-
Dinâmica
Encadeada
Alocação Estática e
Dinâmica
• Estática: quantidade total de memória utilizada
pelos dados de um programa é previamente
conhecida e definida de modo imutável. Durante
toda a execução a quantidade de memória
utilizada não varia.
• Dinâmica: durante a execução, a quantidade de
memória utilizada pelos dados do programa é
variável.
Alocação Sequencial
• Sequencial: elementos da lista são colocados em
posições de memória consecutivas
• Pontos fortes:
o Fácil endereçamento
o Aritmética simples (endereços)
o Fácil inserção e sepressão de elementos no final da lista
• Pontos fracos:
o Dificíl inserção e supressão de elementos no meio da lista
o Dificíl movimentação de elementos na lista
Alocação Encadeada
• Lista sequenciais são estrutura de fácil acesso
o No entanto, o acesso a memória não é ótimo
o Listas muito pequenas sofrem de problemas de re-alocação
o Listas muito grandes alocam memória desnecessarimante
• Listas encadeadas fornecem uma maneira de
otimizar a alocação de memória
o Para cada novo elemento é alocado um espaço em memória
Nós de uma lista
• Cada elemento da lista é chamado de um nó da lista
• Um nó é representado por uma estrutura de contém 2
campos:
o A informação
o Um endereço para o próximo elemento da lista
• A lista é representada como um endereço para o
primeiro nó
o A partir deste nó podemos acessar os demais
LAX
CWB
NWY
Lista Estática Sequencial
• Implementada usando um vetor
o Quantidade Máxima de nós determinada
o Memória alocada em tempo de compilação
o Entretanto, os nós podem, ou não, ser ordenados pelos índices do vetor
• Cada um dos nós podem conter em si próprio um ponteiro para o
próximo elemento, ex:
Em C:
#define MAX 100
Struct node {
int info, next;
}
struct node Node[MAX];
Listas simplesmente
Encadeadas
• Ou Dinâmica Encadeada
o Implementação usando Objetos (Java, Python) ou Ponteiros (C/C++)
o Os espaços de memória para os nós são alocados dinamicamente, à
medida que os novos nós são inseridos na lista
o E liberados à medida que os nós são excluídos
Lista Simplesmente
Encadeadas
• Uma LSE pode ser descrita como sendo um
conjunto dinâmico de nós
o Composta por uma estrutura de nós previamente definida
Info 1
Primeiro
Nós da Lista
Info 2
Info 3
Lista Encadeadas Exemplo
19
Primeiro
12
3
Operações em listas
•
•
•
•
•
•
Criação
Inserção
Exclusão
Busca
Verificação de lista vazia
Liberação de memória
Criação da Lista
Primeiro
NULL
Criação da lista
• Uma outra abordagem é utilizar 2 endereçamentos
o Um para o início e outro para o fim da lista
• O endereço para o fim da lista permite realizar
inserções sem que seja necessário percorrer toda a
lista
• Inicialmente, como a lista está vazia, ambos
apontam para NULL
Inserção na lista
• Existem diversos tipos de inserção que podem ser
feitas em uma lista
o Diferentemente das pilhas e filas, os elementos podem ser inseridos em
qualquer lugar da lista
• Exemplos:
o
o
o
o
Inserção no início
Inserção em uma posição n da lista
Inserção no final da lista
Inserção ordenada na lista
Inserção no início
Primeiro
• Inserindo o elemento 10
• Inserindo o elemento 20
• Inserindo o elemento 30
NULL
Inserção no início –
Inserido o elemento 10
Primeiro
10
NULL
Inserção no início – Caso
Geral
LISTA
Primeiro
el1
newEl
….
eln
Exercícios
• Implementar uma lista em C, com funções para:
o
o
o
o
o
o
o
o
Criar uma lista
Inserir um elemento no início da lista
Inserir um elemento no fim da lista
Imprimir os elementos da lista na tela
Verificar se a lista é vazia
Buscar um elemento qualquer na lista
Retirar um elemento qualquer da lista
Liberar a memória da lista
Lista Duplamente
Encadeadas
Listas duplamente
encadeadas (LDE)
• Listas encadeadas são fácies de serem navegadas
do início para o fim
• No entanto, é difícil navegar do final para o início
da lista
• As listas duplamente encadeadas facilitam tal
navegação
o Permite o deslocameno em ambas as direções
o Um nó em uma LDE armazena duas referências
• Next, que aponta para o próximo nó da lista
• Prev, que aponta para o nó anterior
Lista Simplesmente
Encadeadas
Primeiro
19
12
3
Lista Duplamente
Encadeadas - Exemplo
Primeiro
19
12
3
Sentinelas da cabeça e da
cauda
• Cabeçalho (header), antes do início da lista e final
(trailer) após a cauda da lista
o Não armazenam nenhum elemento
o Header: referência next válida e prev nula
o Trailer: referência next nula e prev válida
• O objetivo LDE deverá apenas armazenar
referências para estas duas sentinelas e um
contador (size) para a quantidade de elementos
(sem contar os sentinelas)
Operações sobre lista
duplamente encadeada
• Remoção de um nodo na extermindade de uma
LDE
• Inserção no início de uma LDE
• Inserção no meio de uma LDE
• Remoção do meio de uma LDE
Exercícios
• Implementar uma lista duplamente encadeada,
com funções para:
o
o
o
o
o
o
o
Criar uma lista
Inserir um elemento no início da lista
Inserir um elemento no fim da lista
Imprimir os elementos da lista na tela
Verificar se a lista á vazia
Buscar um elemento qualquer na lista
Retirar um elemento qualquer da lista
Listas Encadeadas
Circulares
Listas Encadeadas
Circulares (LEC)
• Possui o mesmo tipo de nós de uma LES
• Não existe cabeça nem cauda, o último nó aponta para o
primeiro nó
o
o
Não existe nó inicial nem final
Por isso precisamos de um CURSOR
• Server de ponto de partida (Sabemos quando uma volta foi completa)
• Se a estrutura não for ordenada, o elemento deverá ser
inserido sempre no primeiro lugar.
• Ao remover um elemento, deve-se estar atento para o caso
de a lista ter somente um único elemento, pois a estrutura
torna-se-á vazia.
Lista Encadeadas Circular Exemplo
Cursor
19
12
3
Exercícios
1. Escreva uma função que copie um vetor para
um lista encadeada.
2. Escreva uma função que copie uma lista
encadeada para um vetor.
3. Escreva uma função que faça uma cópia de
uma lista dada.
4. Escreva uma função que concatena duas listas
encadeadas(isto é. “amarra” a segunda no final
da primeira).
5. Escrever uma função que conta o número de
nos de uma lista encadeada.
6. Faça todos os exercícios anteriores utilizando
uma lista duplamente encadeada.