Lista ligada simples

Na Ciência da Computação, uma lista ligada ou lista encadeada é uma estrutura de dados que consiste em uma seqüência de registros de dados, semelhante a um vetor (array), porém em cada registro existe um campo contendo a referência para o próximo registro na seqüência.

Uma característica da lista ligada é ser dinâmica quanto ao seu tamanho em número de elementos, o limite passa a ser o espaço livre na memória, diferentemente de um vetor pois seu tamanho é fixo. Conseqüentemente não há desperdício de memória como existe por exemplo em um vetor com apenas 30% de espaço ocupado e os 70% restantes também consumindo a memória. Possui outra vantagem em relação a um vetor na inserção de um dado no início ou no meio pois não é necessário deslocar os dados à frente. Uma desvantagem é que para ter acesso a um dado é necessário percorrer a lista desde o início.

Cada registro, ou elemento, de uma lista é denominado célula, ou nó, e em uma lista ligada simples a célula é composta por dois campos, um campo que armazena o dado e um campo que armazena o endereço para a próxima célula. O campo dado é uma variável comum de qualquer tipo para armazenar um valor qualquer. O campo que armazena o endereço para o próximo é um ponteiro. A informação fundamental é o início da lista, a partir dele as outras células são acessadas. O último elemento da lista aponta para o nada, para o vazio.

Diversas implementações podem ser acrescentadas em uma lista ligada. A lista pode ser circular, onde o último elemento aponta para o primeiro elemento da lista. A lista pode ser duplamente ligada, deste modo cada célula também contém o endereço da célula anterior. Pode-se ter a informação do endereço da última célula, assim não é necessário percorrer toda a lista para adicionar uma célula no final. A lista pode ser com cabeça, onde existe um "falso" primeiro elemento, que não contém dado e apenas é um ponteiro que contém o endereço da primeira célula, ou até ser uma estrutura especial contendo também o endereço do último elemento. E cada célula da lista pode ter mais de um dado armazenado, por exemplo um pequeno vetor.

Abaixo apresento um exemplo de código, na linguagem C, de um programa capaz de manipular uma lista ligada simples. O código está estruturado em funções que criam, removem, imprimem e contam as células, junto com um menu para a interface com o usuário. O código está preparado para ser compilado no sistema Linux, utilizando a biblioteca nCurses. Para compilar em outro sistema pode ser necessária uma adaptação.

/**
Compilar com o comando:
gcc -o listaligada listaligada.c -lncurses
*/

#include <stdio.h>
#include <stdlib.h>
#include <ncurses.h>

#define ESC 27 /* Constante ESC recebe o código da tecla Esc */

struct celula { // Estrutura de cada célula da lista.
        int    valor; // A célula terá um valor qualquer.
        struct celula *prox; // E o endereço para à próxima célula.
};

struct celula *inicio; // Variáveis globais para guardar o início e o fim da lista.
struct celula *ultimo;

int contacelulas() { /** Função que retorna o número de células da lista. */

  int cont=0;
  struct celula *aux, *pos;

  aux = inicio; // Nossa variável auxiliar retorna no início da lista.

  while (aux != NULL) { // Enquanto a célula que "aux" se refere não for vazia.
    cont++;
    pos = aux->prox; // A variável "pos" recebe o endereço da próxima depois da que "aux" se refere.
    aux = pos; // A variável auxiliar avança para à próxima célula.
  }

  return cont;

}

void mostralista() { /** Função que imprime a toda a lista na tela. */

  struct celula *aux;

  for (aux=inicio; aux!=NULL; aux=aux->prox) // Percorre desde o início usando a variável "aux" para o deslocamento nas células.
    printw("%d ", aux->valor); // Imprime o valor contido na célula atual em que "aux" se refere.

  printw("(%d)", contacelulas()); // Mudança de linha na tela.

}

void inserecelula(int posicao, int valor){ /** Função que insere (cria) uma célula na posição escolhida. */

  int i;
  struct celula *aux, *pos;

  pos=inicio; // Usaremos a variável "pos" para percorrer a lista desde o início.
  
  if(inicio==NULL) { // Se ainda não existe a lista...
    
      inicio = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a primeira célula da lista.
      inicio->valor = valor; // Alimenta um valor para esta primeira célula.
      inicio->prox = NULL; // Esta primeira célula, como ainda é a única, recebe NULL como endereço para uma próxima.
      ultimo = inicio; // Como ainda só temos uma célula então a última é a primeira célula.
      
  } else { // Se já existe a lista...
    
      if(posicao == 1) { // Se vai inserir antes da primeira célula...

        aux = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a nova célula da lista.
        aux->valor = valor; // Alimenta esta nova célula com o valor de parâmetro.
        aux->prox = inicio; // Esta nova célula vai apontar para o inicio.
        inicio = aux; // O início passa a ser esta célula inserida.

      } else if(posicao > contacelulas()) { // Se vai inserir após a última célula...

        aux = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a próxima célula da lista.
        aux->valor = valor; // Esta próxima célula é alimentada com o valor de "valor".
        aux->prox = NULL; //  E recebe NULL como endereço para uma próxima.
        ultimo->prox = aux; // A última célula aponta para esta próxima.
        ultimo = aux; // Esta próxima célula passa a ser a última.

      } else { // Se não é antes da primeira nem após a última...

        for(i=1; i<=posicao-1; i++) { // Percorre da primeira até a célula anterior à posição que receberá uma nova célula.
          if(i==posicao-1) { // Se chegamos na posição anterior...
            aux = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a nova célula da lista.
            aux->valor = valor; // Alimenta esta nova célula com o valor de parâmetro.
            aux->prox = pos->prox; // Esta nova célula vai apontar para a próxima na qual a anterior estava apontando.
            pos->prox = aux; // A célula anterior agora aponta para esta nova célula.
          } else // Se ainda não chegamos na posição...
            pos = pos->prox; // A variável avança para à próxima célula.

        }
      }
  }
}

