Aula 37 — Lista Ligada por Arranjo

Motivação: o limite da lista sequencial

A lista sequencial das aulas 29–36 guarda os registros lado a lado num array de tamanho fixo MAX. Inserir ou remover um elemento no meio exige deslocar fisicamente todos os que vêm depois — custo O(n).

Ideia geral: cada elemento indica seu sucessor

Em vez de exigir adjacência física, adicionamos ao array uma segunda linha de cursores: cada posição guarda o índice do seu sucessor na ordem lógica. O marcador de fim de cadeia é INVALIDO = −1.

Excluindo o 8 — apenas um cursor muda

O elemento 7 (A[3]) aponta para 8 (A[2]). O sucessor de 8 é 9 (A[1]). Para excluir 8, basta redirecionar o cursor de A[3] de 2 para 1. Nenhum dado é movido.

Estrutura de dados: dois campos, duas cadeias

A lista ligada por arranjo usa um único array A[MAX], mas mantém duas cadeias independentes dentro dele:

• Cadeia de uso (inicio): percorre os elementos válidos em ordem lógica crescente.
• Cadeia de disponíveis (dispo): percorre as posições livres para reutilização.

/*------------------------------------------------------------
 *  listaLigadaArranjo.c
 *  Lista ligada por arranjo — ordenada por chave, sem repetição
 *------------------------------------------------------------*/
#include <stdio.h>
#include <stdbool.h>

#define MAX      5
#define INVALIDO -1

typedef int TIPOCHAVE;

typedef struct {
    TIPOCHAVE chave;
    // outros campos do registro...
} REGISTRO;

/* Cada célula do arranjo: um registro + cursor para o próximo */
typedef struct {
    REGISTRO reg;
    int prox;   /* índice do próximo na cadeia (INVALIDO = fim) */
} ELEMENTO;

/* Cabeça da lista: o arranjo + dois cursores de controle */
typedef struct {
    ELEMENTO A[MAX];
    int inicio;  /* índice do 1º elemento em uso   (INVALIDO = lista vazia) */
    int dispo;   /* índice do 1º espaço disponível (INVALIDO = lista cheia) */
} LISTA;

Inicialização

Inicializar a lista significa montar a cadeia de disponíveis ligando todas as células do array em sequência, do índice 0 ao MAX−1. A cadeia de uso começa vazia (inicio = INVALIDO).

void inicializarLista(LISTA* l) {
    int i;
    for (i = 0; i < MAX-1; i++)
        l->A[i].prox = i + 1;   /* cada célula aponta para a próxima */
    l->A[MAX-1].prox = INVALIDO; /* última célula: fim da cadeia        */
    l->inicio = INVALIDO;        /* cadeia de uso vazia                 */
    l->dispo  = 0;               /* primeiro disponível: índice 0       */
}

Retornar o número de elementos

Não há um campo nroElem. Para contar os elementos, percorremos a cadeia de uso desde inicio até encontrar INVALIDO:

int tamanho(LISTA* l) {
    int i   = l->inicio;
    int tam = 0;
    while (i != INVALIDO) {
        tam++;
        i = l->A[i].prox;   /* avança pelo cursor da cadeia de uso */
    }
    return tam;
}

Exibição / Impressão

Percorremos a cadeia de uso a partir de inicio, imprimindo A[i].reg.chave a cada passo:

void exibirLista(LISTA* l) {
    int i = l->inicio;
    printf("Lista: \" ");
    while (i != INVALIDO) {
        printf("%i ", l->A[i].reg.chave);
        i = l->A[i].prox;               /* avança para o próximo da cadeia */
    }
    printf("\"\n");
}

Buscar por elemento

A função de busca deve:

• Receber uma chave do usuário.
• Retornar a posição no arranjo em que o elemento se encontra (caso seja encontrado).
• Retornar INVALIDO caso não haja um registro com essa chave na lista.

Como a lista é ordenada por chave, a busca pode parar antecipadamente: se A[i].reg.chave já for maior ou igual à chave procurada, os elementos seguintes também serão maiores — não há necessidade de continuar.

/* Busca sequencial em lista ordenada — retorna índice no arranjo ou INVALIDO */
int buscaSequencialOrd(LISTA* l, TIPOCHAVE ch) {
    int i = l->inicio;
    while (i != INVALIDO && l->A[i].reg.chave < ch)
        i = l->A[i].prox;
    if (i != INVALIDO && l->A[i].reg.chave == ch)
        return i;
    return INVALIDO;
}

Inserção de um elemento

A inserção nesta lista obedece a três regras:

• Os elementos são mantidos em ordem crescente pela chave.
• Não são permitidos elementos com chaves repetidas.
• O novo elemento ocupa a primeira posição disponível no arranjo (primeiro índice da cadeia de disponíveis).

