Java linked list implement clear() using recursion

Watch this thread
Aaradhana
Badges: 0
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Report Thread starter 7 years ago
#1
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
0
reply
Async
Badges: 19
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report 7 years ago
#2
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.
0
reply
еlohssa
Badges: 1
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report 7 years ago
#3
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).
1
reply
Async
Badges: 19
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report 7 years ago
#4
(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.
0
reply
еlohssa
Badges: 1
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report 7 years ago
#5
(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?
0
reply
Async
Badges: 19
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report 7 years ago
#6
(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.
0
reply
еlohssa
Badges: 1
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
Report 7 years ago
#7
(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:

Image

...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.
Attached files
0
reply
Async
Badges: 19
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report 7 years ago
#8
(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:

Image

...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
0
reply
еlohssa
Badges: 1
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9
Report 7 years ago
#9
(Original post by Async)
Ahhh I see. Good point. Tbh I've never realized how useful the GC can be until I tried C++. Lol
Yep I think the OP's question (implement clear() using recursion) would only make sense if it was for a non GC language.
1
reply
Aaradhana
Badges: 0
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10
Report Thread starter 7 years ago
#10
Oh right... Thanks! I was a little confused with the actual element and the next and the previous but now it makes sense.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest

Does school Maths prepare people well enough for the future?

Yes, it gives everyone a good foundation for any future path (50)
30.12%
Somewhat, if your future involves maths/STEM (73)
43.98%
No, it doesn't teach enough practical life skills (41)
24.7%
Something else (tell us in the thread) (2)
1.2%

Watched Threads

View All