DEV Community

Alex Reis
Alex Reis

Posted on

1 1 1 1 1

Estruturas de Dados: Lista

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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"
Enter fullscreen mode Exit fullscreen mode

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"
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Complexidade O(n).

Referência

Livro Estruturas de Dados e Seus Algoritmos

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more