Destaques

Listas Encadeadas – Operações

Postado por Alex Ferreira na categoria Cursos no dia 01-10-2010

8

Sexta-feira passada eu falei sobre a modelagem de uma Lista Encadeada e deixei para vocês a tarefa de desenvolver os algoritmos de inserção, busca e remoção. Como prometido, o post de hoje irá tratar dessas três operações e iremos analisar a complexidade temporal dos algoritmos apresentados.

Listas Encadeadas vs. Arrays

Na aula passada vimos que os arrays sofrem de um grande problema: arrays são estruturas completamente estáticas, que não mudam de tamanho nunca. Para driblarmos essa dificuldade sugerimos o uso das Listas Encadeadas, onde o tamanho varia de acordo com a necessidade. Se minha lista armazena apenas 5 itens, então que eu só aloque memória suficiente para comportar o espaço de 5 itens.

Porém, nem tudo são problemas no caso dos arrays… Embora ele não seja uma estrutura dinâmica, ele tem uma enorme vantagem: ele é alocado num espaço contíguo de memória. Por esse simples motivo ganhamos o trunfo de podermos acessar qualquer elemento do array utilizando um simples índice. Como foi observado, podemos dizer que o acesso a posição N do array é feito de forma direta, bastando apenas indicar onde eu quero ir.

Infelizmente o mesmo não ocorre com as Listas Encadeadas… O fato de termos que alocar memória somente quando necessitamos acaba resultando em uma estrutura em que cada nó fica num espaço de memória não-contiguo em relação ao próximo. Consequentemente, perdemos o acesso direto ao elemento N da LE.

E como acessamos o N-ésimo nó da LE?

Você lembra que cada nó da LE possui duas informações, sendo que uma delas é o valor e a outra é uma referência para o próximo nó? Nós podemos usar as referências para, do 1º nó, chegarmos ao último nó da LE. Veja bem… O 1º nó possui seu valor e a referência para o 2º nó, que por sua vez também possui a referência para o 3º, que por sua vez possui a referência para o 4º, que por sua vez possui a referência para o 5º, que por sua vez…

Podemos concluir então que para acessar o N-ésimo nó da Lista Encadeada, basta seguir o encadeamento até alcançarmos o nó que desejamos! Se quiséssemos chegar no último nó da lista, por exemplo, teríamos o seguinte algoritmo:

alt

Perceba que esse algoritmo leva tempo O(N) para concluir sua tarefa, onde N é a quantidade de nós da lista! Como dito anteriormente, nos arrays eu posso acessar diretamente qualquer posição dele, portanto levamos tempo O(1). Esse é o preço que pagamos por ter uma estrutura dinâmica =).

Uma vez que já sabemos como acessar um nó qualquer da Lista Encadeada podemos prosseguir com o algoritmo de inserção.

Inserção

A LE não nos oferece nenhuma restrição quanto a disposição dos nós, então podemos criar vários procedimentos diferentes para a inserção. Podemos ter, por exemplo, um procedimento para inserir no inicio da lista, outro para inserir no meio da lista e outro para inserir ao fim da lista. Poderíamos ainda criar um outro algoritmo que insere os nós de forma ordenada na lista e assim ganhar tempo para realizar outras operações (iremos falar das listas encadeadas ordenadas na próxima aula).

O algoritmo que faz a inserção de um elemento ao fim da lista:

alt

O que tentamos aqui é alocar um novo nó e, caso a alocação seja bem sucedida, inserimos o valor de x no campo valor do novo nó e inserimos nulo na referência próximo. Logo depois caminhamos até o último nó da lista e atualizamos sua referência próximo com o endereço do novo nó.

Se analisarmos o algoritmo percebemos que ele leva tempo O(N) para desempenhar seu papel. Infelizmente é impossível criar um algoritmo com a mesma finalidade que realize a inserção em tempo inferior.

De maneira análoga, para inserir um elemento no meio da lista, devemos alocar um novo nó e percorrer até a posição desejada. Após encontrada a posição, temos que fazer com que novoNo referencie o nó referenciado pelo nó anterior e logo depois fazemos com que o nó anterior passe a referenciar o novoNo. Parece confuso? Confira a ilustração do processo abaixo:

alt

