Получение бесконечного цикла при выводе обратного связанного списка - PullRequest
Новая
       11

Получение бесконечного цикла при выводе обратного связанного списка

0 голосов
/ 19 июня 2019

Я изучаю Go и написал следующий код, чтобы перевернуть связанный список. Однако код не работает должным образом.

Вот структура Node вместе с функцией печати и обращения к списку. 

type Node struct {
    number   int
    previous *Node
    next     *Node
}

func PrintList(node *Node) {
    for n := node; n != nil; n = n.next {
        fmt.Println(n)
    }
}

func ReverseList(node *Node) {
    var nextNodeRef *Node

    for n := node; n != nil; n = n.previous {
        if n.next == nil {
            n.next = n.previous
            n.previous = nil

            *node = *n

            break
        } else {
            nextNodeRef = n.next

            n.next = n.previous
            n.previous = nextNodeRef

            if n.next == nil {
                node = n
            }
        }
    }

}

Проблема в том, что когда я переворачиваю список и вызываю PrintList, я получаю, казалось бы, бесконечный вывод всех элементов списка, кроме последнего (который раньше был первым элементом)

Вот моя main функция: 

func main() {
    myList := Node{1, nil, nil}
    myListAddress := &myList

    AddNumber(2, myListAddress)
    AddNumber(3, myListAddress)

    fmt.Println("My list:")
    PrintList(myListAddress)

    ReverseList(myListAddress)
    fmt.Println("My list reversed:")
    // here I always get list elements that contain 3, 2, 3, 2...
    PrintList(myListAddress)
}

А вот функция AddNumber, которую я использую: 

func AddNumber(number int, node *Node) *Node {
    if node == nil {
        log.Fatal("No Node provided")
    }

    var newNode Node

    for n := node; n != nil; n = n.next {
        if n.next == nil {
            newNode = Node{number, n, nil}
            n.next = &newNode

            break
        }
    }

    return &newNode
}

1 Ответ

1 голос
/ 19 июня 2019 
*node = *n

Эта строка не делает то, что вы думаете, что делает. Вы, вероятно, надеялись, что это изменит внешний *Node, чтобы он указывал на новую голову (старый хвост), да? Ну нет, он просто заменяет узел в этом месте. Что объясняет, почему отсутствует первое первое значение.

Итак, перед этим последним шагом у вас есть что-то вроде этого 

nil <- 3 <=> 2 <=> 1 -> nil
       ↑           ↑
       n           node, myListAddress

Затем вы заменяете node значением n (которое составляет nil <- 3 -> 2). Это делает структуру похожей на это: 

      prev
 ┌────────────────┐
 │                │ node, myListAddress    
 ˅                │╱
nil <- 3 <=> 2 -> 3 ──┐
             ^        │next
             └────────┘

Кстати, этот список настолько мал, что эта диаграмма может вводить в заблуждение. Вот как это выглядит с большим количеством элементов: 

      prev
 ┌────────────────────────────┐
 │                            │ node, myListAddress    
 ˅                            │╱
nil <- 5 <=> 4 <=> 3 <=> 2 -> 5 ──┐
             ^                    │next
             └────────────────────┘

Вы можете использовать **Node там. Или просто верните новую голову из функции: 

func ReverseList(node *Node) *Node {

    for n := node; n != nil; n = n.previous {
        if n.next == nil {
            n.next = n.previous
            n.previous = nil

            return n
        } else {
            n.next, n.previous = n.previous, n.next
        }
    }

    return node
}

Тогда 

myListAddress = ReverseList(myListAddress)
...