Lista ligada

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(1)
  • Meio O(n)

• Eliminação
  • Cabeça O(1)
  • Cauda O(n)
  • 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 *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(struct 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;
    }
}

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("----------------------------------------------");
 }

Exemplo em C++

Pode-se utilizar também uma sintaxe de classe, atribuindo esses métodos, da linguagem de programação C++. Aqui, foram criadas duas classes: Node (nó) e List (lista). Os métodos criados foram os seguintes: adicionar, excluir, buscar e imprimir.

#include <iostream>
using namespace std;
 
class Node {
    public:
        int value; // Pode ser implementado qualquer tipo de dados aqui.
        Node *next;
        Node () {
            next = NULL; // Construtor padrão
        }
        Node (int _value) { // Construtor para o caso de haver já um valor a ser atribuído
            value = _value;
            next = NULL;
        }
};
 
class List {
    public:
        Node *head; // A "cabeça" é um ponteiro para o primeiro elemento da lista.
        List () { // Construtor padrão; único
            head = NULL;
        }
 
        void push_back (int x) { // Método para adicionar um elemento novo ao final da lista.
            Node *novo = new Node;
            novo->value = x;
            if (head == NULL)
                head = novo;
            else {
                Node *onde = head;
                while (onde->next)
                    onde = onde->next;
                onde->next = novo;
            }
        }
 
        void imprime(){ // Método para imprimir, na saída padrão, todos os elementos na tela;
            Node* temp = head;
            while (temp) {
                cout << temp->value << endl;
                temp = temp->next;
            }
            return;
        }
 
        bool find (int x) { // Método de busca de um elemento na lista
            Node *pointer = new Node;
            if (!head)
                return false;
            pointer = head;
            for (; pointer; pointer = pointer->next)
                if (pointer->value == x)
                    return true;
            return false;
        }
 
        bool deletar (int x) { // Método de exclusão de um elemento da lista, nesse caso, eliminando todos os elementos equivalentes a "x"
            Node *pointer = new Node;
            if (!find(x))
                return false;
            while (head->value == x)
                head = head->next;
            if (!head)
                return false;
            pointer = head;
            while (pointer) {
                if (pointer->next)
                    if (pointer->next->value == x)
                        pointer->next = pointer->next->next;
                pointer = pointer->next;
            }
            return true;
        }
 
};

Exemplo em Java

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

class No
{
        Object elemento;
        No prox;
 
        No (Object elem){
                elemento = elem;
                prox = null;
        }
}
 
public class ListaLigada
{
        private No primeiro, ultimo;
        private int nroNos;
 
        ListaLigada ()
        {
                primeiro = null;
                ultimo = null;
                nroNos = 0;
        }
 
        public boolean isVazia() {
                return (primeiro == null && ultimo == null);
        }
 
        public void addInicio(Object o) {
                nroNos++;
                No novoNo = new No(o);
                if (isVazia())
                        ultimo = novoNo;
                else
                        novoNo.prox = primeiro;
                primeiro = novoNo;
        }
 
        public void addFinal(Object o)  {
                nroNos++;
                No novoNo = new No(o);
                if (isVazia())
                        primeiro = novoNo;
                else
                        ultimo.prox = novoNo;
                ultimo = novoNo;
        }
 
        public int getNroNos() {
                return nroNos;
        }
 
        /*
         * @param posicao
         *                              posição contada a partir do zero como primeiro elemento
         */
        public void addMeio(Object o, int posicao)      {
                nroNos++;
                No novoNo = new No(o);
                if(posicao <= 1) {
                        addInicio(novoNo);
                        return;
                }
                if (posicao > nroNos) { //Outra abordagem seria lançar exceção para posição inválida (>nroNos+1)
                        addFinal(novoNo);
                        return;
                }
                No noTemp = primeiro.prox;
                for(int posAux=1;posAux<posicao;posAux++)
                        noTemp = noTemp.prox;
                novoNo.prox = (noTemp.prox).prox;
                noTemp.prox = novoNo;
        }
 
        public void Remover(Object elemento)
        {
                No noTemp = primeiro;
                No noAnt = null;
 
                if (primeiro.elemento.equals(elemento)) {
                        primeiro = primeiro.prox;
                        nroNos--;
                }
                else {
                        while (noTemp !=null && !noTemp.elemento.equals(elemento)) {
                                noAnt = noTemp;
                                noTemp = noTemp.prox;
                        }
                        if(noTemp != null) {
                                noAnt.prox = noTemp.prox;
                                nroNos--;
                        }
                        if(noTemp == ultimo) {
                                ultimo = noAnt;
                        }
                }
        }
 
        public Object BuscarElemento (Object elemento)
        {
                int i = 1;
                No noTemp = primeiro;
 
                while (noTemp !=null) {
                        if(noTemp.elemento.equals(elemento)) {
                                return noTemp;
                        }
                        i = i +1;
                        noTemp = noTemp.prox;
                }
                return null;
        }
}

Ver também

• Lista
• Lista duplamente ligada