Lista ligada
Origem: Wikipédia, a enciclopédia livre.
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 manipularmos estas listas nomeadamente: inserir dados ou remover dados temos que ter sempre em atenção em ter um ponteiro que aponte para o 1º elemento e outro que aponte para o fim, isto porque se queremos inserir ou apagar dados que estão no inicio ou no fim da lista então a operação é rápidamente executada caso seja um nó que esteja no meio da lista pois terá que haver uma procura até encontrar a posição desejada.
Índice |
[editar] Vantagens
- A inserção de um elemento no meio da lista não implica mover todos os elementos.
[editar] Desvantagens
- O acesso sequencial, para eliminação ou inserção de um elemento no meio da lista.
[editar] 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)
[editar] Exemplo
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("----------------------------------------------"); }
[editar] Exemplo em Java
Exemplo de um Código feito para um dicionário de palavras em linguagem de programação Java:
import javax.swing.*; class No { int elemento; No prox; No (int elem){ elemento = elem; prox = null; } } class ListaLigada { No primeiro, ultimo; ListaLigada () { primeiro = null; ultimo = null; } public boolean ListaVazia() { if (primeiro == null && ultimo == null) { return true; } else { return false; } } public void InserirInicio(No novoNo) { if (ListaVazia()) { ultimo = novoNo; } else { novoNo.prox = primeiro; } primeiro = novoNo; } public void InserirFinal(No novoNo) { if (ListaVazia()) { primeiro = novoNo; } else { ultimo.prox = novoNo; } ultimo = novoNo; } public int ContarNos() { int tamanho = 0; No NoTemp = primeiro; while (NoTemp !=null) { tamanho = tamanho+1; NoTemp = NoTemp.prox; } return tamanho; } public void InserirMeio(No NovoNo, int posicao) { No NoTemp = primeiro; int NroNos, posAux = 1; NroNos = ContarNos(); if(posicao <= 1) { InserirInicio(NovoNo); } else { if (posicao > NroNos) { InserirFinal(NovoNo); } else { while (posAux < (posicao -1)) { NoTemp = NoTemp.prox; posAux = posAux + 1; } NovoNo.prox = NoTemp.prox; NoTemp.prox = NovoNo; } } } public void Remover(int elemento) { No NoTemp = primeiro; No NoAnt = null; if (primeiro.elemento == elemento) { primeiro = primeiro.prox; } else { while (NoTemp !=null && NoTemp.elemento != elemento) { NoAnt = NoTemp; NoTemp = NoTemp.prox; } if(NoTemp != null) { NoAnt.prox = NoTemp.prox; } if(NoTemp == ultimo) { ultimo = NoAnt; } } } public void ElementoInicio() { if(!ListaVazia()) { System.out.println("O primeiro elemento "+primeiro.elemento); } else { System.out.println("Lista ligada vazia"); } } public void ElementoFinal() { if(!ListaVazia()) { System.out.println("O ltimo elemento "+ultimo.elemento); } else { System.out.println("Lista ligada vazia"); } } public No BuscarNo (int elemento) { int i = 1; No NoTemp = primeiro; while (NoTemp !=null) { if(NoTemp.elemento == elemento) { System.out.println("No "+ NoTemp.elemento + " posicao " +i); return NoTemp; } i = i +1; NoTemp = NoTemp.prox; } return null; } public void MostrarLista() { int i = 1; No NoTemp = primeiro; while (NoTemp !=null) { System.out.println("Elemento " + NoTemp.elemento + " posicao " +i ); NoTemp = NoTemp.prox; i = i +1; } } } class Exemplo1 { public static void main (String args[]) { ListaLigada realLista = new ListaLigada(); int i; int num; for (i = 1; i<=5; i++) { num = Integer.parseInt(JOptionPane.showInputDialog("Digite um nr ") ); realLista.InserirFinal(new No(num)); } realLista.MostrarLista(); System.exit(0); } }