Go: передача указателей в метод и их изменение

Question

Начал изучать Go, но что-то не могу разобраться с сабжем. Вот есть linked list

    type List struct {
        next *List
        val  any
}

создаю его экземпляр вот так

myList := &List{nil, 1}

добавляю ещё звеньев и пытаюсь его развернуть вот так

func (n *List) Reverse() {
    var tmp *List
    tmp = n
    var prev *List
    var last *List
    for tmp != nil {
        last = tmp.next
        tmp.next = prev
        prev = tmp
        tmp = last
    }
    *n = *prev
}

сам разворот стандартный, взят из другого языка, где работает. Но тут список странным образом зацикливается. Что я делаю не так? Такой список 1 2 3 4 превращается в 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4

Вот ссылка на код https://go.dev/play/p/VLffKqlex-d

Answer 1

Да, действительно это так работать не будет. Ну, по крайней мере, у меня тоже не получилось. Я думаю, что адрес ресивера нельзя менять на прямую и нельзя сделать так:

func (l **List) Reverse()

но можно сделать так:

func Reverse(list **List) {
    node := *list
    var prev *List

    for node != nil {
        node, prev, node.next = node.next, node, prev
    }
    *list = prev
}

что выглядит не красиво, а может и идиоматически не правильно. Тогда можно хранит указатель на голову списка в отдельной переменной структуры как сделано в этом примере: https://gist.github.com/P-A-R-U-S/55ee88bfecb87f8614e1a4f67b57c866

Answer 2

Когда вы берёте первый элемент списка в выражении tmp = n, вы записываете в tmp указатель на ту же ячейку памяти, куда указывает n.

Соответственно, когда вы при обращении строите второй элемент, его указатель .next указывает на n

Когда после цикла вы делаете *n = *prev происходит вот что: по адресу n изменяются значения полей n->next и n->val, но само значение n не изменяется. Это означает, что препоследний элемент обращённого списка будет указывать на голову списка. Получается цикл.

Для того, чтобы цикл не возникал, нужно, чтобы при обращении последний элемент был в новом месте. Вместо tmp = n напишите tmp = &List{n.next, n.val}

Собственно, ваш Push работает именно благодаря тому, что вы присваиванием last := *n создаёте копию головы списка в новом месте в куче. В результате после присваивания *n = *node в ячейке n.next лежит указатель на свежеаллоцированный last

Пример работающего кода https://go.dev/play/p/LiWA4NfpV82

ДОБАВКА

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

type List struct {
    next *List
    val  interface{}
}

func (l *List) ReverseInPlace() {
    if l == nil {
        // empty list
        return
    }
    var head, tail *List
    var second_last *List
    tail = l
    for tail != nil {
        next_tail := tail.next
        tail.next = head
        head = tail
        tail = next_tail

        if head.next == l {
            second_last = head
        }
    }
    // Swap l.val and head.val
    if l == head {
        // single-element list
        // do nothing
    } else {
        *l, *head = *head, *l
        // Update last-but-one element
        if second_last == head {
            // two element list
            l.next = head
        } else {
            // more than 2 elements in the list
            second_last.next = head
        }
    }
}

Полный код https://go.dev/play/p/GCNLeGWxezi ВНИМАНИЕ: этот пример не проверяет наличие цикла в списке.

БЛОГ НА HUSL

Go: передача указателей в метод и их изменение

Ответы (2 шт):