• Post Reply Bookmark Topic Watch Topic
  • New Topic

Basic linked list question | trying to have a better design  RSS feed

 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am just revising my java and data structure concept. I was trying to implement linked list. My goal is to write better and clean code.





In the else part of my insert method (highlighted above), I will have to create an instance of the node class. My node class can be any object (i.e. student, book etc.). I want to avoid hardcoding the type and casting in the add method. Should I create a new variable of type T only in my else part as well?

For example, someone wants to create the linked list of type student. In else part, I should be able to create instance student type.

My objective is to have a better design.

Thanks in advance!
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:In the else part of my insert method (highlighted above), I will have to create an instance of the node class.


Indeed you do. But you haven't declared the node class anywhere. You seem to think that a T object will function well as a node, but in reality you need a node to be able to be linked to the next node. That's how a linked list works, right? So you don't want to create a T object there, you already have a T object. Instead you need to create a LinkedListNode<T> object.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks, Paul.

I don't want the user to be aware of the node class. User should just create their objects ("Book" in this case) and create a linked list of type Book and add the objects to it. Just like the way java.util.LinkedList works. Like the following testcase:



Here is my node class:



I have updated my linked list class as following:



The insert method is incorrect because the newNode is empty as I haven't assigned any values to it. This is where I am confused. How do I assign the object to newNode? Or the design is incorrect?

 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:I don't want the user to be aware of the node class.


Of course the user shouldn't be aware of the node class. It should be internal to your LinkedList class so it's not visible to the user.
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:This is where I am confused. How do I assign the object to newNode? Or the design is incorrect?


Yes, the design is incorrect. A Node<T> object should contain a T variable, and that variable should be assigned a value (of type T) when the Node<T> object is constructed.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:
Punit Jain wrote:This is where I am confused. How do I assign the object to newNode? Or the design is incorrect?


Yes, the design is incorrect. A Node<T> object should contain a T variable, and that variable should be assigned a value (of type T) when the Node<T> object is constructed.


Got you. Thank you so much.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another question: Now in my get method, I am simply returning the lastNode for now, which is again Node<T>. But as user should not be aware of the node class. Should I return just T? Then how do I get T? as my firstNode is a Node<T>.

 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, of course. As you said, the user should be unaware of the internal Node class, so it naturally follows that you should return a T object. After all, from the user's point of view it's a list of T objects so the user puts in T objects and gets T objects out.

So. You have a Node<T> object and you want to get a T object out of it to return to the user. You should be able to figure that out, I believe.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:Yes, of course. As you said, the user should be unaware of the internal Node class, so it naturally follows that you should return a T object. After all, from the user's point of view it's a list of T objects so the user puts in T objects and gets T objects out.

So. You have a Node<T> object and you want to get a T object out of it to return to the user. You should be able to figure that out, I believe.


Yes got it. That was a silly question.   :o

Once finished I will post my implementation here as I need review comments to improve the code. :)
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here are some of the API's I have written so far:





Questions:

1.) I realized that I am having lots of null checks. Is there a better way of handling them?
2.) Any other issues with the code? Or can be better?

Thanks in advance!
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Personally, I would make Node a private nested class of Linked​List. That way, Linked​List can access its private fields directly and you can get rid of the getters and setters, and Node becomes completely invisible to the outside world, which is good.

Make your Linked​List and Node classes final unless you intend to extend them.

lastNode is named incorrectly. It actually always holds a reference to the first node in your list. Your add() method appears to insert nodes at the start of the list.

It's weird to me that the get() method would throw an exception if the list doesn't contain the indexed element, but the remove() method returns null. Even if you don't want to throw an exception, never return null from a method. Instead, return Optional.empty().
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can implement your get() and size() methods easily by calling recursive methods on Node:
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Personally, I would make Node a private nested class of Linked​List. That way, Linked​List can access its private fields directly and you can get rid of the getters and setters, and Node becomes completely invisible to the outside world, which is good.


Agreed and changed my classes.

Stephan van Hulst wrote:Make your Linked​List and Node classes final unless you intend to extend them.


Done.

lastNode is named incorrectly. It actually always holds a reference to the first node in your list. Your add() method appears to insert nodes at the start of the list.

