next up previous contents
Next: Filas e pilhas Up: Listas ligadas Previous: Manipulação de nó   Sumário

Manipulação de lista

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 $ \models$ 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.


\begin{Program}
% latex2html id marker 1033\begin{algorithm}{isEmpty}{\textsc...
... \end{algorithm}\caption{Verificação se a lista ligada está vazia.}\end{Program}

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.


\begin{Program}
% latex2html id marker 1048
[bhtp]
\begin{algorithm}{insert}{\t...
...
\end{algorithm} \caption{Inserção de nó no topo da lista ligada.}\end{Program}

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.


\begin{Program}
% latex2html id marker 1062\begin{algorithm}{append}{\textsc{...
... \end{algorithm} \caption{Inserção de nó no final da lista ligada.}\end{Program}

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.


\begin{Program}
% latex2html id marker 1079\begin{algorithm}{removeFirst}{\te...
... \end{algorithm} \caption{Retirada do primeiro nó da lista ligada.}\end{Program}

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.


\begin{Program}
% latex2html id marker 1094\begin{algorithm}{removeLast}{\tex...
...r
\end{algorithm} \caption{Retirada do último nó da lista ligada.}\end{Program}

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.


\begin{Program}
% latex2html id marker 1111\begin{algorithm}{find}{\textsc{Lis...
...rithm}\caption{Busca de nó com chave especificada em lista ligada.}\end{Program}

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().


next up previous contents
Next: Filas e pilhas Up: Listas ligadas Previous: Manipulação de nó   Sumário
Ivan L. M. Ricarte 2003-02-14