O algoritmo precisa fazer duas coisas ao mesmo tempo: encontrar entre quais elementos o novo será inserido (ordem lógica), e em qual posição física do array ele será colocado (cadeia de disponíveis).

Função auxiliar: obterNo

obterNo retira o primeiro nó da cadeia de disponíveis e retorna seu índice. É o equivalente de um malloc manual — reserva um espaço para uso:

int obterNo(LISTA* l) {
    int resultado = l->dispo;              /* salva índice do 1º disponível   */
    if (l->dispo != INVALIDO)
        l->dispo = l->A[l->dispo].prox;    /* avança dispo para o próximo     */
    return resultado;                      /* INVALIDO se lista estava cheia  */
}

Inserção ordenada — exemplo visual: inserir o 8

Estado inicial: lista com [5, 7, 9]. Vamos inserir o 8. O 8 fica entre o 7 e o 9 — precisamos atualizar o cursor do 7 para apontar para o 8, e o cursor do 8 para apontar para o 9.

Algoritmo de inserção para o valor 8:

1. Percorre a cadeia de uso: A[0]=5 < 8 → avança. A[1]=7 < 8 → avança (ant=1). A[2]=9 ≥ 8 → para (i=2).
2. Não é duplicata (9 ≠ 8).
3. Chama obterNo: retorna índice 3; dispo avança para 4.
4. Grava A[3].reg.chave = 8.
5. Como ant=1 (não é INVALIDO): A[3].prox = A[1].prox = 2; A[1].prox = 3.

Inserção ordenada — código completo

bool inserirElemListaOrd(LISTA* l, REGISTRO reg) {

    /* ── Parte 1: validação e localização ── */

    if (l->dispo == INVALIDO) return false;  /* lista cheia */

    int ant = INVALIDO;                      /* antecessor do ponto de inserção */
    int i   = l->inicio;
    TIPOCHAVE ch = reg.chave;

    /* percorre enquanto a chave da lista for menor que a nova */
    while ((i != INVALIDO) && (l->A[i].reg.chave < ch)) {
        ant = i;
        i   = l->A[i].prox;
    }
    /* elemento duplicado: rejeita inserção */
    if (i != INVALIDO && l->A[i].reg.chave == ch) return false;

    /* ── Parte 2: inserção física e ajuste de cursores ── */

    i = obterNo(l);          /* pega o 1º nó disponível               */
    l->A[i].reg = reg;       /* grava o registro no nó obtido         */

    if (ant == INVALIDO) {   /* inserção no início da cadeia de uso   */
        l->A[i].prox = l->inicio;
        l->inicio    = i;
    } else {                 /* inserção no meio ou no final          */
        l->A[i].prox   = l->A[ant].prox;
        l->A[ant].prox = i;
    }
    return true;
}

Exclusão de um elemento

Função auxiliar: devolverNo

Assim como a inserção usa obterNo para reservar um espaço, a exclusão usa devolverNo para devolvê-lo à cadeia de disponíveis. É o equivalente manual do free:

void devolverNo(LISTA* l, int j) {
    l->A[j].prox = l->dispo;   /* j aponta para o antigo 1º disponível */
    l->dispo = j;              /* j passa a ser o novo 1º disponível   */
}

Código da exclusão

A exclusão percorre a cadeia de uso procurando a chave. Ao encontrá-la, desliga o nó da cadeia de uso e o devolve à cadeia de disponíveis via devolverNo:

bool excluirElemLista(LISTA* l, TIPOCHAVE ch) {
    int ant = INVALIDO;
    int i   = l->inicio;

    /* avança enquanto a chave do nó for menor que a buscada */
    while ((i != INVALIDO) && (l->A[i].reg.chave < ch)) {
        ant = i;
        i   = l->A[i].prox;
    }

    /* não encontrou: chegou no fim ou passou da posição esperada */
    if (i == INVALIDO || l->A[i].reg.chave != ch) return false;

    /* desliga o nó da cadeia de uso */
    if (ant == INVALIDO)
        l->inicio = l->A[i].prox;   /* era o primeiro elemento */
    else
        l->A[ant].prox = l->A[i].prox;

    devolverNo(l, i);   /* devolve o nó à cadeia de disponíveis */
    return true;
}

Exemplo completo com todas as operações

O programa a seguir exercita todas as funções implementadas nesta aula. Note que a lista ordena automaticamente os elementos ao inserir, mesmo que os inserimos fora de ordem:

