Java linked list implement clear() using recursion

This is my code:

public void clear(){
if(nodeFirst==null){}
else if(nodeLast==null){nodeFirst.setElement(null);}
else{clear(nodeLast);}
}

private void clear(Node<E> node){
if(node.getPrevious()==null){node.setElement(null);}
else{
Node<E> newNode= node.getPrevious();
node.setElement(null);
clear(newNode);
}

This is part of the test code:

assertEquals("[one, two, three, four, five]", l.toString());
l.clear();
assertEquals("[]", l.toString());

The first assertEquals returns true. The second one gives a nullPointerException.

This is my toString code:
public String toString(){
if(nodeFirst==null){
return "[]";
}
return "[" + toString(nodeFirst) + "]";
}

When I debug, for some reason, it skips the if statement, even though my clear() code should set nodeFirst to null and so the if statement should run. I don't know why this is happening...

Thanks

Reply 1

Async

19

I would appreciate it if you would add code tags around your code. It makes it easier to read.

Just by skimming through your code I can already spot one thing wrong.

the toString() method you declared should really have an @Override annotation on it.

(edited 9 years ago)

Reply 2

еlohssa

1

Eh, I think you've gotten really confused somewhere. You seem to be implementing a double linked list here. Such a linked list should have nodes, and each node has 2 pointers, one to the previous (null if there isn't one) and one to the next (ditto) element. As you recurse either forward or backward, to clear the list, you want to leave the 'dead' nodes unreferenced (and in java the garbage collector deletes them).

TBH, to clear a list in Java, I think you basically just need to set head.next = NULL and tail.previous=NULL. You don't need to visit every node (unlike in c++, where you'd need to visit every node to delete it).

(edited 9 years ago)

Reply 3

Async

19

Original post by еlohssa

Eh, I think you've gotten really confused somewhere. You seem to be implementing a double linked list here. Such a linked list should have nodes, and each node has 2 pointers, one to the previous (null if there isn't one) and one to the next (ditto) element. As you recurse either forward or backward, to clear the list, you want to leave the 'dead' nodes unreferenced (and in java the garbage collector deletes them).

TBH, to clear a list in Java, I think you basically just need to set head.next = NULL and tail.previous=NULL. You don't need to visit every node (unlike in c++, where you'd need to visit every node to delete it).

To clear the so called list. Isit possible to just re-instantiate the object used to store the data? That would be so much easier than recursively clearing it.

Reply 4

еlohssa

1

Original post by Async

To clear the so called list. Isit possible to just re-instantiate the object used to store the data? That would be so much easier than recursively clearing it.

You can wrap a linked list in a class, then re-instantiate it (I'm not sure if that's the approach the OP is taking). But without doing that, you can just NULL the head and tail and let the garbage collector do the rest.

If the question is asking to implement clear() using recursion, then IMO that is a silly question; as why would you do that?

(edited 9 years ago)

Reply 5

Async

19

Original post by еlohssa

You can wrap a linked list in a class, then re-instantiate it (I'm not sure if that's the approach the OP is taking). But without doing that, you can just NULL the head and tail and let the garbage collector do the rest.

Ahaha. I think OP is trying to implement his own linked list for better understanding, which is good. But, how will nulling the head and tail result in GC cleaning up the rest? How does the GC know that the head and tail is somehow linked to the rest of the body of the list?

But then again this all depends on how OP implemented this linked list.

Reply 6

еlohssa

1

Original post by Async

Ahaha. I think OP is trying to implement his own linked list for better understanding, which is good. But, how will nulling the head and tail result in GC cleaning up the rest? How does the GC know that the head and tail is somehow linked to the rest of the body of the list?

But then again this all depends on how OP implemented this linked list.

The GC will see at runtime, that nothing in the program references those nodes. It will then de-allocate their memory. Using singly linked list as example:

...if head is net to NULL, then those 4 nodes become 'unreachable'. The GC sees that and de-allocates their memory. In c++, there is no GC so each node has to be visited and delete has to be called on it.

(edited 9 years ago)

Original post by еlohssa

The GC will see at runtime, that nothing in the program references those nodes. It will then de-allocate their memory. Using singly linked list as example:

...if head is net to NULL, then those 4 nodes become 'unreachable'. The GC sees that and de-allocates their memory. In c++, there is no GC so each node had to be visited and delete has to be called on it.

Ahhh I see. Good point. Tbh I've never realized how useful the GC can be until I tried C++. Lol