Stephan van Hulst wrote:It's weird to me that the get() method would throw an exception if the list doesn't contain the indexed element, but the remove() method returns null. Even if you don't want to throw an exception, never return null from a method. Instead, return Optional.empty().

You mean like this:



and even with this, I get NoSuchElementException.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:You can implement your get() and size() methods easily by calling recursive methods on Node:


Are there any benefits of using recursion over iteration? I always get confused in recursion and always avoid them.

Also, do you mean calling getNumberOfFollowingNodes method into my LinkedList class size method?
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:You mean like this:

and even with this, I get NoSuchElementException.

Because you can't call get() on an empty Optional. You're supposed to return the empty Optional, so you need to change the method's return type.

Try to avoid negatives in boolean expressions, if it isn't too hard to do so:

Are there any benefits of using recursion over iteration? I always get confused in recursion and always avoid them.

Most of the time, it's a matter of preference. In this case recursion is more elegant, because your data structure is already recursive (nodes having references to nodes). Look how easily we could implement the getNumberOfFollowingNodes() method. Using iterative methods on a recursive data structure is a bit silly.

Also, do you mean calling getNumberOfFollowingNodes method into my LinkedList class size method?

Yes.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Punit Jain wrote:You mean like this:

and even with this, I get NoSuchElementException.

Because you can't call get() on an empty Optional. You're supposed to return the empty Optional, so you need to change the method's return type.

Try to avoid negatives in boolean expressions, if it isn't too hard to do so:


1.) Since we are returning Optional.ofNullable, do we still have to check isEmpty()? If node is empty the ofNullable should anyway return an empty object, correct?
2.) My goal was to get a "T" from the user and return a "T" to the user but in this case, I will have to return an Optional. Also, I can't use this in "get" method as the get method should return "T" only.

Stephan van Hulst wrote:
Are there any benefits of using recursion over iteration? I always get confused in recursion and always avoid them.

Most of the time, it's a matter of preference. In this case recursion is more elegant, because your data structure is already recursive (nodes having references to nodes). Look how easily we could implement the getNumberOfFollowingNodes() method. Using iterative methods on a recursive data structure is a bit silly.


Okay, but if there are 10000 nodes, the recursive method is going to have 10000 copies of that function in the stack, wouldn't that be inefficient?
 
Campbell Ritchie
Sheriff
Posts: 55351
157
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:. . . if there are 10000 nodes, the recursive method is going to have 10000 copies of that function in the stack, wouldn't that be inefficient?
Well, a linked list always runs in On (linear complexity), so the recursion is no slower than an iterative method would be, as long as you have enough memory to accommodate that size of call stack. If you need O1 (constant complexity) performance, you would have to change to an array list.
I think you have misunderstood how an Optional<T> works. Don't call get if you can use orElse instead. Search for Optional, particularly articles about it by Raoul‑Gabriel Urma.
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:1.) Since we are returning Optional.ofNullable, do we still have to check isEmpty()? If node is empty the ofNullable should anyway return an empty object, correct?

No, because you have to perform the check anyway to find out if you have to replace the first node. If the first node doesn't exist, dereferencing firstNode.next will give a NullPointerException.

2.) My goal was to get a "T" from the user and return a "T" to the user but in this case, I will have to return an Optional. Also, I can't use this in "get" method as the get method should return "T" only.

Your choice is simple: Either design your methods to return an Optional, or design them to throw an exception if the element isn't present. Don't return null.

Okay, but if there are 10000 nodes, the recursive method is going to have 10000 copies of that function in the stack, wouldn't that be inefficient?

Not necessarily. If the virtual machine supports tail call optimization, recursion may be even more efficient than iteration. Instead of adding a frame to the call stack, the current frame simply gets replaced with the new frame.

Your concern is valid for the getNumberOfFollowingNodes() method though. Since the recursive call is not in tail position, each call will introduce a new frame on the call stack. For large lists, this may cause a StackOverflowError. It's easy to rewrite the size() method to an iterative version though:

