Lista encadeada

Uma lista ligada ou lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por células que apontam para o próximo elemento da lista. Para “ter” uma lista ligada/encadeada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. O esquema a seguir representa uma lista ligada/encadeada com 5 elementos:

Célula 1 ---> Célula 2 ---> Célula 3 ---> Célula 4 ---> Célula 5 ---> (Nulo)

Para inserir dados ou remover dados é necessário ter um ponteiro que aponte para o 1º elemento e outro que aponte para o fim, porque se queremos inserir ou apagar dados que estão nessas posições, a operação é rapidamente executada. Caso seja necessário editar um nó que esteja no meio da lista haverá uma busca pela posição desejada.Diagrama conceitual de uma lista ligada.

Vantagens

  • A inserção ou remoção de um elemento na lista não implica a mudança de lugar de outros elementos;
  • Não é necessário definir, no momento da criação da lista, o número máximo de elementos que esta poderá ter. Ou seja, é possível alocar memória “dinamicamente”, apenas para o número de nós necessários.

Desvantagens

  • A manipulação torna-se mais “perigosa” uma vez que, se o encadeamento (ligação) entre elementos da lista for mal feito, toda a lista pode ser perdida;
  • Para aceder ao elemento na posição n da lista, deve-se percorrer os n – 1 anteriores.

Níveis de complexidade

Numa lista com n itens, temos as seguintes complexidades de tempo no pior caso:

  • Inserção
    • Cabeça O(1)
    • Cauda O(n) (O(1) quando se tem uma referência pro fim da lista)
    • Meio O(n)
  • Eliminação
    • Cabeça O(1)
    • Cauda O(n) (O(1) quando se tem uma referência pro fim da lista)
    • Meio O(n)

Exemplo em C

Exemplo de código feito em linguagem de programação C:

Estrutura

typedef struct No_st{
    int numero;
    struct No_st *prox;
}No;

O tipo de dados seria definido apenas pela chamada ao método struct, mas a inclusão do typedef simplifica a sua utilização. A partir deste momento, a variável do tipo No está disponível, sendo o seu acesso feito como a uma qualquer estrutura de dados.

Exemplo de inicialização e preenchimento no main:

int main(void){
    No exemplo; /*A variável exemplo é do tipo no*/
    No *pexemplo; /*A variável pexemplo do tipo apontador para no*/

   exemplo.numero = 1;
   pexemplo = &exemplo;
   
   printf("%d\n", exemplo.numero);
   printf("%d\n", pexemplo->numero);

   return (1);

}

Neste exemplo, ambas as chamadas à função printf() iriam imprimir o número 1.

Manutenção

Cria Lista

Para começar uma lista não basta começar a inserir novas células, é preciso uma base, ou raiz, que será sempre a mesma para uma lista. Esta raiz pode ser simplesmente um apontador para uma lista ou um apontador para uma primeira célula vazia. Normalmente, para listas, é usada a célula vazia, já para as pilhas e filas é usado o apontador para os respectivos. A função seguinte é usada no main após ser declarada a variável raiz que será do tipo apontador para lista( que nestes exemplos tem o nome No).Esta cria uma célula vazia e mete a raiz a apontar para esta:

No * cria_lista(){     // Função do tipo apontador para lista, i.e., o tipo de função tem de ser igual ao tipo que retorna
    No * novo,*aux;

    novo = (No *) malloc( sizeof( No ));   /*Aloca memória do tamanho de uma célula*/

    if(novo == NULL) exit(0);    /* Se não alocar memória significa que não há memoria disponível, logo deve sair*/
    
    
    novo->prox = NULL;         /*Como esta deve ser a primeira função a ser executada, esta célula vazia aponta para NULL*/
    
    aux= novo; /*Para retornar o aux com o endereço da célula vazia, deve ser corrigido o valor do mesmo*/


    return (aux); /*Retorna o aux*/
}


Um exemplo da sua utilização no main seria:

int main(void){
    No * raiz;

    /*raiz = (No *) malloc( sizeof(No) ); */
    raiz = cria_lista();
    /* Depois começa o seu uso: Inserção, Remoção, etc...*/
    return EXIT_SUCCESS;
}

Como raiz está sendo passada como parâmetro na função cria_lista() e em outras funções, é preciso alocar memória para raiz de modo que seja possível realizar as operações no ponteiro que interage com raiz dentro das funções.

No início

No * inserirNoInicio(No * raiz, int numero){
    No * novo, *aux;
    aux = raiz;
    novo = (No *) malloc(sizeof(No));
    if(novo == NULL) exit(0);     
    novo->numero = numero;
    novo->prox = aux->prox;
    aux->prox = novo;
    return(aux);
}

No fim

void inserirNoFim(No **raiz, int numero){
    No *novo;
    novo = (No *) malloc(sizeof(No));
    if(novo == NULL) exit(0);
    novo->numero = numero;
    novo->prox = NULL;
    
    if(*raiz == NULL){
        *raiz = novo;
    }else{
        No *aux;
        aux = *raiz;
        while(aux->prox != NULL){
            aux = aux->prox;
        }
        aux->prox = novo;
        *raiz = aux;
    }
}

Remoção

No início

void removerNoInicio(No *raiz){
    No *aux;
    if(raiz == NULL)
        printf("\nA lista ja esta vazia");
    else{
        aux = raiz->prox;
        raiz->prox = aux->prox;
        free(aux);
    }
}


No fim

void removerNoFim(struct No **raiz){
    if(*raiz == NULL)
        printf("\nA lista ja esta vazia");
    else{
        struct No *auxFrente, *auxTras=NULL;
        auxFrente = *raiz;
        while(auxFrente->prox != NULL){
            auxTras = auxFrente;
            auxFrente = auxFrente->prox;
        }

        if(auxTras != NULL)
            auxTras->prox = NULL;

        free(auxFrente);
    }
}

Exemplo de um Código feito para um dicionário de palavras em linguagem de programação C:

 struct dic{
     char *original;
     char *complementar;
     struct dic *prox;
 };
 
 struct dic* ini=NULL;
 struct dic* last=NULL;''
 
 //adicionar um novo dic à nossa lista
 void dic_add(char *original, char *complementar){
         
     //se last é igual a Null quer dizer que a lista está vazia
     if (last == NULL){
         // o elemento será o primeiro
         last = (struct dic*)malloc(sizeof(struct dic));
         (*last).original = original;
         (*last).complementar = complementar;
         // Definição da cabeça da fila
         ini = last;
     } else {
         // o elemento será o último
         (*last).prox = (struct dic*)malloc(sizeof(struct dic));
         last = (*last).prox;
         (*last).original = original;
         (*last).complementar = complementar;
     }        
 }
 
 //Percorrer e Imprimir a lista ligada
 void dic_print(){
     int sair = 0;
     struct dic* act = ini;
    
     do {
         if (act == last)
             sair = 1;
         printf("----------------------------------------------\n");
         printf("original: %s\n",(*act).original);
         printf("complementar: %s\n",(*act).complementar);
         printf("prox: %d\n", (*act).prox);
         act = (*act).prox;
     } while(sair == 0);
     printf("----------------------------------------------");
 }

Fonte: https://pt.wikipedia.org/wiki/Lista_ligada

Deixe uma resposta