Listas encadeadas
Em C, uma lista encadeada (lista ligada ou linked list) é composta por um conjunto de estruturas (struct
) ligadas por ponteiros, de forma a construir uma sequência de valores de tamanho variável e que pode ser facilmente alterada.
Listas encadeadas são estruturas dinâmicas muito utilizadas em programação, por sua flexibilidade e escalabilidade. Elas são frequentemente usadas na construção de TADs como pilhas, filas e listas, por exemplo.
Algumas das principais operações efetuadas sobre uma lista encadeada são:
- criar/destruir uma lista
- inserir nodo
- no início
- no fim
- no meio
- remover nodo
- do início
- do fim
- do meio
- percorrer a lista (para imprimir, contar, procurar, etc)
- do início ao fim
- do fim ao início
Esta página apresenta algumas das listas encadeadas mais usadas. Cada uma delas tem características próprias e formas distintas de implementar as operações acima definidas.
Lista simples
struct nodo_t { int valor ; // valor armazenado struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo struct nodo_t *ultimo ; // último nodo int num ; // numero de elementos } ;
Lista simples reversa
struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior } ; struct pilha_t { struct nodo_t *base ; // primeiro nodo struct nodo_t *topo ; // último nodo int num ; // numero de elementos } ;
Lista dupla
struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo struct nodo_t *ultimo ; // último nodo int num ; // numero de elementos } ;
Lista simples circular
struct nodo_t { int valor ; // valor armazenado struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo struct nodo_t *ultimo ; // último nodo int num ; // numero de elementos } ;
Lista dupla circular
struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior struct nodo_t *prox ; // próximo nodo } ; struct fila_t { struct nodo_t *primeiro ; // primeiro nodo int num ; // numero de elementos } ;
Listas "sem cabeça"
A implementação de listas também pode ser feita usando somente estruturas do tipo nodo_t
, sem uma estrutura para a cabeça da lista. É uma implementação mais simples, porém menos flexível.
struct nodo_t { int valor ; // valor armazenado struct nodo_t *ant ; // nodo anterior struct nodo_t *prox ; // próximo nodo } ; struct nodo_t *primeiro ; // início da lista
Exercícios
- Esta página do prof. Paulo Feofiloff (IME/USP) tem uma ótima apresentação de listas encadeadas, com muitos exercícios.