Aula 33 – Inserção na Lista Sequencial

O Desafio de Inserir no Meio

Inserir no final de uma lista sequencial é simples: coloca na próxima posição livre e incrementa o contador. Mas e se precisarmos inserir no meio?

Imagine a lista [9, 3, 4, 1] e queremos inserir o elemento 12 na posição 2 (entre o 3 e o 4). O resultado esperado é [9, 3, 12, 4, 1].

Problema: A posição 2 já está ocupada pelo elemento 4. Não podemos simplesmente sobrescrever — precisamos primeiro abrir espaço deslocando todos os elementos a partir da posição 2 uma casa para a direita.

O Algoritmo: Deslocar para a Direita

O algoritmo tem 3 etapas:

Etapa 1 — Verificar validade

A lista está cheia? O índice i é válido (entre 0 e nroElem)?

Etapa 2 — Deslocar para a direita

Do último elemento até a posição i, mover cada elemento uma posição para frente.

Etapa 3 — Inserir e incrementar

Colocar o novo registro em A[i] e incrementar nroElem.

Visualizando para inserir 12 na posição i=2 na lista [9, 3, 4, 1]:

Passo	Índice 0	Índice 1	Índice 2	Índice 3	Índice 4
Lista inicial	9	3	4	1	—
j=4: A[4] ← A[3]	9	3	4	1	1
j=3: A[3] ← A[2]	9	3	4	4	1
j=2: condição j>i falsa — para	9	3	4	4	1
A[2] = 12, nroElem++	9	3	12	4	1

A Função `inserirElemLista`

bool inserirElemLista(LISTA* l, REGISTRO reg, int i) {
    int j;

    // Verifica: lista cheia OU índice fora do intervalo válido [0, nroElem]
    if ((l->nroElem >= MAX) || (i < 0) || (i > l->nroElem))
        return false;

    // Desloca elementos da posição nroElem até i+1 uma casa para a direita
    for (j = l->nroElem; j > i; j--)
        l->A[j] = l->A[j - 1];

    // Insere o novo registro na posição i
    l->A[i] = reg;
    l->nroElem++;
    return true;
} /* inserirElemLista */

Por que o for começa em j = nroElem? O último elemento válido está em nroElem - 1, então ele precisa ir para nroElem. Começar em nroElem e fazer A[j] = A[j-1] realiza exatamente esse movimento.

Porque deslocar da direita para a esquerda? Se deslocássemos da esquerda para a direita (de i até nroElem), sobrescreveríamos cada elemento antes de movê-lo. O deslocamento deve começar pelo final para preservar todos os valores.

Comparação com Java

Em Java, o ArrayList faz exatamente o mesmo deslocamento internamente — mas esconde toda essa complexidade:

☕ Java

ArrayList<Integer> lista =
    new ArrayList<>();
lista.add(9);
lista.add(3);
lista.add(4);
lista.add(1);

// Inserir 12 na posição 2:
lista.add(2, 12);

// Java faz o deslocamento
// internamente — você não vê
System.out.println(lista);
// [9, 3, 12, 4, 1]

⚙️ C

LISTA lista;
inicializarLista(&lista);
REGISTRO reg;
reg.chave=9; inserirElemLista(&lista,reg,0);
reg.chave=3; inserirElemLista(&lista,reg,1);
reg.chave=4; inserirElemLista(&lista,reg,2);
reg.chave=1; inserirElemLista(&lista,reg,3);

// Inserir 12 na posição 2:
reg.chave = 12;
inserirElemLista(&lista, reg, 2);

exibirLista(&lista);
// Lista: " 9 3 12 4 1 "

O ArrayList é mais poderoso: Além do deslocamento, o ArrayList do Java também redimensiona automaticamente quando fica cheio (cria um array maior internamente). Nossa lista em C tem capacidade fixa — ao atingir MAX elementos, inserirElemLista retorna false.

Custo da Operação: Por que Listas Sequenciais São Lentas para Inserção

No pior caso (inserir na posição 0), precisamos deslocar todos os nroElem elementos. Isso torna a inserção uma operação O(n) — linear em relação ao tamanho da lista.

Onde inserir	Deslocamentos	Caso
Posição final (`i = nroElem`)	0	Melhor caso — O(1)
Posição do meio	nroElem/2	Caso médio — O(n/2)
Posição inicial (`i = 0`)	nroElem	Pior caso — O(n)

Em Java, ArrayList.add(index, value) tem o mesmo custo O(n) para inserções no meio ou no início. Se você precisa de inserções frequentes no início ou no meio, o LinkedList do Java (ou a lista ligada em C) é mais eficiente — mas perde no acesso aleatório.