int main() {
    LISTA l;
    REGISTRO r;

    inicializarLista(&l);
    exibirLista(&l);
    printf("Tamanho: %d\n\n", tamanho(&l));

    /* Inserções fora de ordem — a lista se auto-ordena */
    r.chave = 7; inserirElemListaOrd(&l, r);
    r.chave = 3; inserirElemListaOrd(&l, r);
    r.chave = 9; inserirElemListaOrd(&l, r);
    r.chave = 1; inserirElemListaOrd(&l, r);
    r.chave = 5; inserirElemListaOrd(&l, r);
    exibirLista(&l);
    printf("Tamanho: %d\n\n", tamanho(&l));

    /* Inserção com lista cheia */
    r.chave = 11;
    if (!inserirElemListaOrd(&l, r))
        printf("Inserção de 11 recusada: lista cheia\n");

    /* Inserção de duplicata */
    r.chave = 3;
    if (!inserirElemListaOrd(&l, r))
        printf("Inserção de 3 recusada: elemento já existe\n\n");

    /* Busca */
    int pos = buscaSequencialOrd(&l, 9);
    if (pos != INVALIDO)
        printf("Chave 9 encontrada na posição %d do arranjo\n", pos);
    pos = buscaSequencialOrd(&l, 4);
    if (pos == INVALIDO)
        printf("Chave 4 não encontrada\n\n");

    /* Exclusões */
    if (excluirElemLista(&l, 3)) printf("Chave 3 excluída\n");
    if (excluirElemLista(&l, 1)) printf("Chave 1 excluída\n");
    if (!excluirElemLista(&l, 8)) printf("Chave 8 não encontrada\n\n");

    exibirLista(&l);
    printf("Tamanho: %d\n", tamanho(&l));

    return 0;
}

Código-fonte completo

Todas as definições e funções reunidas num único arquivo:

#include <stdio.h>
#include <stdbool.h>

#define MAX      5
#define INVALIDO -1

typedef int TIPOCHAVE;

typedef struct { TIPOCHAVE chave; } REGISTRO;

typedef struct { REGISTRO reg; int prox; } ELEMENTO;

typedef struct {
    ELEMENTO A[MAX];
    int inicio;
    int dispo;
} LISTA;

/* ── Inicialização ── */
void inicializarLista(LISTA* l) {
    int i;
    for (i = 0; i < MAX-1; i++) l->A[i].prox = i + 1;
    l->A[MAX-1].prox = INVALIDO;
    l->inicio = INVALIDO;
    l->dispo  = 0;
}

/* ── Tamanho ── */
int tamanho(LISTA* l) {
    int i = l->inicio, tam = 0;
    while (i != INVALIDO) { tam++; i = l->A[i].prox; }
    return tam;
}

/* ── Exibição ── */
void exibirLista(LISTA* l) {
    int i = l->inicio;
    printf("Lista: \" ");
    while (i != INVALIDO) { printf("%i ", l->A[i].reg.chave); i = l->A[i].prox; }
    printf("\"\n");
}

/* ── Busca ── */
int buscaSequencialOrd(LISTA* l, TIPOCHAVE ch) {
    int i = l->inicio;
    while (i != INVALIDO && l->A[i].reg.chave < ch) i = l->A[i].prox;
    if (i != INVALIDO && l->A[i].reg.chave == ch) return i;
    return INVALIDO;
}

/* ── Auxiliares de nó ── */
int obterNo(LISTA* l) {
    int r = l->dispo;
    if (l->dispo != INVALIDO) l->dispo = l->A[l->dispo].prox;
    return r;
}

void devolverNo(LISTA* l, int j) {
    l->A[j].prox = l->dispo;
    l->dispo = j;
}

/* ── Inserção ── */
bool inserirElemListaOrd(LISTA* l, REGISTRO reg) {
    if (l->dispo == INVALIDO) return false;
    int ant = INVALIDO, i = l->inicio;
    TIPOCHAVE ch = reg.chave;
    while ((i != INVALIDO) && (l->A[i].reg.chave < ch)) { ant = i; i = l->A[i].prox; }
    if (i != INVALIDO && l->A[i].reg.chave == ch) return false;
    i = obterNo(l);
    l->A[i].reg = reg;
    if (ant == INVALIDO) { l->A[i].prox = l->inicio; l->inicio = i; }
    else { l->A[i].prox = l->A[ant].prox; l->A[ant].prox = i; }
    return true;
}

/* ── Exclusão ── */
bool excluirElemLista(LISTA* l, TIPOCHAVE ch) {
    int ant = INVALIDO, i = l->inicio;
    while ((i != INVALIDO) && (l->A[i].reg.chave < ch)) { ant = i; i = l->A[i].prox; }
    if (i == INVALIDO || l->A[i].reg.chave != ch) return false;
    if (ant == INVALIDO) l->inicio = l->A[i].prox;
    else l->A[ant].prox = l->A[i].prox;
    devolverNo(l, i);
    return true;
}

Resumo: o que você precisa saber desta aula