Lista ligada
Origem: Wikipédia, a enciclopédia livre.
Uma lista ligada é 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, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. O esquema a seguir representa uma lista ligada 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 eleminação ou inserção de um elemento no meio da lista.
[editar] Níveis de complexidade
A nível temporal temos as seguintes complexidades:
- 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);
}
}
[editar] Texto de cabeçalho
==
