Listas Encadeadas

• O Quê São Listas Encadeadas?
• Como Implementar Uma Lista Encadeada?
• Onde Listas Encadeadas São Usadas?
• Quais São As Operações Básicas de Uma Lista Encadeada?

O Quê São Listas Encadeadas?

Uma lista encadeada é uma estrutura de dados linear que suporta de forma eficiente a reorganização de seus elementos. Para isso, os elementos da lista são armazenados em células não contíguas de memória e que são encadeadas por ponteiros.

Uma analogia para essa estrutura de dados é uma lista de tarefas. Novas tarefas podem ser incluídas no início, meio ou final da lista. Igualmente, é possível que uma tarefa em qualquer uma dessas posições seja marcada como concluída.

Como Implementar Uma Lista Encadeada?

• Listas Singularmente Encadeadas - As células da lista são encadeadas em apenas um sentido, da esquerda para a direita.
• Listas Duplamente Encadeadas - As células da lista são encadeadas em ambos os sentidos, da esquerda para a direita e da direita para a esquerda.

Onde Listas Encadeadas São Usadas?

• Na implementação de uma playlist, em um reprodutor de músicas.
• Na implementação de outras estruturas de dados como Pilhas, Filas e Grafos.
• Na implementação de alocadores de memória, para manter quais blocos de memória estão em uso e quais blocos estão livres.

Quais São As Operações Básicas de Uma Lista Encadeada?

Todos os tipos de listas encadeadas suportam as seguintes operações básicas:

• comprimento() retorna o número de elementos em uma lista encadeada.
• primeiro() inspeciona o primeiro elemento de uma lista encadeada.
• ultimo() inspeciona o último elemento de uma lista encadeada.
• inserir-sucessor() insere um elemento como sucessor de outro em uma lista encadeada.
• remover-sucessor() remove o sucessor de um elemento em uma lista encadeada.

Em adicional, listas duplamente encadeadas oferecem as seguintes operações básicas:

• inserir-antecessor() insere um elemento como antecessor de outro em uma lista encadeada.
• remover-antecessor() remove o antecessor de um elemento em uma lista encadeada.