Clearing a double-linked list.

Question

Hi.

I have a double linked list (queue) I have made on my own.

I am wondering, to clear the linked list, is it enough to simply remove the head and tail references?

E.g

public void Clear()
{
    Head = null;
    Tail = null;
}

I am imaging a domino effect, but I am having a hard time testing it. It WILL make the whole object appear empty atleast. All data requests (such as peek, dequeue etc.) returns null. You can also easily Enqueue some new objects. Purely functional it seems to be working.

But I'd really like to know if I am doing it the right way.

Answer 1

Unless the objects in the collection needs to be disposed of, and it is the responsibility of the collection to do that, then your method is probably the best way.

Since there is no root to the object (no live references), garbage collection can pick it up and remove it.

Answer 2

The short answer is yes, garbage collection will clear out all the linked list nodes, provided that nothing external holds a reference to them.

Easiest way to test is to add a finalizer to your linked list node object that outputs some logging. Note that you can't be sure when the garbage collector runs (without forcing it, via GC.Collect()) so you won't see the finalizer called as soon as you call you Clear() method.

The "domino effect" is not going to happen, though; it doesn't matter if references are held to an object, rather than references can be traced back to the stack or a static object. So if several objects refer to each other, but nothing refers to them, then they'll all be garbage collected simultaneously.

Answer 3

I am imaging a domino effect

This isn't how the GC works.

The GC first marks everything "dead", then starting at the root objects it traverses all objects referenced by them, marking each one as "alive".

Since your list is no longer reference by any root objects (or children of) it will be left marked "dead".

The second pass then frees the "dead" objects.

I doubt that you can assume in a finalizer that any objects either side in the list have not been collected first, ie it will be in the GC's own order not the order of the list.

A bit more detail here:- http://msdn.microsoft.com/en-us/magazine/bb985010.aspx