더블 체인 미터

Emuma 이중 체인 시계, (que a partir de agora vou chamar de DLL) todos os nodes têm ponteiro para o node ao qual est ão conectados.
Isso signific que cada node estáconectado a dois nodes,e podemos avançar para o próximo node ou retroceder atéo node front.

DLL permitem opera ões de insert,deleting e,obviamente,de 역력.
E Para fins de manter o examplo 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ãe se perguntou“o meuésentido vila madalena ouésentido vila prudentie?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 front 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
}

값 사이의 노드

O método EntreDuasEstacoes do Metro returna a Estacao que tem um nome situado entre os valores front e proxima.O método percorre a lista para descobrir se as strings front e proxima correspondent em Nodes consutivos.

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 percorer os itens do head ao tail enquanto estacao for differente de nil.Em seguida uma comparaço com os par–metros front 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.

AddToHead 방법

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

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 메서드

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 recurperamos a localizaão do Node de referenceência como estacaoAtual.
Então a estacao SEGUINT do node atual para ser a estacao SEGUINT do node RECURAPERADO(mindfuck)
Parece um malabarismo de valores eéna verdade isso mesmo,talvez por isso pareça complaado mas basta trackear onde estão valores e prestar atenão por onde eles estão passando.

AddToEnd 메서드

AddEstacaoNoFinalDaLinha cujo o nomeébastante descriptivo,faz uma nova inst–ncia de um node e reutiliza o método UltimaEstacao()para recurper o ultimo node e passar o valor do node instanciado como referenceia 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
    }
}

주요 기능

Aqui vou fazer o mesmo processo que usei com o monotriho 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 단일 체인 테이블.

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()
}

출력:

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

쌍쌍

Vantagens sobre는 단일 체인 테이블입니다.

Uma DLL pode ser percorrida de trás para frente e 반대로도 마찬가지입니다.

operaão de delete na DLLémais efficient 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.

NaSLL(단일 체인표),paraexcluirumnode,énecessárioumponteiroparaonodefront.전림프종은 둔해서 정확한 림프종을 괴롭힌다.Na DLL,podemos obter o node front usando ponteiro front.

Desvantagens는 단일 체인 테이블입니다.

Cada node da DLL requer espaço extra para um ponteiro FREAR.(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.