Lista Ligada

Lista ligada é uma estrutura de dados que consiste em uma sequencia de várias estruturas chamadas nós. Cada um desses nós contém dados referentes a cada elemento (como ID ou chave), e uma referencia para a próxima estrutura nó da lista, como mostrado na figura abaixo

Imagem1

Como eu disse no começo, essa estrutura é dívida em duas partes (dados e referência), que podem ser representadas da seguinte maneira em C:

Imagem22

Essa será nossa estrutura base para montar nossa lista ligada. Eu uso uma variável global chamada localização para saber o tamanho atual da fila. (Ela poderia se chamar tamanho, mas ai eu teria que tirar todas as fotos novamente).

Existe mais de uma maneira de estruturar uma lista ligada. A maneira que vamos fazer aqui é chamada de lista com cabeça, onde o primeiro nó na lista só será usado para referência. Isso ajuda na hora de montar as funções de manipulação da lista, tornando mais fácil o trabalho do programador.

Criando a Base da Lista

Para começar uma lista ligada primeiro criamos nosso nó que será a cabeça.

Imagem2

Esse primeiro ponteiro criado será a cabeça da nossa lista. Nossa lista inicia vazia, então o valor que a cabeça aponta é NULL.

Imagem3

Nossa lista no momento está igual a figura acima.

Agora que temos o nosso nó base, que é a cabeça, podemos começar a inserir alguns valores na nossa lista.

Inserindo valores na lista

Inserindo após o nó cabeça

Agora vamos criar uma função para receber os valores e guarda-los na lista igual o código abaixo.

Imagem21

Depois de criar o novo nó e armazenar o valor dentro dele temos que referenciar esse novo nó a nossa lista.

Primeiro pegamos o valor que está ligado ao nó da cabeça e ligamos ao nosso novo nó (linha 51 do código acima).

Imagem5

O segundo passo é ligar o nó cabeça ao nosso novo nó (linha 52 do código acima).

Imagem6

Inserindo vários valores nossa lista fica da seguinte maneira: Inserindo os valores 3, 32 e 1, respectivamente, passando o ultimo nó da lista como parâmetro a cada chamada, temos a seguinte lista:

Imagem7

Inserindo no nó N

Podemos inserir valores no meio da lista, e isso é uma das grandes vantagens de se usar esta estrutura de dados, já que é meio complicado fazer isso com um array normal e estático. O código abaixo insere um valor na posição informada, caso essa posição seja maior que o tamanho da lista o valor será inserido no inicio.

Imagem18

Primeiro, criamos 3 novos ponteiros, um para o nosso novo nó e os outros dois para referência atual e futura.

Usando como referência a lista abaixo, vamos imaginar que o valor que nos vamos armazenar ficará antes do 1.

Imagem7

O passo a passo para inserir o valor será o seguinte:

1. Primeiro, criar os ponteiros e o novo nó, e inserir o valor dentro do novo nó (linha 70 até 73)

Imagem10

2. Achar a posição. Isso será feito dentro do while, até encontrar a posição indicada ou o valor do temp2 = NULL

Imagem11

3. Inserir o novo valor na lista. As duas ultimas linhas da função trata de fazer isso para gente.

Imagem12

Removendo da lista

Removendo após o nó cabeça

Essa função é bem parecida com a de inserir, no entanto vamos liberar a memória que está referenciada com a cabeça e ligar a cabeça com o próximo elemento.

Imagem19

Imagem15

Removendo um nó na posição N

Essa função é similar a “Inserindo no nó N “. só que seguindo a mesma ideia da função acima nosso objetivo nessa função é achar a refência que contem o nó com o nosso valor e tirar ele da referencia da nossa lista.

Imagem20

Imagem17

Imprimindo a Lista

Imprimir a lista nada mais é que passar por todos os seus nós e ir mostrando o valor.

O código abaixo percorre toda a lista. Podemos observar que o primeiro elemento a ser impresso é o ini->proximo e não o ini, já que o ini está apontando para a cabeça da lista e não tem nenhum valor interessante para gente lá.

Imagem8

Anúncios