Listas duplamente
encadeadas
Prof. Rosana Palazon
1
Listas simplesmente encadeadas
Caracterizam-se pelo simples
encadeamento entre os seus elementos.
Não permitem o percurso reverso da lista.
Devido ao simples encadeamento, não
adianta nada conhecermos o ponteiro do
elemento a ser retirado, pois, de qualquer
modo, teremos que percorrer a lista a
procura do seu antecessor.
2
Listas duplamente encadeadas
Cada elemento da lista tem um ponteiro
tanto para o seu próximo como para o seu
anterior.
Assim, dado um elemento, podemos
encontrar com facilidade os elementos
que lhe são adjacentes.
Se tivermos um ponteiro para o ultimo
elemento da lista, poderemos facilmente
percorrê-la em ordem inversa.
3
Listas duplamente encadeadas
Consideremos:
typedef struct lista2{
int info;
struct lista2 *ant;
struct lista2 *prox;
}Lista2; //definição da lista
Lista2 *l; //ponteiro que deve
receber o endereço da lista
4
Listas duplamente encadeadas (criação)
Função de criação:
/* retorna uma lista duplavazia */
Lista2 * lista_cria()
{
return NULL;
}
5
Listas encadeadas (inserção)
Função de inserção:
/* insere o novo dado no início da lista e retorna a
lista atualizada*/
Lista2* lista_insere( Lista2* l, int dado)
{
Lista2 *novo= (Lista2*) malloc (sizeof(Lista2));
novo->info=dado;
novo->prox=l;
novo->ant=NULL;
//verifica se a lista não esta vazia
if(l!= NULL)
l->ant=novo;
return novo;
6
}
Listas duplamente encadeadas (exibição)
Função de exibição:
/* percorre a lista do inicio até o fim
mostrando os elementos*/
void lista_exibe(Lista2* l)
{
Lista2 *aux;/*variável usada para percorrer
a lista */
printf("\n\nLista\n\n");
for(aux=l;aux!=NULL;aux=aux->prox)
printf("%d\t", aux->info);
}
7
Lista duplamente encadeada (main)
 Como seria o trecho do main correspondente à
criação e inserção de valores na lista?
int main()
{
Lista2 *l; //declara uma lista não inicializada
l=lista_cria(); //inicializa a lista
l=lista_insere(l,10); //insere o elemento 10
l=lista_insere(l,20); //insere o elemento 20
l=lista_insere(l,30); //insere o elemento 30
lista_exibe(l); //mostra o conteúdo da lista
printf("\n\n");
system("pause");
return 0;
}
8
Listas encadeadas (lista vazia)
Função de verificação de lista vazia:
/* retorna 1 se vazia ou zero se
falso*/
int lista_vazia(Lista2* l)
{
return(l==NULL);
}
9
Listas encadeadas (busca)
 Função de busca de um elemento na lista:
/* retorna o elemento ou NULL se não achou*/
Lista2* lista_busca(Lista2* l, int dado)
{
//variável usada para percorrer a lista
Lista2 *a;
for(a=l;a!=NULL;a=a->prox)
{
if(a->info == dado) return a;
}
return NULL;
}
10
Listas duplamente encadeadas
(remoção)
Para a retirada de um elemento da lista
usamos a função de busca, e de posse
do ponteiro do elemento a ser removido
religamos os elos:
11
Listas encadeadas (remoção)
 Função que retira um elemento da lista:
/* retorna o elemento ou a lista original*/
Lista2* lista_retira(Lista2* l, int dado)
{
//procura o elemento na lista usando a função busca
Lista2* aux=lista_busca(l, dado);
if (aux==NULL) //não achou o elemento
return l;
//retira o elemento encadeado
if(l==aux) {//verifica se é o primeiro da lista
l=aux->prox;
l->ant=NULL;}
else
aux->ant->prox=aux->prox;
//testa para ver se é o ultimo da lista
if (aux->prox!=NULL)
aux->prox->ant=aux->ant;
free(aux);
12
return l;
}
Lista duplamente encadeada
Exercício
 Criar uma lista duplamente encadeada contendo:
nome e telefone
 Implementar as seguintes funções em um menu:
 Inserir os elementos de forma ordenada (nome), sem
repetição
 Mostrar o próximo a partir de um elemento
(se chegar ao fim da lista, recomece)
 Mostrar o anterior a partir de um elemento
(se chegar ao inicio da lista, recomece)
 Exibir os elementos em ordem crescente ou decrescente
 Localizar um telefone a partir de um nome
13