Módulo 02 Estruturas Sequenciais

Lista Sequencial

Uma lista sequencial representa uma coleção ordenada de elementos armazenados em posições consecutivas. Diferentemente de um array usado diretamente, a lista mantém também um tamanho lógico, distinguindo as posições que realmente pertencem à lista da capacidade total disponível. A partir dessa ideia, podemos implementar um verdadeiro Tipo Abstrato de Dados Lista.

Objetivo 01Distinguir tamanho e capacidade

Objetivo 02Visualizar deslocamentos

Objetivo 03Implementar o TAD em C++17

Uma sequência com regras próprias

O Que é uma Lista Sequencial?

Uma lista sequencial é um TAD em que os elementos são armazenados em uma área contígua e ocupam as primeiras posições disponíveis, sem “buracos” entre eles. Além do vetor que armazena os dados, mantemos uma variável que informa quantos elementos pertencem logicamente à lista.

Memória contígua

Os elementos válidos ocupam posições consecutivas.

Tamanho lógico

A variável tamanho indica quantos elementos existem na lista.

Capacidade

O armazenamento pode possuir mais posições do que a lista utiliza atualmente.

TAD Lista

As operações são oferecidas por uma interface: inserir, remover, buscar, acessar...

Exemplo: se a capacidade é 10 e o tamanho lógico é 6, somente os índices 0 até 5 pertencem à lista. As posições de 6 até 9 são apenas espaço reservado.

Lista sequencial não significa lista encadeada

Na lista sequencial, os elementos ficam em posições contíguas e são acessados por índice. Na lista encadeada, os nós podem estar dispersos na memória e são conectados por referências.

Por que chamar de TAD?

Porque o usuário da estrutura não precisa manipular diretamente o vetor interno. Ele utiliza operações como inserir, remover e consultar, enquanto a implementação mantém as regras da lista.

dados[] + tamanho

Representação Interna

A implementação clássica utiliza um array para armazenar os elementos e uma variável inteira para controlar o tamanho lógico. Essa pequena diferença transforma o array em uma estrutura com estado e operações próprias.

0 ... tamanho-1 = lista válida tamanho ... capacidade-1 = espaço reservado

A lista possui 6 elementos e capacidade para 10.

Invariante 01 0 ≤ tamanho ≤ capacidade

O tamanho nunca pode ser negativo nem ultrapassar a área reservada.

Invariante 02 Elementos em [0, tamanho)

Os elementos válidos permanecem agrupados nas primeiras posições.

Invariante 03 Sem buracos internos

Uma remoção desloca os elementos posteriores para preservar a sequência compacta.

Mantendo a lista compacta

Inserção, Remoção, Busca e Acesso

O acesso por posição aproveita a representação contígua. Já inserções e remoções internas precisam deslocar elementos para manter o invariante de que a lista ocupa sempre as primeiras posições.

Escolha uma operação.

Acesso por posição

Acessar a posição i é O(1), desde que 0 ≤ i < tamanho. A estrutura pode verificar se o índice pertence à parte válida da lista.

Inserção

Antes de inserir, verificamos se a lista está cheia e se a posição é válida. Depois, deslocamos os elementos posteriores para a direita, escrevemos o novo valor e incrementamos tamanho.

Remoção

Após remover uma posição, os elementos seguintes avançam para a esquerda. No final, decrementamos tamanho.

Busca

Em uma lista não ordenada, a busca por valor normalmente é linear. O pior caso exige examinar todos os elementos válidos.

O armazenamento pode ser o mesmo; a abstração não

Array, Vetor Dinâmico e Lista Sequencial

Essas estruturas podem utilizar memória contígua, mas representam conceitos diferentes. A principal diferença está nas regras que a estrutura oferece e em quem controla seu estado.

Característica	Array tradicional	Lista sequencial clássica	std::vector do C++
Memória contígua	Sim	Sim	Sim
Tamanho lógico	Não necessariamente separado	Controlado explicitamente	Gerenciado por `size()`
Capacidade	Fixa	Normalmente fixa na implementação clássica	Pode crescer dinamicamente
Inserção / remoção	Implementadas manualmente	Fazem parte das operações do TAD	Métodos da biblioteca
Controle de invariantes	Responsabilidade do programa	Responsabilidade da implementação da lista	Responsabilidade do contêiner

