Lista encadeada ou Simples

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, cada célula contém um objeto de algum tipo e o endereço da célula seguinte

É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo:

typedef struct cel celula;

Uma célula c e um ponteiro p para uma célula podem ser declarados assim:

celula c; celula *p;

Se c é uma célula então c.conteudo é o conteúdo da célula e c.prox é o endereço da próxima célula. Se p é o endereço de uma célula, então p->conteudo é o conteúdo da célula e p- >prox é o endereço da próxima célula. Se p é o endereço da última célula da lista então p-

>prox vale NULL .

Conteúdo -> prox

Lista Duplamente encadeada

Nelas, cada elemento tem um ponteiro para o próximo elemento e um ponteiro para o elemento anterior. Desta forma, dado um elemento, podemos acessar ambos os elementos adjacentes: o próximo e o anterior. Se tivermos um ponteiro para o último elemento da lista, podemos percorrer a lista em ordem inversa, bastando acessar continuamente o elemento anterior, até alcançar o primeiro elemento da lista, que não tem elemento anterior (o ponteiro do elemento anterior vale NULL).

Lista Circular

Numa lista circular, o último elemento tem como próximo o primeiro elemento da lista,formando um ciclo., neste caso, não faz sentido falarmos em primeiro ou último elemento. A lista pode ser representada por um ponteiro para um elemento inicial qualquer da lista. Para percorrer os elementos de uma lista circular, visitamos todos os elementos a partir do ponteiro do elemento inicial até alcançarmos novamente esse mesmo elemento.

Fila

Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos. Mais especificamente, uma fila (= queue) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo.

Em outras palavras, o primeiro objeto inserido na fila é também o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (= First-In-First-Out).

Pilha

A idéia fundamental da pilha é que todo o acesso a seus elementos é feito através do seu topo. Assim, quando um elemento novo é introduzido na pilha, passa a ser o elemento do topo, e o único elemento que pode ser removido da pilha é o do topo. Isto faz com que os elementos da pilha sejam retirados na ordem inversa à ordem em que foram introduzidos: o primeiro que sai é o último que entrou (a sigla LIFO – last in, first out – é usada para descrever esta estratégia).

Comentários