void removecelula(int posicao) { /** Função que remove uma célula na posição escolhida. */

  int i;
  struct celula *aux, *ant;

  aux=inicio; // Nossa variável auxiliar retorna no início da lista.

  if(inicio!=NULL) { // Se existe a lista...

    if(posicao == 1) { // Se vai remover a primeira célula...

      inicio = aux->prox; // A variável "inicio" recebe o endereço da próxima depois da que "aux" se refere.
      free(aux); // Libera o espaço alocado na memória.

    } else if(posicao == contacelulas()) { // Se vai remover a última célula...

      for(i=1; i<=posicao; i++) { // Percorre da primeira célula até a posição da célula que será removida.
        if(i==posicao-1) { // Se está na célula anterior à que vai ser removida...
          ant = aux; // Guardamos ela como sendo a anterior da que será removida.
          ant->prox = NULL; // A anterior recebe NULL como endereço para uma próxima.
        }
        if(i==posicao) { // Se está na célula que será removida...
          free(aux); // Libera o espaço alocado na memória.
          ultimo = ant; // A última célula agora é a anterior.
        } else // Se ainda não chegou na célula à ser removida...
          aux = aux->prox; // A variável auxiliar avança para à próxima célula.
      }

    } else if((posicao > 1) && (posicao < contacelulas())) { // Se não é a primeira nem a última que vai ser removida...

      for(i=1; i<=posicao; i++) { // Percorre da primeira célula até a posição da célula que será removida.
        if(i==posicao-1) // Se está na célula anterior à que vai ser removida...
          ant = aux; // Guardamos ela como sendo a anterior da que será removida.
        if(i==posicao) { // Se está na célula que será removida...
          ant->prox = aux->prox; // A célula anterior recebe o endereço da próxima depois da que vai ser removida.
          free(aux); // Libera o espaço alocado na memória.
        } else // Se ainda não chegou na célula à ser removida...
          aux = aux->prox; // A variável auxiliar avança para à próxima célula.
      }

    }
  }
}

void limpalista() { /** Função que limpa toda a memória alocada pelas células da lista. */

  struct celula *aux;

  aux = inicio; // Nossa variável auxiliar retorna no início da lista.

  while (aux != NULL) { // Enquanto a célula que "aux" se refere não for vazia.
    inicio = aux->prox; // A variável "inicio" recebe o endereço da próxima depois da que "aux" se refere.
    free(aux); // Libera a memória alocada para a célula em que "aux" se refere.
    aux = inicio; // A variável auxiliar avança para à próxima célula, que passa a ser o início.
  }

}

int main() {

  initscr();      /* Inicialização do ncurses */
  cbreak();       /* Desabilita o buffer do teclado */
  echo();         /* Ativa o echo para os caracteres digitados */
  clear();        /* Limpa a tela */
  
  char tecla; /* Variável que recebe os comandos para as ações na fila */
  int valor; /* Variável que recebe o valor para ser adicionado */
  int posicao; /* Variável que recebe a posição para a operação */
  int i;
  inicio = NULL; /* Ainda não existe uma lista na memória */
  
  while (tecla != ESC) { /* Enquanto não for pressionado Esc é executado o bloco a seguir */
    
    clear(); /* Limpa a tela */
    printw("\nOperacoes em Lista Ligada Simples, o que deseja fazer? (ESC sair)"); /* menu inicial */
    printw("\n\nOpcoes:  (i)nserir");
    printw("\n         (r)emover");
    printw("\n\nConteudo da fila: ");
    if(contacelulas() > 0) /* Se a fila não estiver vazia */
      mostralista(); /* Imprime todos os valores */
    else
      printw("vazio");
        
    printw("\n\nDigite a opcao: "); /* Prompt de linha comando */

    posicao = contacelulas()+1;
    valor = 0;
    
    tecla = getch(); /* Lê a tecla pressionada, comando inserir ou remover */

    switch(tecla) {
      case 'i': /* Operação de inserção na fila */
              printw("\n\nInserir:");
              printw("     Em qual posicao? ");
              scanw("%d", &posicao); /* Recebe a posição */
              printw("\n             Qual o valor? ");
              scanw("%d", &valor); /* Recebe o valor */
              inserecelula(posicao, valor); /* Executa a função */
              break;
      case 'r': /* Operação de remoção na fila */
              printw("\n\nRemover:");
              printw("     Qual posicao? ");
              scanw("%d", &posicao); /* Recebe a posição */
              removecelula(posicao); /* Executa a função */
              break;
      case ESC: /* Operação de saída com confirmação */
              printw("\n\nDeseja sair? s/n ");
              if(getch() == 'n')
                 tecla = 'n'; /* Se não quiser sair então é retirado o Esc da tecla */
              break;
    }
      
  }
  
  limpalista(); /* Executa a função */
  endwin();    /* Finaliza o ncurses */
  return 0;

}