A informação sobre a estrutura de uma lista ligada está distribuída ao longo de seus nós. Assim, a única informação adicional requerida para manter a lista é a especificação de seu nó descritor:
LIST | top | : | NODE |
Na criação de uma lista, o nó descritor está inicialmente vazio, de forma que seu campo next tem o valor nulo. Assim, um procedimento para verificar se a lista está vazia deve verificar o valor desse campo. Esse procedimento está descrito no Algoritmo 2.8.
Para a inserção de um novo nó em uma lista há duas possibilidades que podem ser consideradas, dependendo da opção de se inserir o novo nó no início (antes do primeiro elemento) ou no final (após o último elemento) da lista.
A primeira dessas possibilidades está representada através do procedimento INSERT, que recebe como argumentos as referências para a lista e para o nó a ser inserido. O Algoritmo 2.9 apresenta esse procedimento.
O procedimento que acrescenta um nó ao final da lista necessita varrer a lista completamente em busca do último nó, aquele cujo campo next tem o valor nulo. Para tanto, requer a utilização de uma variável interna que indica qual nó está atualmente sendo analisado. No momento em que o campo next desse nó tiver o valor nulo, então sabe-se que o último nó da lista foi localizado. Esse procedimento, APPEND, está descrito no Algoritmo 2.10.
De forma similar, o procedimento para retirar um nó do início da lista é mais simples que aquele para retirar um nó do fim da lista, pois este requer a varredura completa da lista. Nos dois casos, o valor de retorno é uma referência ao nó retirado; a partir dessa referência, a aplicação pode determinar o que deseja fazer com o nó, se manipular a informação nele contida ou simplesmente liberar os recursos com o procedimento DELETENODE. Um valor de retorno nulo indica que a operação foi especificada sobre uma lista vazia.
O procedimento para retirar o nó do início da lista é apresentado no Algoritmo 2.11. Embora a linha 5 desse algoritmo não seja absolutamente necessária, ela garante que não há meios de acesso aos nós da lista exceto pelos procedimentos definidos. Se ela não estivesse presente, seria possível que a aplicação, ao obter o nó com a informação de endereço do seu antigo sucessor, tivesse acesso a um nó da lista de forma direta.
O procedimento para a retirada de um nó do fim da lista é descrito no Algoritmo 2.12. Da mesma forma que no procedimento de remoção do primeiro elemento da lista, a situação de manipulação de uma lista vazia deve receber tratamento especial. Como no procedimento de inserção, uma varredura de toda a lista é feita mantendo-se uma referência para o nó sob análise; adicionalmente, mantém-se uma referência para o nó anterior a este de forma a permitir a atualização da indicação do fim da lista.
Outro procedimento usual na manipulação de uma lista ligada é aquele que permite procurar o nó que satisfaz um determinado critério de busca -- por exemplo, cuja chave em seu campo de informação seja igual a um argumento fornecido. Esse procedimento de busca é apresentado através do Algoritmo 2.13, que retorna uma referência para o campo de informação do nó encontrado ou o valor nulo se não for encontrado nenhum nó que satisfaça a condição de busca.
Como se observa nesse caso, a varredura de uma lista em busca de uma dada chave é um procedimento seqüencial, similar em conceito à busca linear. Essa é a contra-partida à flexibilidade de manipulação de uma lista -- não há como realizar uma busca binária, por exemplo, nesse tipo de estrutura. Assim, o procedimento deve analisar a lista nó a nó até encontrar o elemento procurado.
Dependendo da aplicação, outros procedimentos podem ser associados à manipulação de uma lista ligada, tais como obter o número de nós na lista, SIZE(); concatenar ou combinar duas listas, CONCAT(); inserir elemento em posição específica da lista, INSERTAT(); ou remover elemento em posição específica, REMOVEAT().