Listas Lineares
continuando .......
1
Listas
! 
! 
relembrando: listas lineares agrupa informações
referentes aum conjunto de elementos que, de alguma
forma, se relacionam entre si
Uma lista linear ou está vazia, ou possui uma série de
elementos (a1,a2, ....., an)‫‏‬
! 
onde ai é um componente de algum conjunto S.
2
Listas Encadeadas
3
Tipo de Dados Recursivo
! 
! 
Um tipo T recursivo, possui componentes que
pertencem ao tipo
definem agregados de crescimento arbitrário
! 
! 
objetos do tipo recursivo podem ser implementados
pelo uso de ponteiros
um componente é representado por um elemento
contendo um ponteiro para o objeto
struct {
int a;
no* proximo
} no;
4
Listas Encadeadas
! 
! 
! 
podem crescer e diminuir dinamicamente
tamanho máximo não precisa ser conhecido a
priori
Provêem flexibilidade permitindo que os ítens
sejam rearrumados eficientemente
!  perda no tempo de acesso a qualquer item
arbitrário da lista
5
Listas Encadeadas
! 
É um conjunto de itens organizados, como
um array (lista sequencial)
! 
! 
A
em um array a organização é implícita (pela
posição)
em uma lista encadeada a sequência de elementos
é especificada explícitamente, onde cada elemento
contém um ponteiro para o próximo da lista.
L
I
S
T
6
Listas Encadeadas
! 
No exemplo:
! 
! 
! 
! 
um elemento é identificado por uma letra
cada elemento é representado por círculo
Cada link é representado por uma seta
Detalhes que devem ser considerados:
! 
! 
! 
todo elemento possui um ponteiro
o ponteiro do último elemento tem que especificar algum tipo
de próximo (aponta para si próprio ou NULL)‫‏‬
um ponteiro ou um elemento para o 1º da lista.
A
L
I
S
T
head
7
Listas Encadeadas
! 
algumas operações são mais eficientes do que
em lista sequencial
! 
mover um elemento com a identificação T do fim da
lista para o começo
! 
Mesmo que a lista seja muito longa, a mudança estrutural é
realizada através de 3 operações
A
L
I
S
T
head
8
Listas Encadeadas
! 
Para inserção de um novo elemento X:
! 
! 
! 
aloca-se memória para um elemento e atualiza-se os
ponteiros
em lista sequencial seria necessário deslocar todos os
elementos a partir do ponto de inserção;
apenas 2 links são alterados para esta operação não importa quão longa é a lista
X
A
L
I
S
T
head
9
Listas Encadeadas
! 
remoção de um elemento:
! 
basta alterar o ponteiro do elemento anterior ao
removido
X
A
head
! 
L
I
S
T
o conteúdo de X (no exemplo) ainda existe, mas
não é mais acessível pela lista
10
Listas Encadeadas
! 
Lista Encadeada x Sequencial
!  remoção e inserção são mais naturais na lista
encadeada
!  outras operações já não são tão naturais
! 
Encontrar o k-ésimo elemento da lista
! 
! 
! 
em uma lista sequencial - simplesmente acessar a[k]
na lista encadeada é necessário percorrer k links.
Achar um ítem antes de um dado ítem
11
Listas Encadeadas
Simplesmente encadeada - ponteiros em uma direção
Duplamente encadeada - ponteiros para duas direções
! 
um ponteiro para o próximo e um para o anterior
12
Listas Encadeadas
! 
Exemplo: Suponha uma lista simplesmente encadeada
! 
! 
! 
! 
Cada nó consiste de: 1 palavavra com 1 floating
point e outra com o ponteiro para o próximo nó
o fim da lista é marcado com um ponteiro com
NULL
É desejável descobrir se algum nó possui um
número igual a 1.0
Deve retornar Verdade se encontrar e Falso em
caso contrário
13
Listas Encadeadas
typedef struct {
float valor;
tipo_nó * proximo
} tipo_nó;
tipo_nó * head;
tipo_nó * prox;
Acha_1()‫‏‬
{ prox = head;
resultado = false;
while ( (prox != NULL) && (!
resultado)){
if (prox->valor == 1.0)‫‏‬
resultado = true;
else
prox = prox->proximo;
}
return(resultado);
}
14
Listas Encadeadas
! 
Inserção e Remoção
! 
alocação dinâmica de memória
! 
! 
malloc e free do C
Exemplo de uso:
! 
! 
Rotina que toma conta do espaço livre de memória
lista de memória livre
! 
Ao liberar memória - inserção na lista
! 
Ao alocar memória - remoção da lista
15
Listas Encadeadas - Inserção
! 
! 
seja uma lista em que cada
elemento armazena um
inteiro
inserir sempre no início
Estrutura usada
struct {
int info;
tipo_no * proximo
} tipo_no;
tipo_no * head;
head = NULL;
Protótipo da Função
Insere(int valor)‫‏‬
head
16
Listas Encadeadas - Inserção
Insere(int valor)‫‏‬
{ tipo_no * novo;
novo = malloc (sizeof(tipo_no));
if (!novo) return(false);
novo->info = valor;
novo->prox = head->prox;
head->prox = novo;
return(true);
}
17
Listas Encadeadas - Remoção
! 
! 
head
remover o 1º elemento, retornando o valor
armazenado
Se remover de uma lista vazia?
18
Listas Encadeadas - Remoção
remove ()‫‏‬
{ valor = INEXISTENTE;
if (head != NULL){
valor = head->valor;
pt = head;
head = head ->prox;
free (pt);
}else “lista vazia”;
return (valor);
}
19
Busca Listas Encadeadas
! 
Busca valor em uma lista encadeada onde os
elementos não seguem uma ordenação
! 
retorna o elemento que contém o valor procurado,
ou NULL, caso não encontre
head
20
Busca Listas Encadeadas
busca_encadeada (valor, ant, pt)‫‏‬
{
pt = head; ant = head;
while (pt != NULL) && ( pt->info != valor){
ant = pt;
pt = pt->prox;
}
}
head
21
Busca Listas Encadeadas
! 
caso o valor esteja na lista
! 
! 
pt aponta para o elemento que contém o valor
senão estiver na lista
! 
pt aponta para NULL, pois o campo proximo do último
elemento aponta para NULL
head
22
Listas Encadeadas - Inserção
! 
Problema: inserir um valor em uma lista
encadeada não ordenada, caso não exista
! 
como não existe ordenação, pode-se inserir no
início da lista
23
Listas Encadeadas - Inserção
Insere(valor){
pt =busca_encadeada (valor, ant, pt );
if (pt == NULL){
novo = malloc ();
novo->info = valor;
novo->prox = head;
head = novo;
}
}
24
Listas Encadeadas - Remoção
! 
Problema: remover o elemento que
armazenar um dado valor em uma lista
encadeada não ordenada, caso exista
25
Listas Encadeadas - Remoção
remove_enc(valor)‫‏‬
{
busca_encadeada ( valor, ant, pt);
if (pt != NULL){
ant->prox = pt->prox;
if (ant == pt) head = pt->prox;
free (pt);
}else “não encontrado”;
}
26
Busca em uma lista ordenada
busca_enc_ord (valor, ant, pt)‫‏‬
{
ant = head; pt = head;
while ((pt != NULL) && (pt->info < valor)){
ant = pt;
pt = pt->prox;
}
}
27
Pensar
! 
! 
Fazer um programa que:
!  Le números inteiros positivos
a) Calcular média destes números
b) Calcular mínimo e máximo destes números
c) Listar os N maiores
Sejam x e y dois polinômios. Calcule a soma de x e y
e armazene em z
28
Listas Encadeadas
Exercício
!  Fazer rotinas para inserção, remoção, e localizar
o n-ésimo elemento
!  Fazer rotina para localizar o elemento antes
daquele de valor 5, considerando uma lista
desordenada
!  Qual a melhor representação: simplesmente
ou duplamente encadeada ?
29