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.

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
} ;

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
} ;

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
} ;

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
} ;

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
} ;

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

• Esta página do prof. Paulo Feofiloff (IME/USP) tem uma ótima apresentação de listas encadeadas, com muitos exercícios.