Novamente temos um algoritmo com tempo O(N). Perceba que o algoritmo para a inserção no meio da lista também serve para inserir no final da lista, bastando apenas indicar que a inserção deverá ser feita no último nó.

Agora fica como exercício para você formalizar o algoritmo de inserção no meio da lista, ou seja, transcrever ele para pseudocódigo ou para a linguagem de sua preferência. Logo depois me responda se o mesmo algoritmo serve para realizar a inserção no inicio da lista e qual o tempo necessário para inserir um elemento no inicio da lista.

Busca

É uma operação bastante simples. Sua finalidade básica é informar se um elemento qualquer existe dentro da lista. Uma descrição em alto nível do algoritmo se resume em percorrer toda a lista até que seja encontrado o nó requisitado.

alt

Novamente temos uma operação que leva tempo O(N) para ser realizada.

Remoção

A remoção é uma operação bastante delicada. Se eu lhe mandar remover um elemento da Lista Encadeada você pode, num primeiro momento, pensar em percorrer o encadeamento até encontrar o nó a ser removido e simplesmente desalocar tal nó. Perceba que se você fizer isso toda a lista ficará comprometida. Lembre-se: cada nó da lista possui a referência para o próximo nó. Se você apenas realizar a desalocação, toda a sub lista que fica depois do nó removido será perdida!

Logo, a operação de remoção consiste em percorrer a lista até encontrarmos o elemento a ser removido. Ao encontrarmos o seu respectivo nó, devemos fazer com que o nó anterior passe a referenciar o nó posterior ao removido. Após ajustar as referências podemos, de fato, desalocar o nó em questão.

alt

E mais uma vez temos um algoritmo com tempo O(N)… Segue uma ilustração de uma operação de remoção:

alt

Bom gente, encerramos a aula de hoje por aqui… Na próxima aula iremos estudar uma das variações da Lista Encadeada, que são as listas ordenadas. Nela poderemos organizar de forma mais inteligente os dados, fazendo com que algumas operações se tornem mais eficientes, do ponto de vista do tempo computacional.

Recomendo fortemente que você tente inventar seus próprios algoritmos para as operações citadas aqui, pois além de fortificar o que foi aprendido, você irá melhorar a sua capacidade de desenvolvimento. É como diz um certo professor:

A tarefa nobre do desenvolvimento é a capacidade de criar algoritmos, e algoritmos eficientes! Codificar é uma tarefa que até macacos podem fazer… Basta ensinar a ele como ler as especificações e meia dúzia de comandos.

alt

Comentários (8)

Você falou que era impossível criar um algoritmo de inserção em tempo inferior ao algoritmo mostrado. No caso para inserir sempre no fim, basta usar um Ponteiro FIM que sempre aponta para o final da lista.
Realmente sua abordagem é válida. Se tivessemos uma referência para o último nó poderiamos fazer a inserção no fim em tempo constante, O(1).

Porém, todavia, contudo, não acho que seja uma boa abordagem. Uma vez que o aluno se acostuma a usar referências para tudo quanto é lugar, ele não quebra a cabeça e consequentemente ele não aprende.

Mas ainda assim é impossível criar um algoritmo que faça a inserção em tempo inferior a O(n)… O que você sugeriu foi a criação de uma nova estrutura para posteriormente criar um novo algoritmo.

Tá, mas um adjetivo é all remenber
Gostei do post, interessante, bem conceitual, mas a onda é a ordenação dos elementos.

Vou ficar aguardando a aula sobre Lista encadeada ordenada para ter uma base de como iserir um elmento no meio da lista ordenada.

tem como vc manda as inserçoes ,remoçao,e busca em C
Cara esse blogo é muito bom sinceramente acho que devem dar continuidade pra ele, achei muito interessante só tive problemas pra encontrar continuação pras aulas.. não tem na area cursos.. e aparentemente não está tendo continuidade.
Força galera
Excelente artigo!

Mas vocês poderiam ter dado continuidade à esse curso de Estrutura de Dados. Esse assunto carece de explicações boas e detalhadas que nem está aqui.

Parabéns!

adorei o conteúdo muito proveitoso, mas gostaria que ao em vez de colocar o cogido escrito colocasse também em linguagem c. acho que fica mais fácil de entender se tivermos as duas opções pois esse assunto e meio difícil, e quanto mais conteúdo tiver melhor.

Deixe um comentário