fbpx

LISTA ENCADEADA - LISTA DUPLAMENTE ENCADEADA - PILHA - FILA

“ Uma Lista Ligada, também conhecida como Lista Encadeada, é um conjunto de dados dispostos por uma sequência de nós, cuja relação de sucessão desses elementos é determinada por um ponteiro que indica a posição do próximo elemento, podendo estar ordenado ou não (Silva, 2007).”

Diferente de vetores onde se aloca a memória de forma sequencial, exigindo um espaço único na memória do tamanho do vetor, a lista encadeada consegue através de nós, utilizar espaços espalhados pela memória, fazendo muito mais eficiente a ocupação da memória.

Porém para conseguir esse tipo de desempenho é necessário o consumo maior de memória, pois é necessário utilizar um ponteiro para guardar o endereço da próxima informação da sequência. 

Um exemplo para ilustrar esse procedimento podemos imaginar que a memória seja uma cidade, a informação completa, no caso a lista seja o CEP e o ponteiro para direcionar a sequência das partes das informações sejam os números das casas e cada caractere da informação, no caso os dados, sejam as casas. 

Caso queira acompanhar as explicações com um código na prática, pode acessar meu GitHub  em meu repositório, ou ir diretamente no meu código ListaEncadeada.cpp onde se tem todas as opções de inserção e remoção dos nós.

COMO FUNCIONA NA PRÁTICA A LISTA ENCADEADA

Definiremos os passos a seguir em vários casos que possam existir para o desenvolvimento de uma lista encadeada.

CRIAÇÃO DE UMA LISTA ENCADEADA

lista encadeada

1º PASSO – Deve se trabalhar com as duas bibliotecas stdio.h ( utilizará printf/scanf ) e a stdlib.h ( utilizará alocador de memória malloc );

2º PASSO – Definir a estrutura da informação a ser alocada, para ter o conhecimento do tamanho de espaço a ser reservado na memória, onde o tamanho do ponteiro é o mesmo da  informação, isto é se uma informação é tipo string o tamanho do ponteiro será do tipo string também, criando um nó com ponteiro com endereçamento do nó anterior e o dado inserido;

3º PASSO – Deve se verificar se existe espaço na memória para alocar a informação junto com seu ponteiro, tornando assim um ponteiro indicando um endereço, levando a duas situações:

Situação 1: Caso exista o espaço necessário para a informação, é criado um ponteiro e um espaço vazio que o ponteiro endereça, então inicia a lista com o ponteiro indicando NULL.

lista encadeada

Situação 2: Caso não exista o espaço a lista não é criada, é indicado ter uma mensagem avisando o usuário que não há espaço necessário para a criação de uma lista.

lista encadeada

ADIÇÃO DE INFORMAÇÕES NA LISTA ENCADEADA

Tendo a lista criada, para adicionar uma informação é simples, basta reservar um outro espaço na memória e seu ponteiro estar indicando o endereço do último dado da lista.

Os passos são os mesmos de uma criação, com a diferença de o ponteiro já ter um direcionamento pré-definido, assim podemos adicionar um novo dado na memória.

lista encadeada

Havendo memória para a adição, como vimos no 3º PASSO da criação de uma lista, deve-se criar um ponteiro cujo a informação contida nele é o endereço do último dado registrado.

Como na figura acima mostra a criação de um ponteiro com a informação já pré-estabelecida do dado 3, e reservado o espaço para ser inserido o dado, que será o 4, pela lista ser sequencial.

REMOÇÃO DOS DADOS DE UMA LISTA ENCADEADA

Para remover os dados de uma lista encadeada, existem duas situações: remover um dado no final da lista e remover um dado no meio ou início da lista. Primeira parte é saber se a lista está vazia, caso esteja, retornar a mensagem que a lista está vazia. Sabendo qual dado deseja remover, podemos analisar as duas formas.

Caso o dado esteja no final da lista, é simples, basta apagar o último registro da lista, tanto o ponteiro quanto o dado, liberando o espaço na memória e deixando o dado anterior como o último, obrigando assim ser o endereço para o próximo ponteiro apontar quando for registrado um novo dado.

lista encadeada

Agora para remover um dado no meio ou no início da lista, exige mais cuidados e procedimentos, onde utilizarei passos para organizar melhor os procedimentos.

1º PASSO – Localizando o dado a ser removido, se cria um novo nó auxiliar, externo da lista apenas para guardar o endereço que o ponteiro do dado a ser excluído para ser usado posteriormente;

lista encadeada

2º PASSO – Com o endereço guardado no nó auxiliar, é feita a exclusão e a limpeza do espaço da memória ocupado por ele.

lista encadeada

3º PASSO – É feito a atribuição do valor guardado no auxiliar, no ponteiro do dado seguinte, fazendo com que a lista volte a ser interligada de forma sequencial, sem espaços vazios no meio da lista.

lista encadeada

4º PASSO – Apagar o nó auxiliar, para não haver consumo de memória desnecessário.

lista encadeada

