Tecnicas De Encadeamento

6. Técnicas de Encadeamento para listas com alocação dinâmica e encadeada

As técnicas de encadeamento fornecem mecanismos para que se possa construir algoritmos mais simples e eficientes para manipular listas ligadas.

As técnicas de encadeamento mais usadas são: nó cabeçalho encadeamento circular encadeamento duplo

6.1 Nó cabeçalho

Consiste de um nó extra mantido sempre na primeira posição da lista encadeada. Este nó não é usado para armazenar um elemento da lista, tendo como único objetivo simplificar os procedimentos de inserção e remoção, veja Figura 6.1.

L

Figura 6.1
O campo de informação do nó cabeçalho fica sem uso. Este campo pode conter, por exemplo o número de nós da lista.

Com o uso de nó cabeçalho, uma lista vazia tem pelo menos um nó. Desta forma uma lista vazia passa a ter a seguinte representação, veja Figura 6.2.

L

Figura 6.2

Vejamos como esta pequena alteração pode tornar os procedimentos de inserção e remoção em listas ordenadas bem mais simples.

a) inicializar uma lista encadeada usando nó cabeçalho

inteiro Inicializar_Lista(endereço do ponteiro da lista) inicio aloca um nó; se a alocação não foi possível então a função retorna –1; atribui ao campo de ponteiro do novo nó o valor NULL; atribui ao endereço da lista o endereço do novo nó; a função retorna 1; fim; b) inserir um novo elemento em uma lista encadeada ordenada. Para fazermos a comparação vamos escrever o algoritmo sem usar nó cabeçalho e depois usando nó cabeçalho.

b1) inserção sem usar nó cabeçalho. Neste caso duas possibilidades tem que ser identificadas: inserção na cabeça da lista e inserção no meio da lista.

tipo Insere_Elem(endereço da lista, elemento) inicio aloca um novo nó; se a alocação não foi possível então a função retorna –1; insere o elemento no campo de informação do novo nó alocado; /* o elemento a ser inserido é o primeiro da lista ou a lista está vazia */ se lista é