Aula 32 – Lista Linear Sequencial: Estrutura e Operações Básicas

O que é uma Lista Linear Sequencial?

Uma lista linear sequencial é uma estrutura de dados onde os elementos estão armazenados de forma contígua na memória, na mesma ordem em que o usuário os vê. Cada elemento (exceto o primeiro e o último) tem exatamente um predecessor e um sucessor.

Ela é implementada com um array de tamanho fixo mais um contador que registra quantas posições estão ocupadas:

Conceito	Em C (nossa lista)	Em Java (equivalente)
Capacidade máxima	`MAX = 50` (constante fixa)	`array.length` ou `new int[50]`
Tamanho atual	`nroElem` (campo da struct)	`arrayList.size()`
Acesso a elemento	`l->A[i].chave`	`lista.get(i)`
Tamanho dinâmico?	❌ Não — fixo em MAX	✅ ArrayList cresce automaticamente

Lista Sequencial vs ArrayList: Nossa lista se parece mais com um int[] de Java do que com um ArrayList: o espaço é reservado de uma vez e nunca cresce. O nroElem faz o papel do .size() do ArrayList — controla quantas posições estão de fato em uso.

A Estrutura Completa do Projeto

Com tudo que aprendemos nas aulas 29, 30 e 31, montamos a base de todos os algoritmos que virão:

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

#define MAX  50    // capacidade máxima da lista
#define ERRO -1    // código de retorno para operações inválidas

typedef int TIPOCHAVE;           // apelido semântico para o tipo da chave

typedef struct {
    TIPOCHAVE chave;             // identificador do registro
    // outros campos poderiam estar aqui: char nome[50], float salario...
} REGISTRO;

typedef struct {
    REGISTRO A[MAX + 1];         // +1 reserva espaço para sentinela (Aula 34)
    int      nroElem;            // quantos elementos estão usados (0 a MAX)
} LISTA;

Por que #include <stdbool.h>? Algumas funções retornam bool (true/false) para indicar sucesso ou falha. Este header, disponível desde C99, define esse tipo. Sem ele, teríamos que usar int com 0 e 1.

Função 1 — `inicializarLista`

A primeira coisa a fazer com qualquer lista é inicializá-la. Sem isso, nroElem contém "lixo" de memória e todas as outras funções se comportarão de forma imprevisível.

void inicializarLista(LISTA* l) {
    l->nroElem = 0;
} /* inicializarLista */

Simples assim. Ela recebe um ponteiro para a lista (LISTA*, como aprendemos na Aula 31) e zera o contador. O array A não precisa ser "limpo" — posições além de nroElem são simplesmente ignoradas.

Em Java, o equivalente seria o construtor: Lista() { this.nroElem = 0; } — chamado automaticamente com new Lista(). Em C, não há construtor automático; você precisa chamar inicializarLista(&lista) explicitamente antes de usar a lista.

Função 2 — `exibirLista`

Percorre os nroElem primeiros elementos do array e imprime suas chaves:

void exibirLista(LISTA* l) {
    int i;
    printf("Lista: \" ");
    for (i = 0; i < l->nroElem; i++)
        printf("%i ", l->A[i].chave);  // TIPOCHAVE = int, então %i
    printf("\"\n");
} /* exibirLista */

Note que o for vai de 0 até nroElem - 1 (a condição é i < nroElem). Posições de nroElem em diante existem no array mas contêm lixo — por isso as ignoramos.

Funções 3 e 4 — `tamanho` e `tamanhoEmBytes`

/* Retorna quantos elementos estão atualmente na lista */
int tamanho(LISTA* l) {
    return l->nroElem;
} /* tamanho */

/* Retorna o tamanho total da struct LISTA em bytes */
int tamanhoEmBytes(LISTA* l) {
    return sizeof(LISTA);
} /* tamanhoEmBytes */

Tamanho lógico ≠ tamanho físico: tamanho() retorna quantos elementos estão em uso (de 0 a MAX). tamanhoEmBytes() retorna o tamanho total da struct em memória — que é sempre o mesmo, independente de quantos elementos estejam preenchidos, pois a alocação é estática.

Função C	Equivalente Java	O que retorna
`tamanho(&l)`	`arrayList.size()`	Elementos em uso (lógico)
`tamanhoEmBytes(&l)`	Sem equivalente direto	Bytes ocupados pela struct na memória
`MAX`	`array.length`	Capacidade máxima (físico)

Funções 5, 6 e 7 — Acesso a Elementos

Três funções para recuperar a chave de elementos específicos:

/* Retorna a chave do primeiro elemento (ou ERRO se lista vazia) */
TIPOCHAVE primeiroElem(LISTA* l) {
    if (l->nroElem > 0) return l->A[0].chave;
    else return ERRO;
} /* primeiroElem */

/* Retorna a chave do último elemento (ou ERRO se lista vazia) */
TIPOCHAVE ultimoElem(LISTA* l) {
    if (l->nroElem > 0) return l->A[l->nroElem - 1].chave;
    else return ERRO;
} /* ultimoElem */

/* Retorna a chave do n-ésimo elemento (ou ERRO se índice inválido) */
TIPOCHAVE enesimoElem(LISTA* l, int n) {
    if ((n >= 0) && (n < l->nroElem)) return l->A[n].chave;
    else return ERRO;
} /* enesimoElem */

Porque l->A[l->nroElem - 1]? Arrays em C começam no índice 0. Se a lista tem 5 elementos, eles ocupam os índices 0, 1, 2, 3 e 4. O último elemento está em nroElem - 1 = 4. Em Java seria lista.get(lista.size() - 1).

Testando as Funções: Mini-Programa

int main() {
    LISTA lista;
    inicializarLista(&lista);

    exibirLista(&lista);  // Lista: ""
    printf("Tamanho:   %d\n", tamanho(&lista));         // 0
    printf("Em bytes:  %d\n", tamanhoEmBytes(&lista));   // ex.: 204 bytes

    // Inserção direta para testar (veremos inserirElemLista na Aula 33)
    REGISTRO reg;
    reg.chave = 9;  lista.A[0] = reg; lista.nroElem++;
    reg.chave = 3;  lista.A[1] = reg; lista.nroElem++;
    reg.chave = 7;  lista.A[2] = reg; lista.nroElem++;

    exibirLista(&lista);   // Lista: " 9 3 7 "
    printf("Primeiro: %d\n", primeiroElem(&lista));   // 9
    printf("Ultimo:   %d\n", ultimoElem(&lista));      // 7
    printf("2o elem:  %d\n", enesimoElem(&lista, 1));  // 3 (índice 1)

    return 0;
}

Lista: " "

Tamanho: 0

Em bytes: 204

Lista: " 9 3 7 "

Primeiro: 9

Ultimo: 7

2o elem: 3

O que é uma Lista Linear Sequencial?

A Estrutura Completa do Projeto

Função 1 — inicializarLista

Função 2 — exibirLista