Uma lista encadeada é uma representação de uma seqüência de objetos na memória do computador. Cada elemento da seqüência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante.
Veja o verbete Linked list na Wikipedia.
Uma lista encadeada (= linked list = lista ligada) é uma seqüência de células; cada célula contém um objeto de algum tipo e o endereço da célula seguinte. Suporemos nesta página que os objetos armazenados nas células são do tipo int. A estrutura de cada célula de uma tal lista pode ser definida assim:
struct cel {
int conteudo;
struct cel *prox;
} ;
|
|
É 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 aponta a última célula da lista então
p->prox vale NULL.
O endereço de uma lista encadeada é o endereço de sua primeira célula. Se p é o endereço de uma lista, convém, às vezes, dizer simplesmente
"p é uma lista".
Listas são animais eminentemente recursivos. Para tornar isso evidente, basta fazer a seguinte observação: se p é uma lista então vale uma das seguintes alternativas:
Uma lista encadeada pode ser organizada de duas maneiras diferentes, um óbvia e outra menos óbvia.
celula c, *ini; c.prox = NULL; ini = &c; | ou |
celula *ini; ini = malloc (sizeof (celula)); ini->prox = NULL; |
celula *ini; ini = NULL;
Suporemos no que segue que nossas listas têm cabeça. O caso de listas sem cabeça será tratado nos exercícios. Eu prefiro listas sem cabeça (porque são mais "puras"), mas a vida do programador fica mais fácil quanto a lista tem cabeça.
Eis como se imprime o conteúdo de uma lista encadeada com cabeça:
// Imprime o conteúdo de uma lista encadeada
// com cabeça. O endereço da primeira célula é ini.
void imprima (celula *ini)
{
celula *p;
for (p = ini->prox; p != NULL; p = p->prox)
printf ("%d\n", p->conteudo);
}
Eis a correspondente função para lista sem cabeça:
// Imprime o conteúdo de uma lista encadeada ini.
// A lista não tem cabeça.
void imprima (celula *ini)
{
celula *p;
for (p = ini; p != NULL; p = p->prox)
printf ("%d\n", p->conteudo);
}
Veja como é fácil verificar se um inteiro x pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista:
// Esta função recebe um inteiro x e uma lista
// encadeada de inteiros. O endereço da lista é
// ini e ela tem uma celula-cabeça. A função
// devolve o endereço de uma celula que contém x.
// Se tal celula não existe, a função devolve NULL.
celula *busca (int x, celula *ini)
{
celula *p;
p = ini->prox;
while (p != NULL && p->conteudo != x)
p = p->prox;
return p;
}
Que beleza! Nada de variáveis booleanas! A função se comporta bem até mesmo quando a lista está vazia.
Eis uma versão recursiva da mesma função:
celula *busca2 (int x, celula *ini)
{
if (ini->prox == NULL)
return NULL;
if (ini->prox->conteudo == x)
return ini->prox;
return busca2 (x, ini->prox);
}
celula *busca (int x, celula *ini) {
int achou;
celula *p;
achou = 0;
p = ini->prox;
while (p != NULL && !achou) {
if (p->conteudo == x) achou = 1;
p = p->prox; }
if (achou) return p;
else return NULL; }
Quero inserir (= insert) uma nova célula com conteúdo x entre a posição apontada por p e a posição seguinte [por que seguinte e não anterior?] em uma lista encadeada. É claro que isso só faz sentido se p é diferente de NULL.
// Esta função insere uma nova celula em uma
// lista encadeada. A nova celula tem conteudo
// x e é inserida entre a celula apontada por
// p e a seguinte. Supõe-se de p != NULL.
void insere (int x, celula *p)
{
celula *nova;
nova = mallocX (sizeof (celula));
nova->conteudo = x;
nova->prox = p->prox;
p->prox = nova;
}
Veja que maravilha! Não é preciso movimentar células para "criar espaço" para um nova célula, como fizemos para inserir um elemento de um vetor. Basta mudar os valores de alguns ponteiros.
Observe também que a função se comporta corretamente mesmo quando quero inserir no fim da lista, isto é, quando p->prox == NULL. Se a lista tem cabeça, a função pode ser usada para inserir no início da lista: basta que p aponte para a célula-cabeça. Infelizmente, a função não é capaz de inserir antes da primeira célula de uma lista sem cabeça.
O tempo que a função consome não depende do ponto da lista onde quero fazer a inserção: tanto faz inserir uma nova célula na parte inicial da lista quanto na parte final. Isso é bem diferente do que ocorre com a inserção em um vetor.
void insere (int x, celula *p) {
celula nova;
nova.conteudo = x;
nova.prox = p->prox;
p->prox = &nova; }
Suponha que quero remover (= to remove = to delete) uma certa célula da lista. Como posso especificar a célula em questão? A idéia mais óbvia é apontar para a célula que quero remover. Mas é fácil perceber que essa idéia não é boa. É melhor apontar para a célula anterior à que quero remover. Infelizmente, isso traz uma nova dificuldade: não há como pedir a remoção da primeira célula. Portanto, vamos nos limitar às listas com cabeça.
Vamos supor que p é o endereço de uma célula de uma lista com cabeça e que desejo remover a célula apontada por p->prox. (Note que a função de remoção não precisa saber onde a lista começa.)
// Esta função recebe o endereço p de uma celula
// de uma lista encadeada. A função remove da
// lista a celula p->prox. A função supõe que
// p != NULL e p->prox != NULL.
void remove (celula *p)
{
celula *morta;
morta = p->prox;
p->prox = morta->prox;
free (morta);
}
Veja que maravilha! Não é preciso copiar informações de um lugar para outro, como fizemos para remover um elemento de um vetor: basta mudar o valor de um ponteiro. A função consome sempre o mesmo tempo, quer a célula a ser removida esteja perto do início da lista quer esteja perto do fim.
void remove (celula *p, celula *ini) {
celula *morta;
morta = p->prox;
if (morta->prox == NULL) p->prox = NULL;
else p->prox = morta->prox;
free (morta); }
A partir de agora, tudo é festa: você pode inventar uma grande variedade de tipos de listas encadeadas. Por exemplo, você pode fazer uma lista encadeada circular: a última célula aponta para a primeira e não para NULL. A lista pode ou não ter uma célula-cabeça (você decide). Para especificar uma lista circular, basta fornecer um endereço (por exemplo, o endereço da última célula).
Outro tipo útil é a lista duplamente encadeada: cada célula contém o endereço da célula anterior e o da célula seguinte. A lista pode ou não ter uma célula-cabeça (você decide). A lista pode até ter uma célula-rabo se você achar isso útil! Uma tal lista pode ser especificada por dois endereços: o da primeira célula e o da última.
Pense nas seguintes questões, apropriadas para qualquer tipo de lista encadeada. Em que condições a lista está vazia? Como remover a célula apontada por p? Idem para a célula seguinte à apontada por p? Idem para a célula anterior à apontada por p? Como inserir uma nova célula entre o elemento apontado por p e o seu antecessor? Idem entre p e seu sucessor?
Suponha que ini é o endereço de uma lista encadeada com cabeça. Nosso problema: Dado um inteiro y, remover da lista a primeira célula que contém y (se tal célula não existe, não é preciso fazer nada).
// Esta função recebe uma lista encadeada ini,
// com cabeça, e remove da lista a primeira
// celula que contiver y, se tal celula existir.
void buscaEremove (int y, celula *ini)
{
celula *p, *q;
p = ini;
q = ini->prox;
while (q != NULL && q->conteudo != y) {
p = q;
q = q->prox;
}
if (q != NULL) {
p->prox = q->prox;
free (q);
}
}
Invariante: no início de cada iteração (imediatamente antes da comparação de q com NULL), temos
q == p->prox ,
ou seja, q está sempre um passo à frente de p.
Mais uma vez, suponha que tenho uma lista encadeada ini, com cabeça. (É óbvio que ini é diferente de NULL.) Nosso problema: Inserir na lista uma nova célula com conteúdo x imediatamente antes da primeira célula que tiver conteúdo y ; se tal célula não existe, inserir x no fim da lista.
// Esta função recebe uma lista encadeada ini,
// com cabeça, e insere na lista uma nova celula
// imediatamente antes da primeira que contiver y.
// Se nenhuma celula contém y, insere a nova
// celula no fim da lista. O conteudo da nova
// celula é x.
void buscaEinsere (int x, int y, celula *ini)
{
celula *p, *q, *nova;
nova = mallocX (sizeof (celula));
nova->conteudo = x;
p = ini;
q = ini->prox;
while (q != NULL && q->conteudo != y) {
p = q;
q = q->prox;
}
nova->prox = q;
p->prox = nova;
}
