Sign in to follow this  
GDKnight

Clearing Linked List C#? (SOLVED)

Recommended Posts

GDKnight    302
Well I have a simple question, I cant seem to find any info online so I decided to ask here. I coded my own LinkedList object in C# now I would like to implement a clear function into it which would clear each node of all its data and infact set each node to null. I am not quite sure how to do this. I could iterate through the nodes contained in it and set them to null but will this delete it? Im afraid it might set a reference to nothing leaving the data intact in memory. Or is this even a concern with C# im not quite sure on the exact details of doing this being a C++ programmer im used to just using delete. Any help would be greatly appreicated. [Edited by - GDKnight on October 24, 2005 5:32:59 PM]

Share this post


Link to post
Share on other sites
Drew_Benton    1861
Quote:
Original post by psae0001
I've no idea my link code won't I just type it out then:


In your post, you did not select text to display for the link as well as you missed the ending quotation mark.

Link Here - Click edit on my post to see how it's supposed to look.

Share this post


Link to post
Share on other sites
GDKnight    302
What about for a non-doubly linked list.

Mines a singly linked list I think what that one you showed in example does to remove it is some how collapse the nodes? I cant seem to get that to work for me.

Share this post


Link to post
Share on other sites
psae0001    100
Well, once again the classical question. First of all, I perfer doubly-linked; nothing speical, I just BELIEVE it works better than singly-link. Anyway, if you are using the singly-link. Here's what I would approce.

On your list, you have a head node, 2nd node, 3rd node ... etc. What you need is to go the head node, set the 2nd node as the head node, then remove the head node.

Share this post


Link to post
Share on other sites
kSquared    1356
Quote:
Original post by GDKnight
I could iterate through the nodes contained in it and set them to null but will this delete it? Im afraid it might set a reference to nothing leaving the data intact in memory.

One way is to implement the Dispose pattern. Here's a starting point for ListNode; you should be able to construct the analogous Dispose pattern for LinkedList.


public class ListNode : IDisposable
{
public object Entry;
public ListNode NextNode;

// ...

void IDisposable.Dispose()
{
Dispose(true);
GC.SuppressFinalize(this);
}

~ListNode()
{
Dispose(false);
}

protected virtual void Dispose(bool disposing)
{
if(disposing)
{
// Cleanup goes here.
Entry = null;
NextNode = null;
}
else
{
// Dispose wasn't called before the finalizer was.
DisposeNotCalled();
}

base.Dispose(disposing);
}

// Ignore improper disposing in Release mode.
[Conditional("DEBUG")]
private static DisposeNotCalled()
{
throw new InvalidOperationException("ListNode was improperly disposed.");
}
}

public class LinkedList
{
// ...

private ListNode[] _nodes;

// ...

public void Clear()
{
for (int i = 0; i < _nodes.Count; ++i)
{
// Disconnects all the nodes from the object graph, assuming there
// aren't any other references.
_nodes[i].NextNode = null;
_nodes[i] = null;
}
}
}

Share this post


Link to post
Share on other sites
Arild Fines    968
Quote:
Original post by kSquared
Quote:
Original post by GDKnight
I could iterate through the nodes contained in it and set them to null but will this delete it? Im afraid it might set a reference to nothing leaving the data intact in memory.

One way is to implement the Dispose pattern.

Eh, why? Are you going to require that list elements implement IDisposable as well? Otherwise there's no point.

There's no iteration needed. As long as all node objects are unreachable from a GC root, they will be collected. This is all you need:

public class LinkedList
{
private ListNode head;
private ListNode tail;
public void Clear()
{
head = tail = null;
}
}


This assumes that the list doesn't hand out references to ListNode objects to external code and that it doesn't hold onto other internal references to such objects besides head and tail. If these conditions hold, the garbage collector will take care of the rest.

Share this post


Link to post
Share on other sites
kSquared    1356
Quote:
Original post by Arild Fines
Quote:
Original post by kSquared
Quote:
Original post by GDKnight
I could iterate through the nodes contained in it and set them to null but will this delete it? Im afraid it might set a reference to nothing leaving the data intact in memory.

One way is to implement the Dispose pattern.

Eh, why? Are you going to require that list elements implement IDisposable as well? Otherwise there's no point.

