Listas Duplamente Encadeadas

• O Quê São Listas Encadeadas?
• Como Implementar Uma Lista Duplamente Encadeada?
• Quais São As Operações Básicas de Uma Lista Duplamente Encadeada?

O Quê São Listas Encadeadas?

Uma lista duplamente encadeada é um tipo de lista encadeada onde suas células são encadeadas em ambos os sentidos. Esse tipo de lista suporta de forma eficiente a navegabilidade reversa (ex. da direita para a esquerda), bem como a inserção e remoção de elementos antecessores a um outro na lista.

Como Implementar Uma Lista Duplamente Encadeada?

• l.celulas[]: células que armazenam os elementos da lista duplamente encadeada.
• l.primeiro: um ponteiro que referencia o primeiro elemento da lista duplamente encadeada.
• l.ultimo: um ponteiro que referencia o último elemento da lista duplamente encadeada.
• l.comprimento: um inteiro que conta o número de elementos na lista duplamente encadeada.

Quais São As Operações Básicas de Uma Lista Duplamente Encadeada?

• comprimento() retorna o número de elementos em uma lista duplamente encadeada.
• primeiro() inspeciona o primeiro elemento de uma lista duplamente encadeada.
• ultimo() inspeciona o último elemento de uma lista duplamente encadeada.
• inserir-sucessor() insere um elemento como sucessor de outro em uma lista duplamente encadeada.
• remover-sucessor() remove o sucessor de um elemento em uma lista duplamente encadeada.
• inserir-antecessor() insere um elemento como antecessor de outro em uma lista duplamente encadeada.
• remover-antecessor() remove o antecessor de um elemento em uma lista duplamente encadeada.

Operação Comprimento

1. Retorne o valor de l.comprimento.

Algoritmo Comprimento

comprimento(l: Lista)
    RETORNE l.comprimento

Operação Primeiro

1. Verifique se a lista l está vazia. Em caso afirmativo, vá para o passo 2. Caso contrário, vá para o passo 3.
2. A lista está vazia, então retorne"lista vazia".
3. Retorne o elemento referenciado pelo ponteiro de primeiro da lista l.primeiro.

Algoritmo Primeiro

primeiro(l: Lista)
    SE l está vazia
        RETORNE "lista vazia"
    SENÃO
        RETORNE l.celulas[l.primeiro]

Operação Último

1. Verifique se a lista l está vazia. Em caso afirmativo, vá para o passo 2. Caso contrário, vá para o passo 3.
2. A lista está vazia, então retorne"lista vazia".
3. Retorne o elemento referenciado pelo ponteiro de último da lista l.ultimo.

Algoritmo Último

ultimo(l: Lista)
    SE l está vazia
        RETORNE "lista vazia"
    SENÃO
        RETORNE l.celulas[l.ultimo]

Operação Inserir Sucessor

1. Crie uma nova célula q na lista l.
2. Armazene e na célula q.
3. Encadeie o sucessor de p como o sucessor de q.
4. Encadeie p como antecessor de q.
5. Encadeie q como o o antecessor do sucessor de p
6. Encadeie q como o sucessor de p.
7. Incremente em uma unidade o contador de comprimento da lista l.comprimento.
8. Se q é a última célula da lista l, atualize l.ultimo para referenciar q.

Algoritmo Inserir Sucessor

inserir-sucessor(l: Lista, p: Célula, e: Elemento)
    q = referência para nova célula
    l.celulas[q] = e
    q.sucessor = p.sucessor
    q.antecessor = p
    p.sucessor.antecessor = q
    p.sucessor = q
    l.comprimento = l.comprimento + 1
    SE q é a última célula de l
        l.ultimo = q

Operação Remover Sucessor

1. Verifique se a lista l está vazia. Em caso afirmativo, vá para o passo 2. Caso contrário, vá para o passo 3.
2. A lista está vazia, então retorne "lista vazia".
3. Salve em q uma referência para o sucessor de p.
4. Salve em e o elemento armazenado em q.
5. Encadeie p como o antecessor do sucessor de q.
6. Encadeie o sucessor de q como sucessor de p.
7. Decremente em uma unidade o contador de comprimento da lista l.comprimento.
8. Se p é a última célula da lista l, atualize l.ultimo para referenciar p.
9. Retorne o elemento e.

Algoritmo Remover Sucessor

remover-sucessor(l: Lista, p: Célula)
    SE l está vazia
        RETORNE "lista vazia"
    SENÃO
        q = p.sucessor
        e = l.celulas[q]
        q.sucessor.antecessor = p
        p.sucessor = q.sucessor
        l.comprimento = l.comprimento - 1
        SE p é a última célula de l
            l.ultimo = p
        RETORNE e

Operação Inserir Antecessor

1. Crie uma nova célula q na lista l.
2. Armazene e na célula q.
3. Encadeie p como o sucessor de q.
4. Encadeie o antecessor de p como antecessor de q.
5. Encadeie q como sucessor do antecessor de p.
6. Encadeie q como antecessor de p.
7. Incremente em uma unidade o contador de comprimento da lista l.comprimento.
8. Se q é a primeira célula da lista l, atualize l.primeiro para referenciar q.

Algoritmo Inserir Antecessor

inserir-antecessor(l: Lista, p: Célula, e: Elemento)
    q = referência para nova célula
    l.celulas[q] = e
    q.sucessor = p
    q.antecessor = p.antecessor
    p.antecessor.sucessor = q
    p.antecessor = q
    l.comprimento = l.comprimento + 1
    SE q é a primeira célula de l
        l.primeiro = q

Operação Remover Antecessor

1. Verifique se a lista l está vazia. Em caso afirmativo, vá para o passo 2. Caso contrário, vá para o passo 3.
2. A lista está vazia, então retorne "lista vazia".
3. Salve em q uma referência para o antecessor de p.
4. Salve em e o elemento armazenado em q.
5. Encadeie p como sucessor do antecessor de q.
6. Encadeie o antecessor de q como antecessor de p.
7. Decremente em uma unidade o contador de comprimento da lista l.comprimento.
8. Se p é a primeira célula da lista l, atualize l.primeiro para referenciar p.
9. Retorne o elemento e.

Algoritmo Remover Antecessor

remover-antecessor(l: Lista, p: Célula)
    SE l está vazia
        RETORNE "lista vazia"
    SENÃO
        q = p.sucessor
        e = l.celulas[q]
        q.antecessor.sucessor = p
        p.antecessor = q.antecessor
        l.comprimento = l.comprimento - 1
        SE p é a primeira célula de l
            l.ultimo = p
        RETORNE e