Listas Encadeadas

Listas Encadeadas
Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante.
Exemplo: lista de afazeres
1. Comprar uma lâmpada;
2. Trocar uma lâmpada queimada;
3. Procurar uma conta no quarto;
4. Pagar uma conta na internet;
5. Desligar o computador;
6. dormir;

Na lista de afazeres anterior, uma tarefa dependia da execução da tarefa anterior.

Representação por vetores
Como representar a lista anterior em um programa escrito na Linguagem C? Primeira opção: vetores ou matrizes

Primeira opção: vetores ou matrizes
Como acrescentar “ligar micro”?

Os itens da lista são armazenados em posições contíguas de memória. A lista pode ser percorrida em qualquer direção. A inserção de um novo item pode ser realizada após o último item com o custo constante. A inserção de um novo item no meio da lista requer um deslocamento de todos os itens localizados após o ponto de inserção.

Segunda opção
Na estrutura de dados dinâmica contém o ponteiro para si próprias.

Representação gráfica de um elemento a lista

Cada item em particular de uma lista pode ser chamado de elemento, nó, célula, ou item. O apontador para o início da lista também é tratada como se fosse uma célula (cabeça), para simplificar as operações sobre a lista. O símbolo / representa o ponteiro nulo (NULL), indicando o fim da lista.

Operações sobre lista encadeada
Podemos realizar algumas operações sobre uma lista encadeadas, tais como:
Inserir itens;
Retirar itens;
Buscar itens;
Para manter a lista ordenada, após realizar a alguma dessas operações, será necessário movimentar alguns ponteiros ( de 1 a 3 elementos).

Outras operações possíveis:
Criar uma lista;
Destruir uma lista;
Ordenar uma lista;
Intercalar duas listas;
Concatenar duas listas;
Dividir uma