Doubly Linked List

Em uma Doubly Linked List, (que a partir de agora vou chamar de DLL) todos os nodes têm um ponteiro para o node ao qual estão conectados.
Isso significa que cada node está conectado a dois nodes, e podemos avançar para o próximo node ou retroceder até o node anterior.

DLL permitem operações de insert, deleting e, obviamente, de traversing.

E Para fins de manter o exemplo de linhas temos agora o que seria uma representação de estações de trem.
Enquanto que a single linked list representa um monotrilho aqui temos duas ligações.

Quem nunca voltou da paulista mais loco e que o coringa chegou na consolação e se perguntou "o meu é sentido vila madalena ou é sentido vila prudente? E o sentido da vida?"

Listas duplamente ligadas são exatamente iguais a estações de metrô pois através de um Node você pode seguir para o próximo ou para o anterior pois temos ponteiros nas duas direções.

// Estacao struct = Node
type Estacao struct {
    // property
    nome string
    // nextNode
    estacaoSeguinte *Estacao
    // previousNode
    estacaoAnterior *Estacao
}

Assim como na single LinkedList temos o mesmo conceito de head e tail então a struct é exatamente igual.

// Metro = Doubly linked list
type Metro struct {
    // head
    inicioDaLinha *Estacao
    // tail
    finalDaLinha *Estacao
}

Node Between Values

O método EntreDuasEstacoes do Metro retorna a Estacao que tem um nome situado entre os valores anterior e proxima. O método percorre a lista para descobrir se as strings anterior e proxima correspondem em Nodes consecutivos.

func (linhaVerde *Metro) EntreDuasEstacoes(anterior string, proxima string) *Estacao {

    var estacao *Estacao
    var estacaoAtual *Estacao

    for estacao = linhaVerde.inicioDaLinha; estacao != nil; estacao = estacao.estacaoSeguinte {

        if estacao.estacaoAnterior != nil && estacao.estacaoSeguinte != nil {

            if estacao.estacaoAnterior.nome == anterior && estacao.estacaoSeguinte.nome == proxima {
                estacaoAtual = estacao
                break
            }
        }
    }
    return estacaoAtual
}

Primeiro instanciamos o Node fazemos um for para percorrer os itens do head ao tail enquanto estacao for diferente de nil. Em seguida uma comparação com os parâmetros anterior e proxima feitos com o tail e head para reconhecer o node entre eles, sendo que a comparação é feita somente se head e tail forem diferentes de nil.

The AddToHead method

O método AddInicioDaLinha define o head para que possamos seguir construindo mais estacões assim como fizemos com o monotrilho.

func (linhaVerde *Metro) AddInicioDaLinha(novaEstacao string) {

    var estacao = &Estacao{}
    estacao.nome = novaEstacao
    estacao.estacaoSeguinte = nil

    if linhaVerde.inicioDaLinha != nil {

        estacao.estacaoSeguinte = linhaVerde.inicioDaLinha
        linhaVerde.inicioDaLinha.estacaoAnterior = estacao
    }
    linhaVerde.inicioDaLinha = estacao
}

AddAfter method

Aqui fazemos um insert de um node após outro node que é passado como parâmetro presente na lista, e para saber se o Node está presente reutilizamos o método ProcuraEstacao() que havíamos feito para a Single Linkedlist.

func (linhaVerde *Metro) AddEstacaoSeguinte(destino string, novaEstacao string) {

    var estacao = &Estacao{}
    estacao.nome = novaEstacao
    estacao.estacaoSeguinte = nil

    var estacaoAtual *Estacao
    estacaoAtual = linhaVerde.ProcuraEstacao(destino)

    if estacaoAtual != nil {

        estacao.estacaoSeguinte = estacaoAtual.estacaoSeguinte
        estacao.estacaoAnterior = estacaoAtual
        estacaoAtual.estacaoSeguinte = estacao
    }
}

Fazemos a instância do Node atribuímos o nome usado como parâmetro e setamos o node seguinte como nil para que se mantenha o conceito de tail.

Fazemos a busca e recuperamos a localização do Node de referência como estacaoAtual.

Então a estacao seguinte do node atual para a ser a estacao seguinte do node recuperado (mindfuck)
Parece um malabarismo de valores e é na verdade isso mesmo, talvez por isso pareça complicado mas basta trackear onde estão os valores e prestar atenção por onde eles estão passando.

The AddToEnd method

AddEstacaoNoFinalDaLinha cujo o nome é bastante descritivo, faz uma nova instância de um node e reutiliza o método UltimaEstacao() para recuperar o ultimo node e passar o valor do Node instanciado como referencia através de ponteiro.

func (linhaVerde *Metro) AddEstacaoNoFinalDaLinha(novaEstacao string) {

    var estacao = &Estacao{}
    estacao.nome = novaEstacao
    estacao.estacaoSeguinte = nil

    var fimDaLinha *Estacao
    fimDaLinha = linhaVerde.UltimaEstacao()

    if fimDaLinha != nil {

        fimDaLinha.estacaoSeguinte = estacao
        estacao.estacaoAnterior = fimDaLinha
    }
}

Main Func

Aqui vou fazer o mesmo processo que usei com o monotrilho pra popular a DLL, e além desses métodos no arquivo doubly.go no repositório tem mais exemplos de métodos para DLL e os métodos reaproveitados da Single Linked List.

func main() {
    var linhaVerde Metro
    linhaVerde = Metro{}

    estacoes := []string{"Tamanduateí", "Sacomã", "Alto do Ipiranga", "Santos-Imigrantes", "Chácara Klabin",
        "Ana Rosa", "Paraíso", "Brigadeiro", "Trianon-MASP", "Consolação", "Clínicas",
        "Sumaré", "Vila Madalena",
    }

    linhaVerde.AddinicioDaLinha("Vila Prudente")
    for i := range estacoes {
        linhaVerde.AddEstacaoNoFinalDaLinha(estacoes[i])
    }

    linhaVerde.ListarEstacoes()
}

Output:

Vila Prudente
Tamanduateí
Sacomã
Alto do Ipiranga
Santos-Imigrantes
Chácara Klabin
Ana Rosa
Paraíso
Brigadeiro
Trianon-MASP
Consolação
Clínicas
Sumaré
Vila Madalena

Doubly vs Single

Vantagens sobre a single linked list

• Uma DLL pode ser percorrida de trás para frente e vice versa.

• A operação de delete na DLL é mais eficiente se o ponteiro para o node excluído for fornecido.

• Podemos usar insert mais rapidamente em referencia a um item tanto a frente quanto trás.

• Na SLL (single linked list), para excluir um node, é necessário um ponteiro para o node anterior. Para obter esse node anterior, às vezes a lista precisa ser percorrida. Na DLL, podemos obter o node anterior usando o ponteiro anterior.

Desvantagens sobre a singly linked list

• Cada node da DLL requer espaço extra para um ponteiro anterior. (ainda assim é possível criar uma DLL sem um segundo ponteiro.)

• Todas as operações requerem um ponteiro extra para ser mantida. Por exemplo, no insert, precisamos modificar os ponteiros anteriores junto com os próximos ponteiros.