However, you can make its performance constant by just keeping a size field in your class and incrementing it when you've added an element to the list.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Punit Jain wrote:. . . if there are 10000 nodes, the recursive method is going to have 10000 copies of that function in the stack, wouldn't that be inefficient?
Well, a linked list always runs in On (linear complexity), so the recursion is no slower than an iterative method would be, as long as you have enough memory to accommodate that size of call stack. If you need O1 (constant complexity) performance, you would have to change to an array list.
I think you have misunderstood how an Optional<T> works. Don't call get if you can use orElse instead. Search for Optional, particularly articles about it by Raoul‑Gabriel Urma.


Thanks Paul for pointing me the article about Optional. Actually I was referring getNumberOfFollowingNodes() for 10000 nodes example.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Punit Jain wrote:1.) Since we are returning Optional.ofNullable, do we still have to check isEmpty()? If node is empty the ofNullable should anyway return an empty object, correct?

No, because you have to perform the check anyway to find out if you have to replace the first node. If the first node doesn't exist, dereferencing firstNode.next will give a NullPointerException.


Cool. Got you.

Stephan van Hulst wrote:
2.) My goal was to get a "T" from the user and return a "T" to the user but in this case, I will have to return an Optional. Also, I can't use this in "get" method as the get method should return "T" only.

Your choice is simple: Either design your methods to return an Optional, or design them to throw an exception if the element isn't present. Don't return null.


Okay. I changed all my return types to Optional.

Stephan van Hulst wrote:
Okay, but if there are 10000 nodes, the recursive method is going to have 10000 copies of that function in the stack, wouldn't that be inefficient?

Not necessarily. If the virtual machine supports tail call optimization, recursion may be even more efficient than iteration. Instead of adding a frame to the call stack, the current frame simply gets replaced with the new frame.

I see. I will need to read tail call optimization once.

Stephan van Hulst wrote:
Your concern is valid for the getNumberOfFollowingNodes() method though. Since the recursive call is not in tail position, each call will introduce a new frame on the call stack. For large lists, this may cause a StackOverflowError. It's easy to rewrite the size() method to an iterative version though:

However, you can make its performance constant by just keeping a size field in your class and incrementing it when you've added an element to the list.


Cool. The keeping class level is more worth.

Thank you so much for all your explanation.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tried to implement all the suggestions and here is how my code looks like as of now:-



Silly Question:-

This code has compilation issues in get() method because I am not calling it via Node class reference. Question is, what node reference should I use?
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't understand why your getNode(position) method belongs to the Node class anyway. Do you want to get node # 3 of a Node, or do you want to get node # 3 of a LinkedList?
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:I don't understand why your getNode(position) method belongs to the Node class anyway. Do you want to get node # 3 of a Node, or do you want to get node # 3 of a LinkedList?


I want to get a node# 3 of linked list, but if I do that recursively I will have to have the method in Node class only as I will be iterating over nodes? Or I am wrong?
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:I want to get a node# 3 of linked list, but if I do that recursively I will have to have the method in Node class only as I will be iterating over nodes? Or I am wrong?


If your code worked with String objects would that mean you have to put it into the String class? Of course not. Likewise just because your code works with Node objects, that doesn't mean it has to be in the Node class.

You want to get Node N from a LinkedList, so you need a getNode(N) method in LinkedList.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:
Punit Jain wrote:I want to get a node# 3 of linked list, but if I do that recursively I will have to have the method in Node class only as I will be iterating over nodes? Or I am wrong?


If your code worked with String objects would that mean you have to put it into the String class? Of course not. Likewise just because your code works with Node objects, that doesn't mean it has to be in the Node class.

You want to get Node N from a LinkedList, so you need a getNode(N) method in LinkedList.


Thanks, Paul. I am trying to do it in the same recursive way in LinkedList.



Now the problem I am getting is what do I pass in return Optional.of();? Any pointers?

 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul, if you want to implement the method with recursion, the alternative to having a getNode(distance) method in the Node class would be a static getNode(startingNode, distance) method in the LinkedList class. Why have a static method that accepts a Node, if you can just put an instance method in Node?

The get(position) method is in the LinkedList class, and returns an element by calling getNode(position) on the first node, and then unwrapping the resulting Node.

