Lista ligada

Uma lista encadeada ou lista ligada é uma estrutura de dados linear e dinâmica. Ela é composta por várias células que estão interligadas através de ponteiros, ou seja, cada célula possui um ponteiro que aponta para o endereço de memória da próxima célula. Desse modo, as células da estrutura não precisam estar em posições contíguas da memória. Isso faz com que a estrutura se torne dinâmica, pois há qualquer momento, é possível alocar uma nova célula e mudar os ponteiros das células já existentes, de modo que a nova célula seja inserida na estrutura com êxito, na posição desejada pelo programador.

Exemplo de lista singularmente encadeada. Nela, cada célula é composta pelo dado e um ponteiro para o elemento posterior.

Ao lado temos um exemplo de uma lista encadeada. Nela, cada célula aponta para o endereço de memória da próxima célula através de um ponteiro. Como o último elemento da lista (célula 5) não possui próximo, ele apontará para nulo, que representa uma posição inválida na memória que não pode sofrer escrita ou ser dereferenciada.

Para inserir dados ou remover dados é necessário, no mínimo, um ponteiro que aponta para a primeira célula da lista. Esse ponteiro é normalmente chamado de head. A partir dele, podemos acessar a segunda célula, e a partir da segunda célula, podemos acessar a terceira, e assim em diante. Ou seja, com o ponteiro para a primeira célula, podemos acessar qualquer célula de uma lista encadeada.

Tipos

Exemplo de lista duplamente encadeada. Nela, cada célula é composta pelo dado, um ponteiro para o elemento posterior e um ponteiro para o elemento anterior.

Normalmente, temos dois tipos diferentes de listas encadeadas:

• Lista singularmente encadeada (Singly Linked List).
• Lista duplamente encadeada (Doubly Linked List).

A lista singularmente encadeada é justamente aquela explicada na seção principal.

A lista duplamente encadeada faz com que cada elemento possua dois ponteiros: um para o elemento posterior (assim como a lista singularmente encadeada), e um para o elemento anterior.

Também possui uma referência (ponteiro) para o último elemento da lista, comumente chamado de tail. As diferenças entre encadeamento singular e duplo são melhores explicadas no parágrafo a seguir.

Singular vs. Duplo

Comparando os dois tipos de listas encadeadas, temos que:

• Uma célula de uma lista duplamente encadeada ocupa mais memória do que uma célula de uma lista singularmente encadeada, devido ao ponteiro adicional que aponta ao elemento anterior (considerando que os tipos das duas listas possuem o mesmo tamanho).
• Inserções em listas duplamente encadeadas são potencialmente mais lentas devido à maior quantidade de ponteiros que precisam ser rearranjados.
• Porém, certas iterações e operações de indexação podem ser mais fáceis ou rápidas em listas duplamente encadeadas. Como por exemplo, percorrer a lista de trás pra frente. Aa lista duplamente encadeada pode acessar a última célula e percorrer através dos ponteiros de trás de cada célula, assim percorrendo a lista de trás para frente. Outro exemplo: pegar o penúltimo elemento da lista. Nesse caso, A lista singularmente encadeada terá que passar por n-1 elementos (onde n é o tamanho da lista), enquanto a duplamente encadeada pode ir para o elemento final e percorrer somente um elemento para trás para obter o penúltimo elemento.

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 todos os elementos (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) (ou O(1) quando se tem uma referência pro fim da lista).
  • Meio: O(n).

• Eliminação
  • Cabeça: O(1).
  • Cauda: O(n) (ou 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. Ele cria um nome alternativo para No_st, que pode ser chamado simplesmente de No por outras estruturas de dados.

Exemplo de inicialização e preenchimento no main:

int main(void){
   No primeiro;
   No segundo;

   primeiro.numero = 1;
   segundo.numero = 2;
   primeiro.prox = &segundo;
   
   printf("%d\n", primeiro.numero);
   printf("%d\n", primeiro.prox->numero);

   return (1);
}

Neste exemplo, as chamadas às funções printf() imprimiriam 1 e 2, respectivamente.

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

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;
	}
}

Exemplo em Pascal

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

program Lista_ligada;
uses crt;
type
  Tdado = char;
  Tptr = ^Tnode;
  Tnode = record
            prox: Tptr;
            info: Tdado;
          end;

procedure exibe(ptr:Tptr);
var
  aux:Tptr;

begin
  aux := ptr;
  if (aux = NIL) then
    writeln('A lista está vazia.') else
  begin
    while (aux^.prox <> NIL) do
    begin
      writeln(aux^.info);
      aux := aux^.prox;
    end;
    writeln(aux^.info);
  end;
  readkey;
end;

procedure insereInicio(var ptr:Tptr; v:char);
var
  aux:Tptr;

begin
  if (ptr <> NIL) then
  begin
    new(aux);
    aux^.info := v;
    aux^.prox := ptr;
    ptr := aux;
  end else
  begin
    new(ptr);
    ptr^.info := v;
    ptr^.prox := NIL;
  end;
end;

procedure insereFinal(var ptr:Tptr; v:char);
var
  aux: Tptr;
  nova: Tptr;

begin
  aux := ptr;
  if (aux = NIL) then
    writeln('Lista está vazia.') else
  begin
    while (aux^.prox <> NIL) do
      aux := aux^.prox;
    new(nova);
    nova^.info := v;
    nova^.prox := NIL;
    aux^.prox := nova;
  end;
end;

procedure remove(var ptr:Tptr; v:char);
var
  aux:Tptr;
  aux2:Tptr;

begin
  if (ptr = NIL) then
    writeln('A lista está vazia.') else
  begin
    aux := ptr;
    if (aux^.info = v) then
    begin
      ptr := ptr^.prox;
      dispose(aux);
    end;
    while (aux^.prox <> NIL) do
    begin
      if (aux^.prox^.info = v) then
      begin
        aux2 := aux^.prox;
        aux^.prox := aux2^.prox;
        dispose(aux2);
      end;
      aux := aux^.prox;
    end;
  end;
end;

Ver também

• Lista
• Lista duplamente ligada