Listas Ligadas
Estruturas de Dados e
Algoritmos
05/11/2015
Fábio Lopes Caversan
1
Listas Ligadas

Desvantagens do armazenamento
seqüencial para representar pilhas e
filas:
 Subdimensionamento
ou
superdimensionamento da memória devido
a alocação fixa de uma certa quantidade de
memória antes da execução do programa
 Possibilidade de overflow
05/11/2015
Fábio Lopes Caversan
2
Compartilhando a memória
disponível




Suponha uma implementação seqüencial de
pilhas
Stack x,y,z;
Suponha que sejam inicializadas, de forma
estática, com 50 elementos
x,y,z terão, durante a utilização,
respectivamente, no máximo, 20, 10 e 70
elementos
05/11/2015
Fábio Lopes Caversan
3
Fazendo cálculos
100 células seriam necessárias
 Porém, na inicialização, deve-se usar o
tamanho 70 para não ocorrer um overflow
 Então, temos 3* 70 = 210,quando somente
100 serão utilizadas
 Que tal evitar esse desperdício através de
um gerenciador de memória?
 Ele controlaria quem recebe mais ou
menos células de memória

05/11/2015
Fábio Lopes Caversan
4
Agrupando as células livres
num banco de memória livre
Banco de memória
05/11/2015
Variáveis
x
y
z
nada
nada
nada
Fábio Lopes Caversan
5
Operação
Banco de memória
x.Push(a)
x
y
z
(nada)
(nada)
y.Push(b)
(nada)
y.Push(c)
(nada)
x.Push(d)
(nada)
z.Push(e)
05/11/2015
(nada)
Fábio Lopes Caversan
6
Operação
Banco de memória
z.Push(f)
(nada)
x
y
z
y.Pop()
z.Pop()
(nada)
x.Pop()
(nada)
z.Push(g)
05/11/2015
Fábio Lopes Caversan
7
Considerações importantes
A ordem das células de memória
disponíveis no banco, no decorrer da
execução da aplicação, muda
substancialmente
 O importante é manter um controle
sobre a ordem lógica das células de
memória e não, necessariamente, sobre
a ordem física

05/11/2015
Fábio Lopes Caversan
8
Lista Ligada (Encadeada) Linear
Cada item na lista é um nó
 Todo nó contem dois campos: o de
informação e do endereço seguinte
 Campo de informação: armazena o real
elemento da lista
 Campo de endereço: endereço do
próximo nó na lista. É um ponteiro!

05/11/2015
Fábio Lopes Caversan
9
Algumas representações do nó ...
Endereço do próximo
nó
Informação
nulo
05/11/2015
Fábio Lopes Caversan
10
Continuando . . .







A lista ligada inteira é acessada a partir de um ponteiro
externo que aponta para o primeiro nó da lista
Um ponteiro externo não está incluindo dentro de um
nó. É acessado por referência a uma variável
O campo do próximo endereço do último nó da lista
contém um valor especial: null
O ponteiro nulo (null) marca o final da lista
Uma lista sem nós é uma lista vazia ou nula
Nesse caso, o ponteiro externo para a lista é nulo
Uma lista pode ser inicializada por uma operação do
tipo list = null (sendo list o ponteiro externo)
05/11/2015
Fábio Lopes Caversan
11
Revisando o mapa conceitual
de um programa na memória
Pilha
Heap
Endereços de retorno de funções,
variáveis locais
Alocação dinâmica: listas
encadeadas
Variáveis Globais
Código do Programa
05/11/2015
Fábio Lopes Caversan
12
Ao “fotografar” a memória do
computador
Programa
Área Livre (Heap)
LIST
Ponteiro externo que aponta para o primeiro nó da lista
ligada. Cuidado com sua manipulação!
05/11/2015
Fábio Lopes Caversan
13
L
N1
N2
N3
. . . Nn null
Dois endereços merecem atenção especial:
• O endereço L do nó inicial que permite identificar em
que parte da memória inicia-se a lista
• O endereço NULL que vem após o nó final. É onde
termina a lista
Sempre lembrando, cada nó i é composto de duas
partes:
• Info: área onde é armazenado o i-ésimo elemento da
lista
• Next: área onde é armazenado o “endereço” do nó N i + 1
05/11/2015
Fábio Lopes Caversan
14
Declarando uma classe Nó para
uma lista ligada
Um dos atributos da classe precisa ser um
ponteiro para uma estrutura do mesmo tipo
public class Node {
private object info;
private Node next;
...
};
05/11/2015
Fábio Lopes Caversan
15
Permitindo o acesso aos atributos



