Lista ligada estática

A lista ligada, quando implementada de forma sequencial, envolve uma abordagem um pouco complexa de se compreender. Por isso, é importante acompanhar a explicação a seguir com bastante atenção.

Definição

De forma similar às implementações dinâmicas, a lista ligada sequencial também deve apresentar uma estrutura ITEM, que faz a vinculação de um elemento da lista com o seu próximo.

#define TAM 4
#define INEXISTENTE -1

typedef struct{
    int chave;
} REGISTRO;

typedef struct{
    REGISTRO r;
    int prox;
} ITEM;

typedef struct{
    ITEM itens[TAM];
    int inicio;
    int dispo;
} LISTA;

Uma particularidade importante é o fato de que, além do vetor de itens e do marcador do inicio, a LISTA possui também outra variável, a dispo, que indica qual posição do vetor está disponível para inserção de um novo ITEM.

Antes da definição dos tipos de dados, além de TAM, também definimos uma constante chamada INEXISTENTE, para facilitar a implementação e representar o valor NULL que, em C, não é aplicável a inteiros.

Funções de manipulação

Inicializar a lista

Para inicializar a lista ligada estática, usaremos a seguinte implementação:

void inicializar(LISTA *l){

    l->inicio = INEXISTENTE;
    l->dispo = 0;

    for (int i = 0; i < TAM - 1; i++){
        l->itens[i].prox = i + 1;
    }
    l->itens[TAM - 1].prox = INEXISTENTE;
}

A dinâmica do procedimento é bastante simples: primeiro, o início da lista é declarado como INEXISTENTE (1). Como a lista está vazia, a primeira posição disponível para inserção é a posição 0.

Até aqui, tudo parece igual às demais estruturas que utilizamos. A diferença começa com a presença de um laço de repetição for, de 0 até TAM-1. Nesse laço, para cada item da lista, vamos apontar qual será o seu próximo. No caso da última posição válida do vetor, representada por TAM-1, declaramos que o seu próximo tem valor INEXISTENTE.

Acompanhe, na representação visual a seguir, o que está acontecendo nesse procedimento:

Representação da lista ligada estática após a inicialização..

Inserindo um elemento na lista

A inserção na lista ligada sequencial acontecerá sempre na posição que está marcada como disponível (l->dispo). Por isso, a manipulação desse valor é um procedimento de extrema importância para o correto funcionamento da aplicação

void inserir(LISTA *l, REGISTRO r){
    if (l->dispo != INEXISTENTE){
        int novo = l->dispo;
        l->dispo = l->itens[l->dispo].prox;

        if (l->inicio == INEXISTENTE){
            l->inicio = novo;
        }
        else{
            int pos = l->inicio;
            int ant = INEXISTENTE;
            while (pos != INEXISTENTE){
                ant = pos;
                pos = l->itens[pos].prox;
            }
            l->itens[ant].prox = novo;
        }
        l->itens[novo].r = r;
        l->itens[novo].prox = INEXISTENTE;
    }
    else{
        printf("Lista cheia!\n");
    }
}

Removendo da lista

void remover(LISTA *l, REGISTRO r) {
    int ant = INEXISTENTE;
    int pos = l->inicio;

    while (pos != INEXISTENTE && l->itens[pos].r.chave != r.chave) {
        ant = pos;
        pos = l->itens[pos].prox;
    }
    if (pos == INEXISTENTE) return;

    if (ant == INEXISTENTE) {
        l->inicio = l->itens[pos].prox;
    }
    else {
        l->itens[ant].prox = l->itens[pos].prox;
    }

    // Adicionar à lista de disponíveis
    l->itens[pos].prox = l->dispo;
    l->dispo = pos;
}

Imprimindo a lista

void imprimir(LISTA *l){
    int pos = l->inicio;
    while(pos!=INEXISTENTE){
        printf("%d\n", l->itens[pos].r.chave);
        pos = l->itens[pos].prox;
    }
}

Testando

int main(void){
    LISTA l;
    inicializar(&l);
    inserir(&l, (REGISTRO){10});
    inserir(&l, (REGISTRO){20});
    inserir(&l, (REGISTRO){30});
    
    remover(&l, (REGISTRO){20});
    inserir(&l, (REGISTRO){40});
    
    imprimir(&l);
    return 0;
}
Nesta página