Lista Encadeada.

Como prometido vamos falar sobre lista encadeada, a principio vamos adotar o pascal, falando um pouco

sobre lista simplesmente encadeada, pense que um array é uma estrutura de dados que é tipada e possui o tamanho limitado ao que definimos no corpo do programa é já era, mas e se for necessário um vetor maior no tempo de execução e claro se for necessário poupar memoria ?, daí entra nossa lista simplesmente encadeada, essa se trata de uma estrutura de dados similar a um vetor a diferença se dá no conceito de alocação dinâmica de cada registro, tornado um vetor de tamanho indeterminado ou seja se desejo um elemento o minha lista terá um elemento mas se necessário n elementos a lista terá n elementos o quanto a memoria poder suportar.

Lista Encadeada

---

Definição: Uma lista encadeada é uma coleção de registros em que cada registro tem um campo que indica a localização do registro seguinte na lista.
Assim, a ordenação é fornecida explicitamente por esse campo. Esquematicamente podemos representar uma lista ligada da seguinte forma:

Onde o registro que representa cada componente da lista possui um campo que aponta para o próximo registro numa certa seqüência de ordenação.
Cabeça: Primeiro registro (elemento) da lista.
Cauda: Último elemento da lista. Para indicar que não ha elementos após a cauda, atribui-se nil ao apontador para o próximo, já que não existe um próximo.
A principal vantagem das listas encadeadas sobre as listas seqüenciais é que as primeiras podem aumentar e reduzir de tamanho dinamicamente, podendo assim ser usadas em diversas situações sem comprometer o uso de memória.
A principal desvantagem das listas encadeadas é a necessidade de armazenamento adicional para guardar os apontadores.
Para ver uma implementação de uma lista Encadeada, abra a unit LstEnc e para um programa que demonstra como usá-la, veja DLstEnc.

Inserção na lista encadeada

---

Inicialmente a cabeça da lista aponta para nil, indicando que a mesma está vazia (1). Após a inserção do um Item 1 na lista, a cabeça aponta para ele, e o apontador para o próximo Item contido no Item 1 aponta para nil, já que após ele não há outros itens (2). Caso um outro elemento (Item 2) seja inserido, ele passa a ser a cabeça da lista e seu apontador para o próximo elemento da lista aponta para a antiga cabeça da lista (Item 1), como pode ser verificado em (3).


Remoção na lista encadeada

---

Quando o item a ser removido encontra-se na cabeça da lista, executamos os seguintes passos:
1) Navegamos na lista até encontrar o item a ser removido e guardamos o apontador para o próximo item (segundo) da lista.
2) Fazemos com que o apontador para a cabeça passe a apontar para o item seguinte à cabeça da lista, através do apontador obtido no passo 1.
3) Já que a cabeça já foi ajustada, executamos o dispose no item que localizava-se na cabeça da lista, liberando a memória referente ao Item removido da lista.
4) A lista passa a ter um elemento a menos e a variável dinâmica que continha o elemento apontado pela cabeça da lista foi desalocado da memória.

Quando o item a ser removido não se encontra na cabeça da lista, é necessário atualizar o apontador do item anterior. Sendo assim, usamos um apontador (PAtual) para procurar o Item a ser removido e outro (PAnterior) para guardar o Item anterior na lista encadeada. Desta forma, ao encontrar o Item (1), temos um apontador para o item anterior a ele (PAnterior) e para o próprio item (PAtual), como mostra (2). De posse destes apontadores, podemos ajustar o apontador para o próximo do item apontador por PAnterior para o endereço apontado pelo campo próximo do item apontado por PAtual. Em seguida, usamos o dispose para desalocar a variável dinâmica que guarda o item removido (3). Ao final, temos uma lista encadeada com um item a menos e com todos os apontadores ajustados.


 Fonte:http://albertocn.sytes.net/2010-2/ed1/aulas/listas_lineares.htm