Очистка непустого двусвязного списка на Go

Question

Как это делать правильно на Go (c учетом особенностей сборщика мусора)?

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

Вот так это сделано в doublylinkedlist из github.com/emirpasic/gods

func (l *List) Clear() {

    l.size = 0
    l.head = nil
    l.tail = nil
}

Вот так у меня:

func (l *List) Clear() {

    for n := l.Back(); n != nil; n = n.Prev() {
        n.next = nil
    }

    l.size = 0
    l.head = nil
    l.tail = nil
}

В стандартной библиотеке вообще нет метода для очистки списка.

P.S. Исправил свой вариант по совету Pak Uula на этот

func (l *List) ClearOld() {

    n := l.Back()
    for n != nil {
        n = n.Prev()
        l.RemoveBack()
    }

    l.size = 0
    l.head = nil
    l.tail = nil
}

но оставил его только в качестве напоминания. А основным сделал метод без цикла.

Answer 1

Сборщик мусора в Go прошел долгий путь. Сейчас в нём реализован mark & sweep алгоритм. Если совсем грубо, то все глобальные объекты учтены в некотором реестре. Время от времени запускается mark алгоритм - от объектов, на которые ссылаются глобальные переменные, перебирают все достижимые обеъкты и помечают их как "живые". Затем запускается sweep - все объекты из глобального реестра, непомеченные как живые, удаляются.

В вашем случае это означает, что те объекты, которые вы храните в вашем списке, после присваиваний l.head = nil; l.tail = nil станут недоступны через переменную l и в очередной фазе mark не будут помечены как живые. Соответственно, в последующей фазе sweep они будут удалены. Утечки памяти не будет.

У вашего цикла

    for n := l.Back(); n != nil; n = n.Prev() {
        n.next = nil
    }

есть сразу две пробелемы. Во-первых, если на объекты внутри списка нет ссылок из переменных помимо l, то обнуление n.next ничего не даст для mark, объем работы для gc не изменится.

Во-вторых, удаление только n.next ничего не даст, так как почти на каждый Node в удалённом списке будет висеть ссылка n.prev. Нужно удалять оба указателя.

На самом деле обнуление указателей на элементы списка имеет смысл. Но только в том случае, если на какой-то из элементов списка есть указатель вне элементов списка. Обозначим его как E. Если E.prev и E.next не делать nil, то все остальные элементы списка, достижимые из элемента E, зависнут в памяти. Другими словами, в памяти зависнет весь список, так как у вас список двусвязный. Но обнуление тут тоже не есть гуд, так как E.Prev() и E.Next() после обнуления вернут нулевые указатели, и ваша программа может навернуться, если не будет проверять возвращаемые значения методов Prev и Next.

Так что что так, что эдак - есть свои минусы.

БЛОГ НА HUSL

Очистка непустого двусвязного списка на Go

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