• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Paul Clapham
  • Devaka Cooray
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Frits Walraven
Bartenders:
  • Carey Brown
  • salvin francis
  • Claude Moore

LinkedList Implementation  RSS feed

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I'm creating a LinkedList class that also uses Stack implementation. So far, I've been running into trouble with null pointer exceptions, especially in my remove and push methods. The remove method doesn't remove as it should and for some reason the push method includes null in the output.  Can I get some advice on how to improve my code? Also, I'm not sure why my professor decided to go with new Integer to test the remove method. I am aware it's one of the deprecated methods. Thanks!

Output:

[ 3 5 7 ]
3 5 7 9
[ ]


[ 5 3 null ]
5
[ 3 null ]


LinkedList


DriverClass


 
Marshal
Posts: 64089
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Please show us your Stack interface.
 
luan perre
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is the given Stack interface

 
Campbell Ritchie
Marshal
Posts: 64089
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for showing us the code. That looks good, but I would make two changes:-
Rather than no such element exception, consider throwing this instead.
Use /** comments */ instead of // comments

Line 5. that comment is incorrect; you are not creating a empy List, but a one‑element List with an empty node.
What do lines 63‑65 mean? And line 97? Line 97 makes it look as if you were popping the next to top element rather than the top element. Similarly line 107.
 
Sheriff
Posts: 5917
155
Chrome Eclipse IDE Java Postgres Database Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't you mean while (temp != null)?
 
Campbell Ritchie
Marshal
Posts: 64089
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

luan perre wrote:. . . I'm not sure why my professor decided to go with new Integer to test the remove method.

Because your teacher is on the ball and wants to make your code fail if you use the == operator.

I am aware it's one of the deprecated methods.  . . .

Not method, but constructor.
 
luan perre
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I updated the methods with some of your suggestions but still am running into some issues. Right now, I'm working through the logic to see where I'm going wrong.

New Output:
[ 3 5 7 ]
3 7 9
[ ]


[ 5 3 null ]
7
[ 3 null ]

 
Campbell Ritchie
Marshal
Posts: 64089
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your push() method looks unnecessarily long, but otherwise I can't see anything that won't work.
Please show us your constructor.
 
Marshal
Posts: 13441
222
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Line 5. that comment is incorrect; you are not creating a empy List, but a one‑element List with an empty node.


I would argue otherwise. The comment declares the intent. The code, on the other hand, is simply the OP's implementation, which is to use a Null Object. I don't know if OP intentionally did that or knew that's what he was doing but it is nevertheless a Null Object, at least initially. You could also call it a "bookend" -- the point being that first will always point to it.

To check for an "empty" list, you'd simply check for first == last. Again, I don't know if OP is deliberately doing this or if he just stumbled on this blindly/accidentally.
 
Junilu Lacar
Marshal
Posts: 13441
222
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

@OP: What is this code supposed to mean? The condition seems wrong.

Given that you will throw a NoSuchElementException if this condition is true, it seems your intent was to check if the list is empty. However, if you initialize your instances like this:

then (first.next == last) will be false even though the list is empty.

The ideal code would be:

write your code so that it's always expressing intent clearly. A formula like first.next == last is not readily discernible as right or wrong. In this case, it's probably wrong.

I would actually start with a test. In JUnit, that would be something like this:
 
luan perre
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Update. My stack methods work now with the correct outputs. These are the changes I made for reference.


Normally I would create helper methods to aide my methods like isEmpty() or hasNext() but the way that this assignment is put together, we're only to fill in toString(), clear(), remove(E e), push(E e), pop(), and top();
So although there are things i would have done differently, I'm not to change anything from the other methods.

From what I understand, first is to be a pointer to the actual first node, so that's why I had to change my methods to first.next to yield the correct results.

I ran size() on each of the lines to check that the number of elements is correct. All but the remove method return the correct amount.
 
Campbell Ritchie
Marshal
Posts: 64089
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