He didn't say what it was a list of. If this is unmanaged resources we're talking about, it's much better to code defensively than to wait for it to come back and bite you. Clearly it's not POD, since he's trying to set them to null -- you can't set a value type to null. That said, adding a trial check like "Node toDispose = _node as IDisposable;" wouldn't be unreasonable.

Quote:
There's no iteration needed. As long as all node objects are unreachable from a GC root, they will be collected.

That statement is a little misleading -- you forgot to add the word "eventually" to the end. Remember, when an object is collected could be a very long time after when it is no longer f-reachable; do you really want your linked list of FileStreams holding on forever? Probably not.

In addition, your solution of merely setting the head and tail to null is not one I'm very fond of. An external reference to one of the nodes would still appear to be valid to the GC (and would never get disposed), even though the rest of the list is supposedly "cleared". This is an inconsistent object state and suggests poor design.

You correctly clarify this by saying that it works only if you don't hand out references externally, but what good is a collection class where you can't see the elements? The "linked list" described with that code looks more like a double-ended stack (you can see the top and the bottom but not anything in between).

Share this post


Link to post
Share on other sites
Arild Fines    968
Quote:
Original post by kSquared
He didn't say what it was a list of.

A fairly reasonable assumption would be that it is a list of either Object or T.
Quote:

If this is unmanaged resources we're talking about, it's much better to code defensively than to wait for it to come back and bite you. Clearly it's not POD, since he's trying to set them to null -- you can't set a value type to null. That said, adding a trial check like "Node toDispose = _node as IDisposable;" wouldn't be unreasonable.

Do you really think the standard containers do this? They don't, because of the cost. If you want to dispose the elements of a list, stack or whatever, you need to do your own iteration and IDispose()'ing, prior to .Clear()'ing the list.

Quote:

Quote:
There's no iteration needed. As long as all node objects are unreachable from a GC root, they will be collected.

That statement is a little misleading -- you forgot to add the word "eventually" to the end. Remember, when an object is collected could be a very long time after when it is no longer f-reachable; do you really want your linked list of FileStreams holding on forever? Probably not.

See above.

Quote:
}
In addition, your solution of merely setting the head and tail to null is not one I'm very fond of.

That's really too bad, since it's pretty much the only valid idiom in this case.
Quote:

An external reference to one of the nodes would still appear to be valid to the GC (and would never get disposed), even though the rest of the list is supposedly "cleared". This is an inconsistent object state and suggests poor design.

How the hell is that *inconsistent*? The 2.0 linked list class works just like that.
Quote:

You correctly clarify this by saying that it works only if you don't hand out references externally, but what good is a collection class where you can't see the elements?

Uh. You don't hand out references to the *node* objects externally. That doesn't mean you can't hand out references to the elements contained by the nodes.
Quote:

The "linked list" described with that code looks more like a double-ended stack (you can see the top and the bottom but not anything in between).

That's the general idea behind a linked list. If you want to go anywhere else, you start from the front or the back (depending on whether it's a doubly or singly linked list). What's the list object supposed to do - keep a reference to every node in an array, so it can be accessed quickly by index...?

Share this post


Link to post
Share on other sites
GDKnight    302
It got rid of all the nodes but then it went to add a node and had an error after clearing the list.

Though, I have one small question.
~Node()
{
Dispose(false);
}
is this a destructor?

[Edited by - GDKnight on October 24, 2005 5:55:31 PM]

Share this post


Link to post
Share on other sites
Arild Fines    968
Quote:
Original post by GDKnight

Though, I have one small question.
~Node()
{
Dispose(false);
}
is this a destructor?

Yes.
Quote:

I was taught that destructors don't exist in C#.

They do, but it's usually not a good idea to rely on them. If you add a destructor, the garbage collector will put the object on something called the "finalization queue" when it collects it. This queue is processed by a low-priority system thread, which can take a long time getting to your object. All this means that if your object contains a destructor, it may stay alive a lot longer than if it didn't have one.

Usually, if you need a destructor (to clean up resources owned by your object that really *needs* to be cleaned up), you should also implement the IDisposable interface. This gives any client the opportunity to explicitly call .Dispose() on your object to release said resources. Your implementation of .Dispose() should call GC.SuppressFinalize to prevent the garbage collector from putting your object on the finalizer queue.

Google for "IDisposable pattern".

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this