Caso tenha notado a lista é sequencial, porém por não ser um vetor, não precisa estar fisicamente sequencialmente e sim interligadas sequencialmente, como na figura acima, pode se ver um nó vazio entre os nós ocupados, porém se você seguir os nós, ele acompanha a sequência de criação dos dados.

LISTA DUPLAMENTE ENCADEADA

A lista duplamente encadeada tem a mesma finalidade da lista encadeada, porém ela tem funcionalidades a mais, que é a movimentação do início para o fim, como é na lista encadeada mas também pode se movimentar do final para o início, fazendo com que ela possa ser muito mais dinâmica.

O ponto negativo comparado com a lista encadeada é que a lista duplamente encadeada ocupa mais espaço na memória, pois ela necessita de um ponteiro a mais para cada dado inserido, que é o ponteiro que indica o endereço do próximo dado, diferente da encadeada que necessita apenas do ponteiro com endereço do nó anterior apenas.

Vamos pontuar as diferenças que a lista duplamente encadeada tem referente a encadeada, para não ficar uma explicação repetitiva.

As bibliotecas continuam as mesmas, o que vai mudar é na criação da estrutura do nó, deve se adicionar um ponteiro a mais, para endereçar o próximo nó.

CRIAÇÃO DE UMA LISTA DUPLAMENTE ENCADEADA

Para a criação da lista deve se verificar se tem espaço suficiente para criar, caso tenha, já faz a reserva na memória criando um ponteiro apontando para NULL, no anterior e NULL para o próximo, mostrando assim que é uma lista vazia e criada, em caso de não haver espaço em memória, por boas práticas deve se enviar uma mensagem para o usuário informando que não há memória suficiente.

lista duplamente encadeada

ADIÇÃO DE INFORMAÇÕES NO INÍCIO DE UMA LISTA DUPLAMENTE ENCADEADA

Recebendo o dado a ser inserido, aso a lista esteja vazia, o primeiro ponteiro indicando o próximo no cabeçalho da lista é adicionado a informação do endereçamento do novo nó, e se mantém o ponteiro do novo nó direcionando para o próximo como NULL.

Caso a lista não esteja vazia, deve-se criar um nó temporário, para auxiliar na busca de onde será inserido esse dado.

lista duplamente encadeada

Inserindo no início da lista, podemos organizar por passos:

1º PASSO – Se cria um nó auxiliar onde guarda a informação do ponteiro que indica próximo nó no cabeçalho da lista, e seus dados,  que no caso é a indicação do primeiro nó da lista e no ponteiro que indica o anterior se coloca o endereço do novo nó criado;

lista duplamente encadeada

2º PASSO – Logo após encontrar o ponteiro que indica o nó anterior tendo o valor NULL, é caracterizado o início da lista, assim é adicionado o novo dado e o ponteiro indicando para o ponteiro próximo do auxiliar;

3º PASSO – O nó auxiliar deixa de ser um nó temporário e se torna um nó indicado pelo primeiro nó da lista, concluindo assim a inserção de um novo nó no início da lista.

lista duplamente encadeada

Lembrando que a lista encadeada ou a duplamente encadeada, não são lineares e sim sequenciais, sendo assim o que vale é o direcionamento dos ponteiros e não a posição do nó na memória.

ADIÇÃO DE INFORMAÇÕES NO FIM DE UMA LISTA DUPLAMENTE ENCADEADA

Já essa opção é a mais simples, pois segue o mesmo padrão da lista encadeada, onde se cria o nó temporário auxiliar para guardar o novo dado a ser registrado, logo após ser verificada a existência da lista.

Então se cria o nó auxiliar com os ponteiros e dados da nova informação a ser inserida e inicia uma busca do início da lista até encontrar um ponteiro que indica o próximo nó com valor NULL.

lista duplamente encadeada

Assim é nesse ponteiro próximo indicando NULL, é atribuído o endereçamento do ponteiro que indica o endereçamento do nó anterior do novo nó criado, e o ponteiro do novo nó aponte para NULL, se tornando o último nó da lista.

lista duplamente encadeada

ADIÇÃO DE INFORMAÇÃO NO MEIO DA LISTA DUPLAMENTE ENCADEADA

Se utiliza o mesmo procedimento que usamos nos dois casos acima, tendo o local que deve ser colocada a informação na sequência da lista deve ser feita a análise do local, caso existente inicia o procedimento.

Podemos criar alguns passos para essa função:

1º PASSO – Cria um nó auxiliar onde seu ponteiro que indica o anterior, será o mesmo do ponteiro do local indicado, e o seu ponteiro indicado próximo terá o endereçamento do nó atual do local escolhido;

lista duplamente encadeada

2º PASSO – Assim é atribuído um novo valor para o ponteiro do anterior do local indicado para o endereçamento do novo nó auxiliar, fazendo com que deixe de ser auxiliar e se torne o novo nó adicionado no local indicado.

lista duplamente encadeada

REMOÇÃO DOS DADOS DE UMA LISTA DUPLAMENTE ENCADEADA

No caso de remoção de nó da lista encadeada é feito a verificação se a lista está vazia, analisando se os ponteiros do nó inicial estão direcionando para o NULL, caso esteja vazia, convém disparar uma mensagem de que a lista está vazia para o usuário.

