aula 242

Lista encadeada, lista duplamente encadeada e lista circular

Dando continuidade ao nosso Curso de Programação C e ao estudo das estruturas de dados dinâmicas, vamos aprender nesta aula sobre a estrutura lista encadeada, lista duplamente encadeada e lista circular.

O que é uma lista encadeada?

Uma Lista, também chamada de Lista Encadeada ou ainda Lista Simplesmente Encadeada, é uma sequência de elementos encadeados, um após o outro.

Após esta definição talvez você esteja se perguntando: mas então qual a diferença da lista para as outras estruturas que já estudamos?

Qual a diferença entre uma lista, uma fila e uma pilha?

A forma de construir e conectar as estruturas são muito semelhantes. A diferença está na forma como manipulamos cada estrutura, ou ainda, nas operações que realizamos em cada estrutura.

Em uma pilha toda inserção e remoção é feita no topo. Em uma fila as inserções sempre são feitas no final da fila (exceto em uma fila de prioridades) enquanto a remoção sempre é feita no início da fila.

Uma lista encadeada é uma estrutura mais livre, sem muita regra. Uma inserção pode ser feita no início, no meio, no final, em qualquer parte da lista. Inclusive a inserção pode ser ordenada de forma crescente ou decrescente. Assim como uma remoção. Para ser uma lista basta uma sequência de nós encadeados.

Diferentemente das estruturas pilhas e filas, outra operação muito comum nas listas encadeadas é a operação de busca, descobrir se um determinado elemento está na lista.

Como construir uma lista encadeada?

Assim como nas estruturas anteriores, a construção de uma lista também se dá por meio da definição de uma estrutura normalmente chamada de . Cada Nó possui ao menos um ponteiro utilizado para “apontar para o Nó seguinte”. Também podemos definir a estrutura Lista que possuirá dentre seus elementos um ponteiro para o primeiro Nó da lista.

Existe uma grande diversidade de listas. A mais comum é a lista encadeada ou lista simplesmente encadeada. Esta lista possui um Nó inicial e a partir dele é possível percorrer toda a lista até o final, apenas nesta direção, do início para o fim.

lista simplesmente encadeada
Representação visual de uma Lista Simplesmente Encadeada.

Também existe a lista duplamente encadeada. Nesta lista cada Nó possui dois ponteiros, um para o Nó seguinte e um para o Nó anterior. Assim, é possível percorrer a lista nos dois sentidos, do início para o fim e vice versa.

lista duplamente encadeada
Representação visual de uma Lista Duplamente Encadeada.

Por fim, existe também a lista circular, que pode ser simplesmente ou duplamente encadeada. Na lista circular, como o nome sugere, o último Nó da lista aponta novamente para o início, o primeiro Nó da lista. Neste caso é preciso ter atenção ao percorrer a lista para não entrar em loop infinito.

lista circular
Representação visual de uma Lista Simplesmente Encadeada Circular.

Nas aulas seguintes vermos em detalhes como implementar cada uma destas aulas. Não perca!

Deixe um comentário

vinte − dezenove =

Wagner Gaspar

Capixaba de São Gabriel da Palha, Espírito Santo. Bacharel em Ciência da Computação pela Universidade Federal do Amazonas e mestre em informática pela Universidade Federal do Espírito Santo.