Em comparação com as listas sequenciais, a representação ligada não necessita de unidades de armazenamento com endereços contíguos. Elementos que são logicamente adjacentes não precisam estar fisicamente próximos. As relações lógicas são mantidas através de ponteiros, permitindo operações de inserção e remoção mais eficientes em alguns casos, mas sacrificando a capacidade de acesso aleatório.

A lista linear representada por encadeamento é conhecida como lista ligada simples. Nela, os elementos são armazenados em nós distribuídos de forma arbitrária. Cada nó contém um campo para o dado e um ponteiro para o nó seguinte, como mostrado na estrutura abaixo:

--------------------------
|  dado  |  próximo   |
--------------------------

typedef struct NoLigado {
    TipoElem dado;
    struct NoLigado *prox;
} NoLigado, *ListaLigada;

Um ponteiro de cabeça, normalmente chamado de L, identifica a lista, apontando para o seu início. Frequentemente, é utilizado um nó cabeça, um nó adicional antes do primeiro nó de dados, para simplificar operações. Quando presente, o ponteiro de cabeça aponta para o nó cabeça; caso contrário, aponta diretamente para o primeiro nó de dados.

Operações Básicas

Inicialização

Recomenda-se utilizar nó cabeça em muitas implementações, como em problemas de algoritmos.

bool InicializarLista(ListaLigada &L) {
    L = (NoLigado*)malloc(sizeof(NoLigado));
    L->prox = NULL;
    return true;
}

Comprimento da Lista

O comprimento é determinado por travessia comlpeta, contando todos os nós.

int Comprimento(ListaLigada L) {
    int cont = 0;
    NoLigado *noAtual = L;
    while (noAtual->prox != NULL) {
        noAtual = noAtual->prox;
        cont++;
    }
    return cont;
}

A complexidade de tempo é O(n).

Busca por Índice

NoLigado *ObterElemento(ListaLigada L, int posicao) {
    NoLigado *iterador = L;
    int contador = 0;
    while (iterador != NULL && contador < posicao) {
        iterador = iterador->prox;
        contador++;
    }
    return iterador;
}

Complexidade de tempo: O(n).

Busca por Valor

NoLigado *LocalizarPorValor(ListaLigada L, TipoElem valor) {
    NoLigado *iterador = L->prox;
    while (iterador != NULL && iterador->dado != valor)
        iterador = iterador->prox;
    return iterador;
}

Complexidade de tempo: O(n).

Inserção de Nó

Existem abordagens de inserção anterior e posterior. Para inserir na posição i, primeiro localiza-se o nó i-1.

Inserção posterior:

bool InserirPosicao(ListaLigada &L, int pos, TipoElem elem) {
    NoLigado *pred = L;
    int idx = 0;
    while (pred != NULL && idx < pos - 1) {
        pred = pred->prox;
        idx++;
    }
    if (pred == NULL) return false;
    NoLigado *novoNo = (NoLigado*)malloc(sizeof(NoLigado));
    novoNo->dado = elem;
    novoNo->prox = pred->prox;
    pred->prox = novoNo;
    return true;
}

Complexidade de tempo: O(n), devido à busca.

Inserção anterior: pode ser realizada inserindo após o nó atual e trocando os dados.

    novoNo->prox = noAlvo->prox;
    noAlvo->prox = novoNo;
    TipoElem temp = noAlvo->dado;
    noAlvo->dado = novoNo->dado;
    novoNo->dado = temp;

Sem contar a busca, a complexidade é O(1).

Remoção de Nó

Após validação, localiza-se o nó predecessor e remove-se o nó seguinte.

bool RemoverPosicao(ListaLigada &L, int pos, TipoElem &elemRemovido) {
    NoLigado *antecessor = L;
    int idx = 0;
    while (antecessor->prox != NULL && idx < pos - 1) {
        antecessor = antecessor->prox;
        idx++;
    }
    if (antecessor->prox == NULL || idx > pos - 1) return false;
    NoLigado *noRemovido = antecessor->prox;
    elemRemovido = noRemovido->dado;
    antecessor->prox = noRemovido->prox;
    free(noRemovido);
    return true;
}

Complexidade de tempo: O(n).

Alternativamente, para remover o sucessor de um nó p:

    NoLigado *sucessor = p->prox;
    p->dado = p->prox->dado;
    p->prox = sucessor->prox;
    free(sucessor);

Construção por Inserção no Início

Partindo de uma lista vazia, novos nós são inseridos após o nó cabeça. A ordem dos dados inseridos é invertida na lista resultante.

ListaLigada ConstruirPorInicio(ListaLigada &L) {
    NoLigado *s; int valor;
    L = (NoLigado*)malloc(sizeof(NoLigado));
    L->prox = NULL;
    scanf("%d", &valor);
    while (valor != 9999) {
        s = (NoLigado*)malloc(sizeof(NoLigado));
        s->dado = valor;
        s->prox = L->prox;
        L->prox = s;
        scanf("%d", &valor);
    }
    return L;
}

Complexidade total: O(n), pois cada inserção é O(1).

Construção por Inserção no Final

Um ponteiro para o último nó mantém referência constante, inserindo novos nós no final. A ordem dos dados é preservada.

ListaLigada ConstruirPorFinal(ListaLigada &L) {
    int valor;
    L = (NoLigado*)malloc(sizeof(NoLigado));
    NoLigado *s, *cauda = L;
    scanf("%d", &valor);
    while (valor != 9999) {
        s = (NoLigado*)malloc(sizeof(NoLigado));
        s->dado = valor;
        cauda->prox = s;
        cauda = s;
        scanf("%d", &valor);
    }
    cauda->prox = NULL;
    return L;
}

Complexidade de tempo semelhante: O(n).

Lista Ligada Dupla

Os nós possuem dois ponteiros: um para o predecessor e outro para o sucessor. Os nós extremos têm ponteiros nulos. As operações envolvem a modificação de dois ponteiros, mas a complexidade é similar à da lista simples.

-------------------------------
| anterior | dado | próximo |
-------------------------------

Lista Circular

A lista circular difere da simples pelo fato de o último nó apontar de volta para o nó cabeça, em vez de NULL. Operações envolvendo o nó final requerem ajustes específicos. Também existe a variante de lista duplamente ligada circular.

Lista Estática

Uma lista estática utiliza um bloco contíguo de memória pré-alocada. Os ponteiros são representados por índices relativos no array, chamados de cursores.

Exemplo de representação:

O fim da lista é indicado por próximo == -1. Inserções e remoções envolvem apenas alterações nos cursores, sem deslocamento de elementos.