Caso não esteja vazia e sabendo de qual dado será excluído, fazendo uma busca desde o primeiro nó até encontrar o dado a ser excluído e apagar o dado depois de atribuir novos valores para os ponteiros do nó anterior e do próximo.

Funciona da seguinte forma: se cria um um nó auxiliar para armazenar o dado inserido para a remoção, para iniciar na lista, seu ponteiro anterior será atribuído o valor inicial da lista, e seu ponteiro próximo será atribuído o mesmo valor do ponteiro próximo do primeiro nó da lista.

Fazendo assim uma busca, caso o dado a ser removido esteja no primeiro nó da lista, ele passa para o próximo passo para a remoção.

Caso não seja, é feito a atribuição de novos valores, onde o ponteiro anterior do nó auxiliar passa a ter o valor de seu ponteiro próximo ( o primeiro nó da lista) e seu ponteiro que endereça o seu próximo nó, terá o valor do endereço de seu próximo nó, fazendo assim uma forma de escada, subindo degrau por degrau.

lista duplamente encadeada
lista duplamente encadeada

Quando chegar no nó que está o valor escolhido a ser removido, é feito outro processo. É feita uma nova atribuição de valores no ponteiro do nó anterior, terá o valor editado para o valor do ponteiro próximo do nó auxiliar, fazendo com que a sequência da lista pule o valor selecionado para ser removido da lista. E por fim apague o nó auxiliar para não ocupar a memória.

lista duplamente encadeada

Também é interessante apagar o nó removido da lista, após ter sido retirado da lista, porém está na memória ainda, necessitando ser removido, como boas práticas.

lista duplamente encadeada

PILHA

É um sistema onde se adiciona uma sequência de dados de forma simples e econômica, porém com limitações, pois ela só consegue inserir dados de uma única forma de entrada e saída, isto é, só se adiciona um dado no fim da pilha e só pode ser removido, também do fim da pilha.

Esse processo é conhecido como FILO (First in Last out), traduzindo, o primeiro dado a entrar é o último a sair.

pilha

Na prática, para utilizar a pilha, basta criar qual será o tipo de dado a ser armazenado juntamente com seu nome, podendo então trabalhar sempre com o último dado da pilha, tanto para adicionar algum dado após ele, ou removê-lo.

Suas funções são:

  • Criar uma pilha vazia;
  • Inserir um dado no topo;
  • Remover o dado do topo;
  • Verificar se a pilha está vazia;
  • Remover a estrutura de pilha.

Um exemplo fácil de se imaginar o funcionamento de uma pilha é um caminhão cegonha, transportando carros, onde tanto a entrada quanto a saída é uma só.

pilha

FILA

Também uma forma simples e econômica de se tratar, com limitações como na pilha, porém com diferença de só se pode adicionar um dado no final, e para remover apenas pelo primeiro elemento inserido.

Transformando assim um sistema de FIFO ( First in, first out), traduzindo fica primeiro que entra é o primeiro que sai.

O tratamento da fila na prática parecido com a pilha, se cria uma fila, indicando o tipo do dado e o nome, e assim se adiciona dados, sempre sequencialmente após o último dado inserido, e para remover sempre o primeiro dado a ser inserido.

Suas funções:

  • Criar uma fila vazia;
  • Inserir dado no final;
  • Retirar o dado do início;
  • Verificar se a fila está vazia;
  • Remover a fila.
fila

Exemplificando a fila podemos ver que as ações são feitas sequencialmente, sempre necessitando agir do início para o final, imagine que para removermos a imagem do monitor, é necessário uma sequência de processos, precisa de um click do mouse, para ser processado e mudado o que é apresentado no monitor, não se pode remover a imagem diretamente do monitor sem os processos anteriores.

No mundo real o processo pode ser imaginado como  a lista de pedidos em um restaurante pelo ifood, onde o primeiro pedido que chegou, é preparado e enviado, caso chegue outro pedido vai para o final da fila, até todos os anteriores serem preparados e enviados.

Ou a clássica fila do pão, na padaria.

CONCLUSÃO

A conclusão adquirida como desenvolvimento do trabalho foi que existem inúmeras formas de se manipular e organizar os dados, mas com suas limitações, portanto deve-se escolher a forma de se usar caso a caso.

Pois quanto menos limitações de manipulação dos dados, maior o custo de memória como é no caso da lista duplamente encadeada o que torna um fator muitas vezes decisivo na hora de se escolher usá-la, caso não haja tanto espaço para trabalhar.

Já na parte de pilha ou fila, podem ser economicamente vantajosas em relação a memória, porém se seu banco de dados for muito numeroso, a economia em espaço será custosa na parte de tempo, pois demandará muito tempo de processamento por ser apenas uma forma de trabalhar os dados.

Então sempre devemos escolher o melhor custo/benefício para otimizar ambos os quesitos, como espaço em memória, tempo de processamento, qualidade na alimentação e busca ou em casos específicos, visando a necessidade do cliente.

marcus rolim

Marcus Rolim

Trabalho de revisão de algoritmo e estrutura de dados avançados, do 5º semestre de ciência da computação. UNIDERP