Algoritmos e Estruturas de Dados
Listas Encadeadas
Prof. Me. Claudio Benossi
[email protected]
Listas Encadeadas
 Listas encadeadas ou listas ligadas
representam uma seqüência de objetos na
memória do computador.
 Exemplo: Lista de afazeres
1. Comprar uma lâmpada
2. Trocar uma lâmpada queimada
3. Procurar uma conta no quarto
4. Pagar uma conta na internet
5. Desligar o computador
6. Dormir
Listas Encadeadas
Na lista de afazeres anterior, uma tarefa
dependia da execução da tarefa anterior
Ação atual
Próxima
ação
Listas Encadeadas
1. Comprar
lâmpada
2
2. Trocar
lâmpada
3
3. Procurar
conta
4
4. Pagar
conta
5
5. Desligar
micro
6
6. Dormir
fim
Listas Encadeadas
:: Representação por vetores
Como representar a lista anterior em um
programa escrito na Linguagem C?
 Primeira opção: vetores ou matrizes
Tarefa:
Índice:
Comprar Trocar Procurar
lâmpada lâmpada conta
1
2
3
Pagar
conta
Desligar
micro
Dormir
4
5
6
Listas Encadeadas
:: Representação por vetores
Primeira opção: vetores ou matrizes
 Como acrescentar “Ligar micro”?
Tarefa:
Índice:
Comprar Trocar Procurar
lâmpada lâmpada conta
1
2
3
Pagar
Ligar
conta
micro
4
Desligar
micro
5
Dormir
6
7
Listas Encadeadas
:: Representação por vetores
Primeira opção: vetores ou matrizes
 Os itens da lista são armazenados em posições
contíguas de memória.
 A lista pode ser percorrida em qualquer direção.
 A inserção de um novo item pode ser realizada após
o último item com custo constante.
 A inserção de um novo item no meio da lista requer
um deslocamento de todos os itens localizados após
o ponto de inserção.
 Retirar um item do início da lista requer um
deslocamento de itens para preencher o espaço
deixado vazio.
Listas Encadeadas
:: Representação por ponteiros
Segunda opção: ponteiros
 Estruturas de dados dinâmicas: estruturas de dados
que contém ponteiros para si próprias.
struct lista {
char nome_tarefa[30];
float duracao;
char responsavel[30];
...
struct lista *prox;
};
ponteiro para a
própria estrutura lista
Listas Encadeadas
:: Representação por ponteiros
Representação gráfica de um elemento da lista:
campos de informação
próximo nó
 Cada item é encadeado com o seguinte, mediante
uma variável do tipo ponteiro.
 Permite utilizar posições não contíguas de memória.
 É possível inserir e retirar elementos sem
necessidade de deslocar os itens seguintes da lista.
Listas Encadeadas
:: Representação por ponteiros
 Cada item em particular de uma lista pode ser chamado
de elemento, nó, célula, ou item.
 O apontador para o início da lista também é tratado
como se fosse uma célula (cabeça), para simplificar as
operações sobre a lista.
 O símbolo / representa o ponteiro nulo (NULL),
indicando o fim da lista.
p
3
5
2
4
/
162
Operações sobre lista encadeada
Podemos realizar algumas operações sobre uma
lista encadeadas, tais como:
 Inserir itens;
 Retirar itens;
 Buscar itens.
Para manter a lista ordenada, após realizar
alguma dessas operações, será necessário
apenas movimentar alguns ponteiros (de um a
três elementos).
Operações sobre lista encadeada
Outras operações possíveis:
 Criar uma lista
 Destruir uma lista
 Ordenar uma lista
 Intercalar duas listas
 Concatenar duas listas
 Dividir uma lista em duas
 Copiar uma lista em outra
Operações sobre lista encadeada
:: Inserção de itens
Podemos inserir itens:
 No começo de uma lista
 No final de uma lista
 No meio de uma lista
Operações sobre lista encadeada
:: Inserção de itens no início
O endereço armazenado no ponteiro p deve ser
alterado para o endereço do item a ser
acrescido à lista.
p
5
2
4
/
3
163
Operações sobre lista encadeada
:: Inserção de itens no final
O endereço armazenado em p será alterado
caso a lista esteja vazia ou
O campo prox do último item será alterado.
/
p
3
p
3
/
5
/
164
Operações sobre lista encadeada
:: Inserção de itens no meio
Campo prox do item a ser inserido recebe o
campo prox do item posterior
Campo prox do item antecessor recebe o
endereço do item a ser inserido
p
3
2
4
/
5
lista[5].prox ← lista[2]
lista[3].prox ← 5
165
Operações sobre lista encadeada
:: Remoção de itens no início
O endereço armazenado no ponteiro p deve ser
alterado para o endereço do item que segue o
primeiro item da lista.
p
5
2
4
/
166
Operações sobre lista encadeada
:: Remoção de itens no final
O campo prox do último item será alterado
caso a lista contenha mais de um item ou
O endereço armazenado em p será alterado
para NULL.
p
3
p
3
/
5
/
/
167
Operações sobre lista encadeada
:: Remoção de itens no meio
Item antecessor recebe o campo prox do item
a ser removido
lista[3].prox ← lista[5].prox
p
3
5
2
4
/
168
Um outro exemplo
O programa abaixo...
169
Outros tipos de Listas Encadeadas
 Existem ainda outras variações de lista encadeada,
dentre elas:
 Listas Duplamente Encadeadas
 Listas Circulares
Listas Duplamente Encadeadas
Cada elemento da lista é ligado a seu sucessor e
a seu predecessor.
Possibilita um trajeto em ambos os sentidos,
simplificando o gerenciamento da lista.
Listas Duplamente Encadeadas
A estrutura de dados de um nó de uma lista
duplamente encadeada recebe um novo campo:
um ponteiro para o nó antecessor.
typedef struct
int
struct noh
struct noh
} tipoNode;
noh {
info;
*ant;
*prox;
170
Listas Circulares
São listas encadeadas cujo fim aponta para o
seu início, formando um círculo que permite
uma trajetória contínua na lista. Podem ser:
 Singularmente encadeadas
 Duplamente encadeadas
Listas Circulares
A estrutura de um nó de uma lista circular
permanece a mesma. Dependerá apenas se o
encadeamento da lista é duplo ou singular.
O que modifica é que não há mais necessidade
de dois ponteiros para indicar o início e o fim da
lista.
Basta marcar um nó da lista para evitar loops.
171
Questões