Listas Encadeadas em C

Uma Lista Encadeada é um sequência de objetos, lembrando, todos do mesmo tipo, na memória. Cada objeto da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e continua. Veja um exemplo na imagem abaixo:

Veja que cada célula guarda consigo um valor e ela aponta para a seguinte! Guarde bem esse conceito inicial pois é a estrutura básica de uma lista encadeada. ESTRUTURA: Guarda o valor do objeto e "aponta" para a próxima célula.

A explicação irá conter tópicos com exemplos práticos e códigos, além de um projeto feito por mim que foi produzido com o andamento de cada tópico.

Estrutura da Lista Encadeada

Apenas recapitulando a parte inicial, Lista Encadeadas é uma sequência de células; cada célula contém um objeto(Lembrando que todos do mesmo tipo) e o endereço da célula seguinte. Então, abaixo veja o código da declaração da Estrutura da Lista.

                 
         struct TipoLista {
                int valor;//Ou seja, o contéudo da célula, o seu valor.
                struct TipoLista *proximo;//"Aponta", ponteiro.
        };

Explicação do Código: Registramos uma nova estrutura, ou se desejar, Declaramos uma nova Estrutura, com o valor da célula e a seta que aponta pro próximo termo que é um Ponteiro.

Veja novamente na imagem abaixo que a célula 1 está apontando para a célula 2 e assim sucessivamente.

É conveniente tratar as células da lista como um novo tipo-de-dados (typedef):

typedef struct lista celula; //Celula

Vamos um pouco mais longe, digamos então que declararemos uma célula e um ponteiro para a célula.


            celula c;//Célula c
            celula *p;//Ponteiro p

Ok, declaramos as variáveis, se c é uma célula então c.valor é o contéudo(a variável valor da nossa estrutura), e c.proximo é o endereço de memória da próxima célula. Se p é um ponteiro, então, p->valor é o contéudo da célula e p->proximo aponta pra próxima célula, E quando chegar na última célula ela irá apontar pra NULL, pois não há nada. Então, a última célula é se e somente se p->proximo == NULL.

Endereço de uma Lista Encadeada

O endereço de uma lista encadeada é o endereço de sua primeira célula. Considere que le é uma lista encadeada. A lista está vazia se e somente le == NULL, isso quer dizer, a lista não possui células.

OBSERVAÇÃO: Listas são tendeciosas à funções e à procedimentos recursivos, geralmente, os algoritmos de lista encadeada ficam mais simples, otimizados com chamadas recursivas, ademais, é fácil manipular listas recursivamente e você verá ao longo dos problemas e exemplos práticos.


            //A seguinte função recursiva imrime o contéudo de uma lista encadeada le:
              void imprime(TipoLista *le){
                   if(le != NULL){
                    printf("%d\n", le->conteudo);
                    imprime(le->proximo);
                   }
              }

            //Aqui a função Iterativa:
              void imprime(TipoLista *le){
                celula *p;
                for(p=le; p!=NULL; p= p->proximo){
                    printf("%d\n", p->conteudo);
                }
              }

Busca em uma Lista Encadeada

A ideia principal desse tópico é a busca em uma Lista Encadeada, ou seja, a busca de um elemento x na minha Lista e saber se ele pertence ou não a ela.


//Função que retorna se um valor está na lista ou não.
//Se sim retorna o numero(tamanho) da célula, Se não retorna 0, ou seja, o valor não foi encontrado.
            int buscaElemento(int num, struct TipoLista *p){
	             int contador=0;
	             while(p->proximo != NULL && p->valor != num){
		         p = p->proximo;
		         contador++;
	             }
	             if(p->valor == num){
		                return contador;
	             }else{
	                    return 0; //False, nao encontrou o valor.
	             }
            }

Iniciamos o contador com 0 para que a cada laço do loop seja iterado +1 no seu valor, pois assim retorna em qual célula o elemento estará caso ele estiver na lista. O laço WHILE continua até que o ponteiro não aponte para uma célula vazia e que o valor da célula seja diferente do valor que queremos achar.

Cabeça da Lista - HEAD CELL

Convém tratar a primeira célula de uma lista encadeada como um mero "marcador de início" e ignorar o contéudo da célula. A primeira célula é a cabeça.
head cell = dunny cell.

Uma Lista Encadeada está vazia se e somente se le->proximo == NULL. Para criar uma Lista Encadeada vazia com cabeça, basta dizer:


            TipoLista *le;
            le = malloc(sizeof(lista));
            le->proximo = NULL;

A função malloc aloca dinamicamente memória para o Novo Nó de acordo com o sizeof da Estrutura.

Constantemente a head da lista é alterada, no exemplo que produzi a cada criação de um nó a cabeça muda, ainda que a lista não seja uma estrutura LIFO(last-in first-out) mas a cabeça indica o último que entrou.


        for(i=1; i<=6; i++){
            struct TipoLista *NovoNo = malloc(sizeof(lista));
            NovoNo->valor = i*10;
            NovoNo->proximo = le->proximo;//Insere o nó no início da lista.
            le->proximo = NovoNo;//Atualiza a HEAD da lista, antes era NULL e agora é o NovoNo.
        }

Inserção em uma Lista Encadeada

Suponha que quero inserir a nova célula entre a posição apontada por p e a posição seguinte. Considere o problema de inserir uma nova célula em uma Lista Encadeada. Só faz sentido se P é diferente de NULL.

Em tese, a inserção segue a mesma estrutura de código da mudança de cabeça da lista e adição de elementos.


        //Função que insere uma nova célula na LE.
        void insere(int x, lista *p){
            lista *nova;
            nova = malloc(sizeof(lista));
            nova->valor = x;
            nova->proximo = p->proximo;
            p->proximo = nova;
        }

No caso acima, inserimos a nova célula no início da Lista, mas se o p->prox==NULL então inserimos a nova célula no fim da lista.

Então, temos duas opções, Insere na cabeça da Lista ou insere no final da Lista.

Remoção em uma Lista Encadeada

Considere o problema de remover uma certa célula de uma Lista Encadeada. Como especificar a célula em questão? A ideia mais óbvia é apontar para a célula que quero remover. Mas é fácil perceber que essa ideia não é boa, é melhor apontar para a célula anterior à que remover. Veja que por esse método não é possível remover a primeira célula, ou se p == NULL ou p->proximo==NULL.


        //Esta função recebe o endereço p de uma célula de uma LE e remove da lista a p->prox.
        void remove(celula *p){
            celula *lixo;
            lixo = p->proximo;
            p->proximo = lixo->proximo;
            free(lixo);
        }

A função free desaloca o espaço de memória daquela variável, no caso em que estamos trabalhando é a célula da Lista.