Lista ligada
 | Este artigo não cita fontes confiáveis. (Março de 2011) |
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.
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
[editar | editar código-fonte]
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
[editar | editar código-fonte]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
[editar | editar código-fonte]- 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
[editar | editar código-fonte]- 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
[editar | editar código-fonte]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
[editar | editar código-fonte]Exemplo de código feito em linguagem de programação C:
Estrutura
[editar | editar código-fonte]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
[editar | editar código-fonte]Cria Lista
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]No início
[editar | editar código-fonte]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
[editar | editar código-fonte]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++
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]