Manipulação de nó

Como pode-se observar nessa figura, um nó é essencialmente uma estrutura com dois campos de interesse: info, o conteúdo do nó, e next, uma referência para o próximo nó da lista. A entrada que determina o topo da lista deve ser registrada à parte da lista. Essa informação é tipicamente mantida em um nó descritor da lista. A entrada que marca o fim da lista não precisa de indicação especial -- tipicamente, o ponteiro nulo como valor de next marca o final da lista.

Para fins de descrição dos procedimentos de uma lista ligada, considera-se aqui que o nó de uma lista é um registro com a seguinte estrutura:

NODE $\models$	info	:	ENTRY
	next	:	NODE

Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória. Neste texto, a criação e remoção de um nó estarão associadas respectivamente aos procedimentos:

CREATENODE(ENTRY e).

Aloca recursos (área de memória) para guardar a informação especificada nos argumentos. Retorna uma referência para o nó criado, do tipo NODE; e

DELETENODE(NODE n).

Libera os recursos usados pelo nó.

Estabelecer a conexão entre dois nós é uma operação simples e freqüente na manipulação de listas. Para estabelecer a ligação entre um nó já pertencente a uma lista e um novo nó, basta fazer com que o novo nó referencie no campo next o nó que anteriormente era referenciado pelo nó original -- mesmo que esse campo tenha o valor nulo. Para concluir a conexão, o nó original deve ter atualizado o campo next para referenciar o novo nó. O efeito dessa conexão é ilustrado na Figura 2.4.

Figura: Efeito da aplicação do procedimento LINKNODE.

[Antes da ligação]

[Após a ligação]

O procedimento LINKNODE, apresentado no Algoritmo 2.7, descreve como estabelecer essa ligação entre os dois nós que são passados como argumento.