1.3. Listas Duplamente Ligadas

Algoritmos e Estrutura de
Dados
Nome do professor: Bruno Leonardo Andrade Silva
Aula que se refere: Listas Duplamente Ligadas
Listas Duplamente Ligadas
● Uma Lista Duplamente Ligada é uma estrutura de dados onde cada nó da lista possui três
campos:
○ um campo contendo a informação;
○ um ponteiro direcionando para o próximo elemento;
○ um ponteiro direcionando para o elemento anterior.
https://saulo.arisa.com.br/wiki/index.php/Listas_Duplamente_Encadeadas
● Oferecendo assim maior flexibilidade de navegação em comparação com listas ligadas

simples.
● Facilitam o acesso reverso sem a necessidade de percorrer a lista a partir do início.
● Acesso bidirecional eficiente.
Caso de Uso
● Uma playlist é um exemplo prático de um caso de uso para uma lista duplamente ligada.
● Com uma lista duplamente ligada, você pode navegar pela playlist tanto para frente
quanto para trás de maneira eficiente.
Estrutura de uma Lista Duplamente Ligada
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Musica {

char titulo[50];
struct Musica *anterior;

struct Musica *proximo;
} Musica;
typedef struct Playlist {

Musica *inicio;
} Playlist;
Adicionar elementos à lista duplamente ligada (final)
void inserirMusicaNoFim(Playlist *playlist, const char *titulo) {
Musica *novaMusica = (Musica *)malloc(sizeof(Musica));
strcpy(novaMusica->titulo, titulo);
novaMusica->anterior = NULL;
novaMusica->proximo = NULL;
if (playlist->inicio == NULL) {
playlist->inicio = novaMusica;
return;
}
Musica *atual = playlist->inicio;

while (atual->proximo != NULL) {
atual = atual->proximo;
}
atual->proximo = novaMusica;
novaMusica->anterior = atual;
}
Adicionar elementos à lista duplamente ligada
(posição)
void inserirMusicaPorPosicao(Playlist *playlist, int posicao, const char *titulo) {
Musica *novaMusica = (Musica *)malloc(sizeof(Musica));
strcpy(novaMusica->titulo, titulo);
Musica *pos = playlist->inicio;

for (int i = 0; i < posicao && pos != NULL; i++) {
pos = pos->proximo;
}
if (pos == NULL) {
novaMusica->anterior = NULL;
novaMusica->proximo = playlist->inicio;
if (playlist->inicio != NULL) {
playlist->inicio->anterior = novaMusica;
}
}
Adicionar elementos à lista duplamente ligada
(posição)
else {
novaMusica->anterior = pos->anterior;
novaMusica->proximo = pos;
if (pos->anterior != NULL) {
pos->anterior->proximo = novaMusica;
} else {
}
pos->anterior = novaMusica;
}
}
Remover elementos da lista duplamente ligada
void removerMusica(Playlist *playlist, int posicao) {
if (playlist->inicio == NULL) {
printf("A playlist esta vazia.\n"); return;
}
Musica *musicaRemover = playlist->inicio;

for (int i = 0; i < posicao && musicaRemover != NULL; i++) {
musicaRemover = musicaRemover->proximo;
}
if (musicaRemover == NULL) {
printf("Posicao invalida.\n"); return;
}
if (musicaRemover->anterior != NULL) {
musicaRemover->anterior->proximo = musicaRemover->proximo;
} else {
playlist->inicio = musicaRemover->proximo;
}
if (musicaRemover->proximo != NULL) {
musicaRemover->proximo->anterior = musicaRemover->anterior;
}
free(musicaRemover);
}
Imprimir lista
void imprimirPlaylist(Playlist *playlist) {
printf("\n========================== PLAYLIST ==========================\n");
Musica *atual = playlist->inicio;
int posicao = 0;
while (atual != NULL) {
printf("[%d] %s\n", posicao, atual->titulo);
posicao++;
}
printf("==============================================================\n");
}
Método principal – Parte 1
int main() {
Playlist minhaPlaylist = {NULL};
Musica *musicaAtual = NULL;
inserirMusicaNoFim(&minhaPlaylist, "Faroeste Caboclo");

inserirMusicaNoFim(&minhaPlaylist, "Pais e Filhos");
inserirMusicaNoFim(&minhaPlaylist, "Vento no Litoral");
imprimirPlaylist(&minhaPlaylist);
int opcao;
do {
printf("\nESCOLHA UMA OPCAO:\n\n");
printf("1 - Tocar Proxima\n");
printf("2 - Tocar Anterior\n");
printf("3 - Inserir Musica no Fim\n");
printf("4 - Inserir Musica no Meio\n");
printf("5 - Remover Musica\n");
printf("0 - Sair\n");
scanf("%d", &opcao);
switch (opcao) {
case 1:
if (musicaAtual == NULL) {
musicaAtual = minhaPlaylist.inicio;
} else if (musicaAtual->proximo != NULL) {
musicaAtual = musicaAtual->proximo;
} else {
printf("Nao ha proxima musica.\n");
}
if (musicaAtual != NULL) {
printf("Tocando: %s\n", musicaAtual->titulo);
}
break;
case 2:
if (musicaAtual != NULL && musicaAtual->anterior != NULL) {
musicaAtual = musicaAtual->anterior;
printf("Tocando: %s\n", musicaAtual->titulo);
} else {
printf("Nao ha musica anterior.\n");
}
break;
case 3:
{
char titulo[100];
printf("Digite o titulo da musica: ");
scanf("%s", titulo);
inserirMusicaNoFim(&minhaPlaylist, titulo);
}
break;
case 4:
{
char titulo[100];
int posicao;
printf("Digite o titulo da musica: ");
scanf("%s", titulo);
printf("Digite a posicao de insercao da musica (comecando em 0): ");
scanf("%d", &posicao);
inserirMusicaPorPosicao(&minhaPlaylist, posicao, titulo);
}
break;
case 5:
{
int posicao;
printf("Digite a posicao da musica a ser removida (comecando em 0): ");
scanf("%d", &posicao);
removerMusica(&minhaPlaylist, posicao);
}
break;
case 0:
printf("Encerrando a playlist.\n");
break;
default:
printf("Opcao invalida.\n");
}
} while (opcao != 0);
Método principal – Parte final
Musica *atual = minhaPlaylist.inicio;
while (atual != NULL) {
Musica *temp = atual;
free(temp);
}
return 0;
}
Vamos praticar?
Referências Bibliográficas
● Rovai, Kleber Ricardi. Algoritmos e estrutura de dados. Londrina : Editora e Distribuidora

Educacional S.A., 2018. 216 p.
● Harvey M. Deitel e Paul J. Deitel. Como programar em C. Pearson. 2010. 6ª Edição. 692 p.
● https://www.w3schools.com/c/
● https://www.codingame.com/playgrounds/24988/programacao-c/
● http://www.ticmania.net/tic3/rec/programacao/c/pub/indexc.html
● https://pt.wikipedia.org/wiki/Lista_ligada

1.3. Listas Duplamente Ligadas

Enviado por

Direitos autorais:

Formatos disponíveis

1.3. Listas Duplamente Ligadas

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

1.3. Listas Duplamente Ligadas

Enviado por

Direitos autorais:

Formatos disponíveis

Algoritmos e Estrutura de

● Oferecendo assim maior flexibilidade de navegação em comparação com listas ligadas

typedef struct Musica {

struct Musica *anterior;

typedef struct Playlist {

Musica *atual = playlist->inicio;

Musica *pos = playlist->inicio;

Musica *musicaRemover = playlist->inicio;

inserirMusicaNoFim(&minhaPlaylist, "Faroeste Caboclo");

● Rovai, Kleber Ricardi. Algoritmos e estrutura de dados. Londrina : Editora e Distribuidora

Você também pode gostar