Importante: “Lista Sequencial” descreve uma forma de implementar o TAD Lista. O array é o mecanismo de armazenamento; a lista é a abstração construída sobre ele.

Custos da representação contígua

Complexidade das Operações

Operação	Complexidade	Motivo
Acessar posição	O(1)	Endereço calculado diretamente pelo índice.
Alterar posição	O(1)	Mesmo princípio do acesso.
Buscar valor	O(n)	Lista não ordenada pode exigir percurso completo.
Inserir no fim	O(1)	Se houver capacidade, escreve em `dados[tamanho]`.
Inserir no início	O(n)	Desloca todos os elementos.
Remover do fim	O(1)	Basta reduzir o tamanho lógico.
Remover do início	O(n)	Todos os elementos restantes avançam.
Espaço	O(capacidade)	O bloco é reservado mesmo quando parte está livre.

Implementando o TAD

Lista Sequencial em C++17

A implementação abaixo usa um array fixo para armazenamento e encapsula o controle de tamanho e as operações dentro de uma classe.

Estrutura básica

#include <stdexcept>
#include <vector>

class ListaSequencial {
private:
    std::vector<int> dados;

public:
    void inserir(int posicao, int valor) {
        if (posicao < 0 || posicao > static_cast<int>(dados.size()))
            throw std::out_of_range("posição inválida");

        dados.insert(dados.begin() + posicao, valor);
    }

    int remover(int posicao) {
        if (posicao < 0 || posicao >= static_cast<int>(dados.size()))
            throw std::out_of_range("posição inválida");

        int removido = dados[posicao];
        dados.erase(dados.begin() + posicao);
        return removido;
    }

    int buscar(int valor) const {
        for (int i = 0; i < static_cast<int>(dados.size()); ++i)
            if (dados[i] == valor) return i;
        return -1;
    }

    int obter(int posicao) const {
        return dados.at(posicao);
    }
};

Inserção em uma posição

void inserir(int posicao, int valor) {
    if (posicao < 0 || posicao > static_cast<int>(dados.size()))
        throw std::out_of_range("posição inválida");

    dados.insert(dados.begin() + posicao, valor);
}

Remoção

int remover(int posicao) {
    if (posicao < 0 || posicao >= static_cast<int>(dados.size()))
        throw std::out_of_range("posição inválida");

    int removido = dados[posicao];
    dados.erase(dados.begin() + posicao);
    return removido;
}

Busca linear

int buscar(int valor) const {
    for (int i = 0; i < static_cast<int>(dados.size()); ++i)
        if (dados[i] == valor) return i;

    return -1;
}

Acesso seguro

int obter(int posicao) const {
    if (posicao < 0 || posicao >= static_cast<int>(dados.size()))
        throw std::out_of_range("posição inválida");

    return dados[posicao];
}

Por que posição de inserção aceita tamanho?

Se a lista possui tamanho 6, as posições válidas para acesso são 0 a 5, mas inserir na posição 6 significa acrescentar o elemento ao final da lista.

Por que não “apagamos” a última célula após remover?

O que define quais posições pertencem à lista é a variável tamanho. Depois de decrementá-la, a antiga última posição deixa de ser logicamente válida, independentemente do valor residual que permaneça fisicamente no array.

Lista sequencial pode ser dinâmica?

Sim. A ideia de lista sequencial exige contiguidade lógica/física dos elementos, não necessariamente capacidade fixa. É possível usar realocação dinâmica, como ocorre em estruturas semelhantes ao std::vector do C++.

Modelo mental

O Que Você Precisa Guardar

Armazenamento Elementos em posições contíguas.

Tamanho Define a parte válida do array.

Inserir / remover Preserva a lista sem buracos.

TAD Array interno + regras + operações.

Resumo: a Lista Sequencial mostra uma diferença fundamental de Estruturas de Dados: estrutura não é apenas onde os dados estão armazenados, mas também as regras e operações que mantêm esses dados organizados.