Uma Lista linear é um conjunto de n >= 0 elementos L[1], L[2], ..., L[n]. Tal que:

• se n > 0, L[1] é o primeiro elemento
• para 1 <= k <= n, o nó L[k] é precidido pelo L[k-1].

As operações mais frequentes em listas são a busca, a inclusão e a remoção de um determinado elemento.

Se as inserções e remoções são permitidas apenas nas extremidades da lista, ela recebe o nome de deque (double end queue). Se as inserções e as remoções são realizadas somente em um extremo, a lista é chamada pilha, sendo denominada fila no caso em que inserções são realizadas em um extremo e remoções em outro.

O tipo de armazenamento de uma lista linear pode ser classificado de acordo com a posição relativa (sempre contígua ou não) na memória de dois nós consecutivos na lista.

Alocação sequencial

A maneira mais simples de se manter uma lista linear na memória do computador é colocar seus nós em posições contíguas. Nesse caso, o endereço real do (j + 1)-ésimo nó da lista se encontra c unidades adiante daquele correspondente ao j-ésimo. A constante c é o número de palavras de memória que cada nó ocupa.

Seja uma lista linear. Cada nó é formado por campos, que armazenam as características distintas dos elementos da lista. Além disso, cada nó da lista possui, geralmente, um identificador, denominado chave. Para evitar ambiguidades supõe-se que todas as chaves são distintas. Os nós podem ser ordenadso ou não, segundo suas chaves.

Busca por um nó conhecendo sua chave

    busca1(x):
        i := 1; busca1 := 0
        enquanto i <= n faça
            se L[i].chave == x então
                busca1 := i
                i := n+1
            senão
                i := i+1

Algoritmo que cria um novo nó com a chave procurada

    busca(x):
        L[n+1] := x; i := 1
        enquanto L[i].chave != x faça
            i := i+1
        se i != n+1
            busca := i
        senão
            busca := 0

Ambos algoritmos tem complexidade do pior caso O(n). Mas o segundo é mais rápido por fazer menos comparações.

Busca por um elemento na lista ordenada

    busca-ordenada(x):
        L[n+1] := x; i := 1
        enquanto L[i].chave < x faça
            i := i+1
        se i == n+1 ou L[i].chave != x então
            busca-ordenada := 0
        senão
            busca-ordenada := i

Complexidade O(n).

Busca Binária

    busca-bin(x):
        inf := 1; sup := n; busca-bin := 0
        enquanto inf <= sup faça
            meio := (inf+sup)/2
            se L[meio].chave == x então
                busca-bin:=meio
                inf := sup+1
            senão se L[meio].chave < x então
                inf := meio+1
            senão
                sup := meio-1

Complexidade O(log n).

As operações de inserção e remoção utilizam a busca, tanto para evitar chaves duplicadas quanto para encontrar o elemento a ser removido. Os algoritmos de inserir e remover a seguir consideram uma lista não ordenada. A memória pressuposta disopnível tem M posições (M+1 pois é necessária uma posição extra para a busca).

Inserção de um nó com chave x

    se n < M então
        se busca(x) == 0 então 
            L[n+1] := novo-valor
            n := n+1
        senão "elemento já existe"
    senão overflow

Remoção de um nó com chave x

    se n != 0 então
        indice := busca(x)
        se indice != 0 então
            valor-recuperado:=L[indice]
            para i := indice até n-1 faça
                L[i] := L[i+1]
            n := n-1
        senão "elemento não existe"
    senão underflow

Complexidade de ambos é O(n).

Alocação encadeada

Também conhecida por aloção dinamica uma vez que as posições de memória são alocadas conforme o necessário. Os nós de uma lista então encontram-se dispersos na memória e são interligados por ponteiros.

Qualquer estrutura, inclusive listas, que seja armazenada em alocação encadeada requer o uso de um ponteiro que indique o endereço de seu primeiro nó. O percurso de uma lista é feito então a partir desse ponteiro.

Imprimir uma lista encadeada
*ptlista é o ponteiro para o primeiro nó.

    pont := ptlista
    enquanto pont != null faça
        imprimir(pont->.info)
        pont := pont->.prox

Busca em uma lista ordenada
*pont é retornado apontando para o elemento procurado, ant aponta para o anterior e ptr vai percorrer a lista

    busca-enc(x, pont, ant)
        ant := ptlista; pont := null
        ptr := ptlista->.prox
        enquanto ptr != null faça
            se ptr->.chave < x então
                ant := ptr
                ptr := ptr->.prox
            senão se ptr->.chave == x então
                pont := ptr
                ptr := null

Complexidade O(n).

Inserção de um nó novo

    busca-enc(x, pont, ant)
    se pont == null então
        // alocar pt
        pt->.info := novo-valor
        pt->.chave := x
        pt->.prox := ant->.prox
        ant->.prox := pt
    senão "elemento já existe"

Remoção de um nó

    busca-enc(x, pont, ant)
    se pont != null então
        ant->.prox := pont->.prox

        // desalocar pt
    senão "nó não encontrado"

Complexidade de ambos é O(n).

Busca em uma lista não ordenada

    busca-enc(x, pont, ant)
        ant := ptlista; pont := null
        ptr := ptlista->.prox
        enquanto ptr != null faça
            se ptr->.chave == x então
                pont := ptr
                ptr := null
            senão
                ant := ptr
                ptr := ptr->.prox

Complexidade O(n).

Referência

Livro Estruturas de Dados e Seus Algoritmos