De acordo com a linguagem, pode ser
necessária a escrita de métodos para ler e
escrever nos atributos, garantindo o
encapsulamento.
Nas linguagens que possuem propriedades,
isso pode ser feito com os comandos get e
set.
Cada vez que atribuímos um valor para a
propriedade, o set é chamado. Cada vez que
lemos um valor da propriedade, o get é
chamado.
05/11/2015
Fábio Lopes Caversan
16
public class Node {
private object info;
private Node next;
public object Info {
get {return info;}
set {info = value;}
}
public Node Next {
get {return next;}
set {next = value;}
}
...
};
05/11/2015
Fábio Lopes Caversan
17
Incluindo um elemento no início da lista
info
list
next
info next
5
3
info next
8
nulo
p
info
list
p
5
05/11/2015
info next
info next
3
8
nulo
info next
info next
3
8
6
info
list
next
5
next
Fábio Lopes Caversan
nulo
18
6
p
5
3
8
nulo
list
p
list
6
5
3
8
nulo
list
6
5
3
8
nulo
05/11/2015
Fábio Lopes Caversan
19
Os passos anteriores são
expressos pelo seguinte algoritmo
Node p = new Node();
p.Info = x;
p.Next = list;
list = p;
05/11/2015
Fábio Lopes Caversan
20
Removendo um nó do início de uma lista
info
7
list
P
list
7
X=7 P
7
next
info
next
info
next
5
9
nulo
5
9
nulo
5
9
nulo
list
P
7
5
9
nulo
5
9
nulo
5
9
nulo
list
P
7
list
list
05/11/2015
Fábio Lopes Caversan
21
Os passos anteriores para remover um
nó são expressos pelo seguinte
algoritmo
Node p = list;
list = p.Next;
x = p.Info;
05/11/2015
Fábio Lopes Caversan
22
Implementação ligada de
Pilhas



Incluir um elemento no início de uma lista
ligada é semelhante à inclusão numa pilha
O 1º nó da lista representa o topo da pilha
Vantagem: todas as pilhas ou filas usadas por
um programa podem compartilhar a mesma
lista de nós disponíveis, desde que não
ultrapassam a quantidade total de nós
disponíveis
05/11/2015
Fábio Lopes Caversan
23
Uma pilha usando lista ligada
stack
5
3
8
7
nulo
5
3
8
7
nulo
stack
6
05/11/2015
Fábio Lopes Caversan
24
Como o 1º nó da lista é o topo
da lista
A implementação de Push (x) poderia ficar:
Node p = new Node( );
p.Info = x;
p.Next = stack;
stack = p;
05/11/2015
Fábio Lopes Caversan
25
A implementação de x = pop (s)
poderia ficar :
if (Empty ())
// Exception, mensagem, etc...
else {
Node p = stack;
stack = p.Next;
x = p.Info;
p = null;
return x;
}
05/11/2015
Fábio Lopes Caversan
26
Uma fila usando lista ligada
final
início
4
1
7
9
3
final
início
4
1
05/11/2015
nulo
7
9
Fábio Lopes Caversan
3
6
nulo
27
Algoritmo para x = q.Remove ()
if (Empty())
// Exceção, mensagem, etc...
Node p = front;
x = p.Info;
front = p.Next;
if (front = = null)
rear = null;
p = null;
return ( x );
05/11/2015
A fila q consiste numa fila e dois
ponteiros: front e rear. As operações
q.Empty() e x=q.Remove() são análogas a
s.Empty(s) e x=s.Pop(s), basta substituir
front por stack.
Muita atenção ao remover o último
elemento da fila: rear fica também nulo
porque se a fila está vazia front e rear
devem ser nulos
Fábio Lopes Caversan
28
Algoritmo para q.Insert (x)
Node p = new Node();
p.Info = x;
p.Next = null;
if (rear = = null )
front = p;
else
rear.Next = p;
rear = p;
05/11/2015
Fábio Lopes Caversan
29
Desvantagens de pilhas e
filas como listas ligadas?




Mais armazenamento do que o vetor: Info e Next
Mas o espaço de armazenamento não é o dobro.
Depois, pode-se compactar as informações
Cada inclusão/exclusão corresponde a uma
inclusão/exclusão na lista de nós disponíveis
Grande vantagem: compartilhamento de nós,
desde que não ultrapasse o número de nós
disponíveis
05/11/2015
Fábio Lopes Caversan
30
Listas ligadas como estruturas de
dados





São importantes não só para implementar pilhas e
filas, mas como estruturas de dados
Acessa-se um item percorrendo-se a lista a partir do
início
Um vetor permite o acesso direto ao enésimo item
com uma única operação
Já uma lista exige n operações e é necessário
percorrer cada um dos primeiros n-1 elementos antes
do enésimo
Vantagem da lista: aparece na inserção ou remoção
de um elemento porque não é necessário nenhuma
movimentação dos n elementos
05/11/2015
Fábio Lopes Caversan
31
Inserção de um novo elemento num vetor
x0
x1
x2
x3
x4
x5
05/11/2015
x0
x1
x2
x3
x4
x5
Fábio Lopes Caversan
x0
x1
x2
x
x3
x4
x5
x6
32
Já numa lista o trabalho de inserção
independe do seu tamanho
n
list
X0
X1
X2
X3
X4 nulo
X1
X2
X3
X4 nulo
n
list
X0
InsertAfter (n,x)
X
DeleteAfter(n)
Node p = new Node()
Node p = n.Next;
p.Info = x;
x = p.Info;
p.Next = n.Next;
n.Next = p.Next;
n.Next = p
p = null;
05/11/2015
Fábio Lopes Caversan
33