Maybe some confusion arises because the getNode() method is not declared and implemented properly. Its parameter should be the distance from the current node, not a position. It doesn't work because the implementation always makes the recursive call on the current node, not the next node.
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks like I didn't read the requirements, then. I don't care whether recursion is used or not, and I would expect a method which gave me the n-th node in the list and not one which gave me the n-th node from the current node. Apologies if (and only if) I misunderstood the requirements.
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's not a requirement, it's just an implementation detail. The getNode() method is a private method used to implement the get() method. I suggested it because I think it's more elegant to use a recursive algorithm than a loop when your data structure is already recursive.

It's perfectly alright to just implement the getNode() method by iterating through the chain using a for-loop, and in that case you can move the method to the LinkedList class. I just think recursion is better.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay. So basically there are two things:

1.) I can have an iterative solution in the LinkedList class. However, implementing a recursive solution in the LinkedList class is not possible with this design? Please correct me if I am wrong here.

2.) As Stephan suggested, I can have a private recursive getNode method in the Node class and call it from the LinkedList class.

Talking about the recursive solution, the problem I am facing is how do I call that private getNode method from Node class to my LinkedList class?

Stephan van Hulst wrote:
Maybe some confusion arises because the getNode() method is not declared and implemented properly. Its parameter should be the distance from the current node, not a position. It doesn't work because the implementation always makes the recursive call on the current node, not the next node.


Do you mean I will need to have a loop in my get method of LinkedList class also, from where I am calling the getNode of Node class?


Please accept my apologies if I am dragging this too much.
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Punit Jain wrote:1.) I can have an iterative solution in the LinkedList class. However, implementing a recursive solution in the LinkedList class is not possible with this design? Please correct me if I am wrong here.

It is possible, but it doesn't make sense. The recursive method requires an object of type Node, and not an object of type LinkedList. That means you can add static method to LinkedList that accepts a Node, but why not just add an instance method to Node? Java is object oriented after all; procedural code should be avoided.

Talking about the recursive solution, the problem I am facing is how do I call that private getNode method from Node class to my LinkedList class?

Just call it on your first node. If there is no first node, return Optional.empty().

Do you mean I will need to have a loop in my get method of LinkedList class also, from where I am calling the getNode of Node class?

No. Just call it on your first node and you're done. No loops. This is why I think recursion is more elegant.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Talking about the recursive solution, the problem I am facing is how do I call that private getNode method from Node class to my LinkedList class?

Just call it on your first node. If there is no first node, return Optional.empty().


Actually, I tried that, but it always gives me the firstNode.

 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Because your getNode() method isn't implemented correctly.
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
By the way, your get() method does a lot of unnecessary stuff. You can just do this:
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:By the way, your get() method does a lot of unnecessary stuff. You can just do this:


 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Because your getNode() method isn't implemented correctly.


I think my getNode() needs to have one more parameter Node.

 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why? You're just passing its next node to the next invocation, but you're not actually doing anything useful with any of the nodes you're passing.

Your precious version of the method was more correct. The only problem is that you're always calling the method on the current node, without moving through the chain. So instead of calling it on the current node, you should call the method on a different one.
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Why? You're just passing its next node to the next invocation, but you're not actually doing anything useful with any of the nodes you're passing.

Your precious version of the method was more correct. The only problem is that you're always calling the method on the current node, without moving through the chain. So instead of calling it on the current node, you should call the method on a different one.


Will I have to start from the last node? But in this case, I will have iterate till the last node first.

Following is the method in Node class:-



This is how I am calling it from the LinkedList class:-

 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The entire point of recursion is no loops. The get() method was fine as it was, it was the getNode() method that was wrong.

Imagine yourself standing in a line of people. The guy behind you asks you for the name of the person 5 spots ahead of you. You can't get out of line. You can only whisper to the person in front of you. How will you find out the answer, so you can tell the guy behind you?
 
Punit Jain
Ranch Hand
Posts: 1066
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:The entire point of recursion is no loops. The get() method was fine as it was, it was the getNode() method that was wrong.

Imagine yourself standing in a line of people. The guy behind you asks you for the name of the person 5 spots ahead of you. You can't get out of line. You can only whisper to the person in front of you. How will you find out the answer, so you can tell the guy behind you?


Got it.



But now the problems here is, I am initializing node with this. Now every recursive call will make it initialized by firstnode always. So it will always return me the second node.
 
Stephan van Hulst
Saloon Keeper
Posts: 7722
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're not actually doing anything with node.next.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!