Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados > Estruturas de Dados
Listas Lineares Ligadas
Se a inserção e exclusão em listas sequenciais podem acarretar grande movimentação de dados, uma solução óbvia é permitir que os dados ocupem qualquer posição disponível (e não necessariamente a posição física correta), e então criar um esquema para preservar a ordem dos elementos e gerenciamento de nós livres /ocupados.
Uma lista linear ligada (ou simplesmente lista ligada) é uma lista linear na qual a ordem (lógica) dos elementos da lista (chamados “nós”) não necessariamente coincide com sua posição física (em memória). Pode ser implementada de forma estática (usando-se um vetor) ou, em linguagens de programação que oferecem suporte à alocação dinâmica, com uso de ponteiros.
Listas Ligadas de Implementação Estática
A lista é formada pelo vetor de registros (A), um indicador de início da estrutura (inicio) e um indicador de início da lista de nós disponíveis (dispo).
Na prática, inicio e dispo são as entradas de duas listas que compartilham o mesmo vetor, sendo uma para os elementos efetivos da lista, e a outra para armazenar as posições livres.
typedef struct
{
REGISTRO A[MAX];
int inicio;
int dispo;
} LISTA;
Cada registro contém, além dos campos exigidos pela aplicação, um campo prox que contém um índice para o próximo elemento na série (vazio ou ocupado, conforme descrito a seguir). Um campo prox com valor -1 será usado para designar que o elemento em questão não possui sucessor.
Ao ser criada, a lista possui inicio = -1 (que indica que a lista está vazia) e dispo = 0 (ou seja, a primeira posição do vetor está disponível). Além disso, os campos prox de cada registro (exceto o último) apontam para o registro seguinte, constituindo uma lista de registros vazios encabeçada por dispo. O campo prox do último registro recebe o valor -1 indicando que não há mais elementos depois daquele ponto. A lista está cheia quando não há mais nós disponíveis (i.e., quando dispo == -1). A lista esta vazia quando não há elemento inicial (i.e., quando inicio == -1).
// Inicialização
void inicializarListaLigadaEstatica(LISTA *l)
{
l->inicio = -1;
l->dispo = 0;
for(int i=0; i < MAX – 1; i++)
l->A[i].prox = i + 1;
l->A[MAX – 1].prox = -1;
}
// Exibição da lista
void exibirLista(LISTA l)
{
int i = l.inicio;
while (i > -1) {
printf(“%d “, l.A[i].chave); // TIPOCHAVE deve ser int
i = l.A[i].prox;
}
}
// Busca sequencial
int buscaSeqOrd(TIPOCHAVE ch, LISTA l, int *ant)
{
int i = l.inicio;
*ant= -1;
while (i != -1)
{
if(l.A[i].chave >= ch) break;
*ant = i;
i= l.A[i].prox;
}
If(l.A[i].chave==ch) return(i);
else return (-1);
}
O gerenciamento de nós livres e ocupados exige a criação de rotinas específicas para “alocar” e “desalocar” um nó da lista apontada por dispo. A alocação envolve descobrir o índice de uma posição válida no vetor na qual novos dados possam ser inseridos, além de retirar esta posição da lista de disponíveis. A desalocação envolve a devolução de uma posição à lista de disponíveis para que possa ser reutilizada.
Listas Ligadas de Implementação Dinâmica
Para evitar a necessidade de definição antecipada do tamanho máximo da estrutura de implementação estática (i.e., o vetor), podemos tirar proveito dos recursos de alocação dinâmica de memória das linguagens de programação como C, deixando o gerenciamento de nós livres / ocupados a cargo do ambiente de programação. Esta técnica constitui à implementação dinâmica de listas ligadas, e requer o uso das funções disponibilizadas em
malloc.h: # include
Em uma lista ligada de implementação dinâmica, não há mais uso de vetores. Cada elemento da lista é uma estrutura do tipo NO, que contém os dados de cada elemento (inclusive a chave) e um ponteiro prox para o próximo nó da lista. Um nome auxiliar (estrutura) é usado para permitir a auto-referência ao tipo NO que está sendo definido.
typedef struct estrutura
{
TIPOCHAVE chave;
int info;
estrutura *prox;
} NO;
O tipo LISTA propriamente dito é simplesmente um ponteiro inicio apontando para o primeiro nó da estrutura (ou para NULL no caso da lista vazia). O último elemento da lista possui seu ponteiro prox também apontando para NULL. Embora não seja necessário o encapsulamento deste ponteiro em um tipo LISTA (afinal, uma lista é apenas um ponteiro, que pode ser NULL ou não), esta medida será adotada aqui por questões de padronização em relação aos tipos LISTA anteriores, e também porque alguns dos próximos tipos agregarão mais informações a esta definição.
typedef struct
{
NO* inicio;
} LISTA;
A alocação e desalocação de nós é feita dinamicamente pelo próprio compilador C através das primitivas malloc e free, respectivamente.
NO* p = (NO*) malloc(sizeof(NO)); // cria um novo nó em memória, apontado por p
free(p); // a área de memória apontada por p é liberada;
Via de regra, malloc() é usado em rotinas de inserção ou criação de novos nós, enquanto que free() é usado na exclusão. Rotinas que não criam ou destroem nós dificilmente precisam usar estas funções.
A única diferença significativa entre as implementações estática e dinâmica de listas ligadas está no fato de que a implementação estática “simula” uma lista ligada em vetor, e nos obriga a gerenciar as posições livres e ocupadas. Isso deixa de ser necessário no caso da alocação dinâmica “real”.
Referência Bibliográfica
Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.