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 Nó. 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.
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.
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.
Nas aulas seguintes vermos em detalhes como implementar cada uma destas aulas. Não perca!
