Listas Encadeadas

De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar

Listas Encadeadas

Uma lista encadeada ou lista ligada é uma estrutura de dados linear e dinâmica. Cada elemento de uma lista encadeada é chamado de célula ou , e possui dois campos, um para guardar a informação e o outro para guardar o endereço do nó seguinte. O último nó da lista aponta para nulo[1].

O esquema a seguir representa uma lista ligada/encadeada:

As listas encadeadas são dinâmicas, ou seja, tem a vantagem terem seu tamanho variável. Diferente das Pilhas ou Filas implementadas a partir de vetores, as quais tem um tamanho máximo fixo, limitado pela declaração do tamanho do vetor[1].

Implementação de listas encadeadas em linguagem C

Na linguagem C, para implementar uma lista encadeada, formada por nós, utilizamos para a declaração do nó uma struct com dois campos, um para a informação e um ponteiro que aponta para o próximo nó.

Declaração de um nó de uma lista encadeada

typedef struct {
       int    conteudo;
       struct node *prox;
} node;

Observações:

  1. É conveniente tratar os nós de uma lista encadeada como um novo tipo de dados, usando typedef, e atribuir um nome a esse novo tipo (ver Estruturas em C).
  2. A declaração da estrutura usa recursividade, onde um dos campos da estrutura é do tipo da estrutura sendo declarada.


Exemplos de listas encadeadas implementadas em C

C Progressivo.net Lista completa implementada em C[2]

Outras referências
[3] [4] [5]

Exercícios

  1. Implementar uma pilha utilizando listas encadeadas.
  2. Implementar uma fila utilizando listas encadeadas.

Referências


--Evandro.cantu (discussão) 12h40min de 22 de outubro de 2014 (BRST)