Lista ligada: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 22h04min de 4 de março de 2015

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.

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

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