时间戳

首页 > 解决方案 > Golang中双链循环列表上的函数InsertBefore()

list - Golang中双链循环列表上的函数InsertBefore()

问题描述

我在 Golang 中实现了一个双链循环列表，我遇到了以下问题，我能够正确组装 InsertAfter() 函数以向列表中添加值，它包含以下结构：

package main

type Node struct {
    Value int
    Next  *Node
    Prev  *Node
}

func CreateList(n int) *Node {
    nn := &Node{
        Value: n,
        Next:  nil,
        Prev:  nil,
    }
    nn.Next = nn
    nn.Prev = nn

    return nn
}

func InsertAfter(p *Node, value int) *Node {
    nn := &Node{Value: value}
    q := p.Next
    p.Next = nn
    nn.Next = q
    q.Prev = nn
    nn.Prev = p

    return nn
}

func main() {
    L := CreateList(3)
    x := InsertAfter(L, 7)
    InsertAfter(x, 11)
    k := InsertBefore(x, 5) //This (when it works) should insert the value 5 before the value 7
}

在此之后，我使用此函数在列表中插入 3 个 int 值（值 3、7 和 11）但我需要创建一个函数（称为 InsertBefore()）尊重前一个函数的结构并实现反函数为此并在之前插入一个值，我能够创建它的一部分，但它不起作用（如下所示），请告诉我我在哪里失败或我缺少什么来完成它？谢谢你。

func InsertBefore(p *Node, value int) *Node {

    nn := &Node{Value: value}
    q := p.Prev
    p.Prev = nn
    nn.Prev = q
    q.Next = nn
    nn.Next = p

    return nn
}

标签： listgolinked-listinsert

解决方案

我为代码添加了一些解决方法。我认为这现在正在工作。

    package main
    
    import (
        "fmt"
    )
    
    type Node struct {
        Value int
        Next *Node
        Prev *Node
    }
    
    func CreateList(n int) *Node {
        nn := &Node{
            Value: n,
            Next: nil,
            Prev: nil,
        }
        nn.Next = nn
        nn.Prev = nn
    
        return nn
    }
    
    
    func (p *Node)InsertAfter(value int) *Node {
        nn := &Node{Value: value}
        nn.Prev = p
        nn.Next = p.Next
    
        //if p is not the last element in the list
        //its next.previous should be new node
        if p.Next.Prev != p.Next {
            p.Next.Prev = nn
        }
    
        p.Next = nn
    
        return nn
    }
    
    func printList(p *Node) {
        n := p
        for {
            fmt.Println(fmt.Sprintf(`node %v, prev %v, next %v`, n, n.Prev.Value, n.Next.Value))
            n = n.Next
            if n == p {
                break
            }
        }
    }
    
    func (p *Node)InsertBefore(value int) *Node {
        nn := &Node{Value: value}
        nn.Next = p
        nn.Prev = p.Prev
        if p.Prev == p {
            //this means this is the root
            //so we need to update last node's next
            n := p
            for {
                if n.Next == p {
                    n.Next = nn
                    break
                }
                n = n.Next
            }
            nn.Prev = nn
        } else {
            p.Prev.Next = nn
        }
        p.Prev = nn
        return nn
    
    }
    
    func main() {
        L := CreateList(3)
        x := L.InsertBefore(7)
    
        x.InsertAfter(11)
        x.InsertBefore(5)
    
        fmt.Println(`final list`)
        printList(x)
    }

//Output: -
//final list
//node &{7 0xc00000c060 0xc00000c078}, prev 5, next 11
//node &{11 0xc00000c030 0xc00000c048}, prev 7, next 3
//node &{3 0xc00000c078 0xc00000c060}, prev 11, next 5
//node &{5 0xc00000c048 0xc00000c078}, prev 5, next 7

你可以在这里运行代码

推荐阅读