luan perre wrote:. . . check that the number of elements is correct. All but the remove method return the correct amount.

Your updated code looks a lot better, but I am still worried about your using first.next rather than plain simple first. And what you said there means your counting is incorrect, I am afraid. A miss is as good as a mile, and one wrong result raises concerns about all results. The error might be in the remove() method, as you suggest, in which case it might only occur if you declare your reference as List.
 
Junilu Lacar
Marshal
Posts: 13441
222
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I updated the original code you gave with the most recent updates you said you made and the code still failed these tests, as I suspected it would:


java.util.NoSuchElementException
at ... .LinkedList.remove(LinkedList.java:86)
at ... .LinkedListTest.bug1(LinkedListTest.java:19)
...

This is the buggy code:


org.opentest4j.AssertionFailedError: Unexpected exception type thrown ==>
Expected :<java.util.NoSuchElementException>
Actual   :<java.lang.NullPointerException>

...
at ... .LinkedListTest.bug2(LinkedListTest.java:27)
...
caused by: java.lang.NullPointerException
at ... .LinkedList.pop(LinkedList.java:122)
...

This is the buggy code:


 
Junilu Lacar
Marshal
Posts: 13441
222
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

luan perre wrote:
Normally I would create helper methods to aide my methods like isEmpty() or hasNext() but the way that this assignment is put together, we're only to fill in toString(), clear(), remove(E e), push(E e), pop(), and top();
So although there are things i would have done differently, I'm not to change anything from the other methods.


I know it's not your fault but that is quite pathetic. It's as if your instructor is elephant breaking you. To me, this is absolutely the WORST way to teach programming.

By the way, the bugs I pointed out were easily fixed and the code's intent clarified significantly by adding the isEmpty() method as I suggested:
 
Junilu Lacar
Marshal
Posts: 13441
222
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's yet another test that fails:


org.opentest4j.AssertionFailedError: Unexpected exception type thrown ==>
Expected :<java.util.NoSuchElementException>
Actual   :<java.lang.NullPointerException>

...
at ... .LinkedListTest$NoSuchElement.bug3(LinkedListTest.java:41)

These tests all fail because of this bug:

 
Junilu Lacar
Marshal
Posts: 13441
222
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And in case you're wondering, the code I'm running these failing tests against PASSES the tests in the DriverClass you gave.

This would be a VERY dangerous situation if this code was to be used out in the real world and your only tests were those you have in that DriverClass.

Edit: Actually, some of the test code in DriverClass  DOESN'T pass -- it's just difficult to discern that because this not a self-validating test.

This is the test code:

And this is the actual output:

[ 3 5 7 ]
3 7 9  // <=== WRONG
[ ]

This is even more dangerous now because you think the tests pass even though they actually failed.
 
Campbell Ritchie
Marshal
Posts: 64089
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is that because the remove(int) method is different from the remove(E) method?
 
Junilu Lacar
Marshal
Posts: 13441
222
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Is that because the remove(int) method is different from the remove(E) method?


I didn't see a remove(int) method. If you declare a generic method remove(E e) where E is Integer and pass it an int literal, remove(1), then Java's autoboxing and auto-unboxing behavior kicks in and the call becomes remove(new Integer(1)) under the covers.

Edit: Only autoboxing behavior actually comes into play in the remove(1) call.  Auto-unboxing will happen when you get an Integer from the list and assign the value to an int.
 
Campbell Ritchie
Marshal
Posts: 64089
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . I didn't see a remove(int) method. . . . .

That means I am getting confused between the current List interface and java.util.List, which does have a remove(int) method. Sorry for my mistake.
 
I am not young enough to know everything. - Oscar Wilde This tiny ad thinks it knows more than Oscar:
Create Edit Print & Convert PDF Using Free API with Java
https://coderanch.com/wiki/703735/Create-Convert-PDF-Free-Spire
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!