How to delete all nodes in doubly linked list?

user_18862632 0
Viewed 76

I'm curious as to what is the correct way of deleting all nodes in a doubly linked list.

Here's my linked list structure:

type ListNode struct {
    Data branch
    Next *ListNode
    Prev *ListNode
}

type doublyLinkedList struct {
    Head *ListNode
    Tail *ListNode
    Size int
}

Will it work if I just point the Head & Tail nodes to Nil?

func deleteAllNodes(dl *doublyLinkedList) {
    dl.Head = nil
    dl.Tail = nil
    dl.Size = 0
}

If so, what happens to all the nodes? Does it get garbage collected?

doubly-linked-list go
1 Answers

In a reference counted environment (Arc in Rust, shared_ptr in C++, Swift, etc.), this could leak.

The nodes may have references among themselves, but there's no other references to them. In graph theory terms, the nodes being "deleted" form a component of the object graph, which is now a disconnected graph.

Any environment with a tracing garbage collector (including Go) can handle this, no problem.

First, the GC will detect all connected components of the memory graph (those objects which are referenced from root references, like global variables, local variables, etc.). This is called the "mark" phase. Then, it will delete all disconnected components in a second "sweep" phase. https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na%C3%AFve_mark-and-sweep

user_31412340
Related