Listas Ligadas
As listas ligadas ou encadeadas são conjuntos de elementos encadeados, onde cada
elemento contém uma ligação com um ou mais elementos da lista. A forma de
organização e acesso aos elementos de uma lista podem caracterizar pilhas, filas,
árvores binárias e grafos.
A grande diferença entre as listas e as pilhas ou filas é que as listas não possuem regras
para o acesso de seus elementos. Ou seja, a inclusão, exclusão ou consulta dos
elementos da lista podem acontecer de forma aleatória. Isso implica numa série de
cuidados durante os processos de inclusão e exclusão, devido à necessidade de não
destruir a ordem da lista com ponteiros "perdidos".
Uma lista ligada tem necessariamente uma variável ponteiro apontando para o seu
primeiro elemento. Essa variável será utilizada sempre, mesmo que a lista esteja vazia,
e deverá apontar sempre para o início da lista (primeiro elemento). Caso esta primeira
variável não seja atualizada corretamente (no caso da inclusão de um elemento na
primeira posição), a lista poderá se perder na memória e não ser mais acessível.
Cada elemento da lista ligada será composto por 2 partes principais: uma parte conterá
as informações e a outra as conexões com outros elementos.
Inicialmente, vamos admitir que cada elemento da lista possui uma única conexão.
Assim, cada elemento será formado por um bloco de dados e um ponteiro para o
proximo elemento, e chamaremos cada elemento de célula:
Uma vez que cadacada célula é um conjunto de informações de tipos diferentes (por
exemplo: um dado int e o ponteiro *int) ela é uma estrutura formada pelo programador.
Para a figura acima, podemos dizer que a estrutura édefinida como:
structcelula{
// nome da estrutura
int dados;
// campo
structcelula* proximacelula;
// ponteiro para a proximacelula
}
Supondo que na área de dados haverá um único campo inteiro e que a célula deverá
apontar para outra para que uma lista seja constituída, então o ponteiro para a próxima
célula deverá ser ponteiro de structcelula, pois apontará para uma nova célula. Assim, a
lista ligada de células ficará assim organizada:
Iniciando a Lista
Uma lista ligada é toda composta por elementos alocados em memória alocada
dinamicamente. No entanto, é importante lembrar que memória alocada dinamicamente
não tem um nome como as variáveis declaradas normalmente num programa. Sendo
assim, toda lista deverá ter uma variável "padrão" que apontará para o seu primeiro
elemento.
Uma vez que o primeiro elemento será uma célula, e cada célula é uma estrutura, então
a variável que apontará para o início da lista será um ponteiro de estrutura. A variável
início mostrada na figura acima será então definida como:
structcelula* inicio;
Uma vez que a lista não possui elementos ainda, então:
inicio = 0;
Incluindo a Primeira Célula
Utilizando a lista composta pelas células definidas acima e pela variável apontadora da
primeira célula:
structcelula{
int dados;
structcelula* proximacelula;
}*inicio;
// nome da estrutura
// campo de dados
// ponteiro para a proximacelula
// ponteiro para o início da lista
Para uma lista vazia (sem células), a variável inicio apontará para zero:
inicio=0;
Incluindo o primeiro elemento (primeira célula):
structcelula* aux;
//variavel auxiliar
// reserva de memória para nova célula com endereço de memória alocada armazenado
em aux:
aux = (structcelula*) malloc (sizeof (structcelula));
Temos então:
e precisamos atualizar os ponteiros para que a lista receba seu primeiro elemento. Sendo
assim:
1) aux->proximacelula = 0; // atribui 0 ao campo proximacelula da célula apontada
por aux
2) inicio = aux; // copia o endereco de aux em inicio
(animação)
Para inserir dados nesta primeira célula, podemos utilizar o ponteiro aux, que
permanece apontando para a célula.
aux->dados = 10;
//atribui o valor 10 ao campo dados da célula pontada por aux
A maneira de ler é: "aux ponteiro dados recebe 10".
Definindo as Estruturas
As estruturas podem ser compostas de diferentes maneiras, conforme explicado na aula
de Estruturas, contendo quantos campos de dados forem necessários e quantos ponteiros
forem necessários. Observe a lista a seguir e a definição da estrutura formadora das suas
células:
structelementocelula{
structelementocelula* anterior; // ponteiro da celula anterior
intindice;
// campo de dado
char nome[15];
// campo de dado
structelementocelula* proxima; // ponteiro da proximacelula
}*cabeca, *cauda;
Percorrendo a Lista
Uma vez que as células de uma lista não possuem nome, pois são memória alocada
dinamicamente, a única maneira de acessar uma célula é através dos ponteiros para esta
célula.
A primeira célula da lista é especialmente fácil de acessar, pois existe sempre uma
variável apontando para ela (o inicio nas imagens anteriores). No entanto, como acessar
as demais células? É importante lembrar que todas as células tem sempre alguém que as
aponta. Ou seja, a segunda célula da lista será apontada pela primeira, a terceira pela
segunda e assim por diante até o final da lista.
Sendo assim, para percorrer uma lista e acessar cada uma das suas células, utiliza-se
uma variável auxiliar. Essa variável irá receber o endereço de uma célula e permitirá
que o conteúdo dessa célula seja acessado (consultado, modificado, etc). Vamos criar
uma variável para isso:
structcelula* aux;
// variável auxiliar para percorrer a lista
Inicialmente, aux deverá apontar para o mesmo lugar que a variável de inicio da lista
para que possamos percorrê-la. Depois, aux receberá o endereço contido no campo
ponteiro, ou seja, receberá o endereço da próxima célula: isso acontecerá até aux valer 0
(zero) e a lista ter sido completamente percorrida. Observe na animação a seguir:
struct no{
char letra;
struct no* px;
}*inicio;
(animação)
Incluindo Células
A inclusão de células numa lista ligada deve ser feita com cuidado para que os ponteiros
permaneçam atualizados e parte da lista não se perca.
Existem algumas situações que devem ser verificadas no momento de inclusão de uma
célula, principalmente porque uma célula pode ser incluída em diferentes posições da
lista (início, meio ou fim)
Observe a lista abaixo e os passos necessários para incluir a célula de valor 13 no seu
final:
1.
2.
3.
4.
5.
se a lista não é vazia percorrer a lista até a última célula
alocar memória
atribuir dados aos campos de dados
atribuir ao campo ponteiro da última célula o endereço da nova célula
atribuir 0 ao campo ponteiro da célula incluída
(animação)
structxxx *aux, *nova;
aux = inicio;
if (aux!=0) {
while(aux->prox != 0)
aux = aux->prox;
nova = (structxxx *)malloc(sizeof(structxxx))
nova->valor = 13;
nova->prox = aux->prox;
aux->prox = nova;
}
Excluindo Células
Os passos para exclusão de uma célula vão depender da posiçào da célula dentro da
lista. Uma exclusão pode ocorrer no início, final ou no meio da lista.
Da mesma forma que na inclusão, o principal cuidado é com os ponteiros para que a
lista não tenha células perdidas durante o processo.
Na lista a seguir é feita a exclusão da célula de valor 7. Os passos necessários são:
1. percorrer a lista até a célula anterior à de valor 7
2. atribuir o endereço da célula de valor 7 a um ponteiro auxiliar (essencial
para que a memória seja liberada)
3. alterar o endereço apontado pela célula anterior à de valor 7 para que ela
aponte para onde a célula de valor 7 aponta atualmente.
4. liberar a memória da célula de valor 7
(animação)
structxxx *aux, *apaga;
aux = inicio;
while(aux->prox->valor != 7)
aux = aux->prox;
apaga = aux->prox;
aux->prox = apaga->prox;
free(apaga);
Exercícios
•
1) Elabore um algoritmo para a inclusão de elementos numa lista ligada de
encadeamento simples (um único ponteiro de célula) a partir do seu início.
Lembre-se de verificar quando a célula é a primeira a ser inserida na lista. Faça a
simulação desenhando os passos da inclusão.
•
2) Declare a estrutura padrão das células da lista do exercício 1).
•
3) Atribua valores à(s) área(s) de dados do primeiro elemento da lista definida
em 1) e 2).
•
4) Escreva os passos necessários em linguagem C para inserir o elemento 9 na
lista a seguir de forma que a lista permaneça ordenada.
•
5) Exclua a célula que contém o valor 2 da lista em 4). (Cuidado para não perder
os ponteiros!)
•
6) Com a lista definida em 4) exiba o conteúdo de:
o comeco->valor
o comeco->prox->valor