Punit Jain wrote:In the else part of my insert method (highlighted above), I will have to create an instance of the node class.
Punit Jain wrote:I don't want the user to be aware of the node class.
Punit Jain wrote:This is where I am confused. How do I assign the object to newNode? Or the design is incorrect?
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.
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.
Stephan van Hulst wrote:Personally, I would make Node a private nested class of LinkedList. That way, LinkedList 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.
Stephan van Hulst wrote:Make your LinkedList and Node classes final unless you intend to extend them.
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.
Stephan van Hulst wrote:You can implement your get() and size() methods easily by calling recursive methods on Node:
Punit Jain wrote:You mean like this:
and even with this, I get NoSuchElementException.
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 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:
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.
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.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?
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?
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.
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 wrote:
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.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?
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 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.
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.
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.
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.
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?
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?
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.
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.
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.
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?
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?
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().
Stephan van Hulst wrote:By the way, your get() method does a lot of unnecessary stuff. You can just do this:
Stephan van Hulst wrote:Because your getNode() method isn't implemented correctly.
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.
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?
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |