Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS forum!
  • 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Making a doubly linked list using comparable, getting tripped up on how to properly rewire nodes.

 
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is my assignment guidelines for this specific insert method:

This method inserts the new item into the list, while keeping the list in sorted order (sorted from smallest to largest using comparable). This means that you will have to figure out where the new item is supposed to go, and then correctly rewire the list to actually place it there.

NOTE: context/full code--- https://hastebin.com/uloyekemar.kotlin

I did some testing, tried to research online before looking for help. The issue seems to be that my references are screwed up and I didn't rewire the nodes properly. Also seems to be a bug in my toString() method maybe? Really not sure, I just see answers to what the problem could be but don't know how to fix it since I am a beginner.

TLDR: my comparable if statements in the insert method are not working, possibly due to references and/or toString implementation.

Also, I know the other methods are utter nonsense but I intend to fix this first... thanks!

 
Bartender
Posts: 558
10
IntelliJ IDE Spring Fedora
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
One important thing to keep in mind when writing code is to minimize repeating lines. ("DRY") This increases readability and makes it easier to fix things.
 
William Golovlev
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Al Hobbs wrote:One important thing to keep in mind when writing code is to minimize repeating lines. ("DRY") This increases readability and makes it easier to fix things.


What specifically are you referring to? If it is something outside of the insert method, I am not worrying about that as of now.
 
Master Rancher
Posts: 4465
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Please post your code here on the forum.  Be sure to wrap it in code tags.
 
William Golovlev
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Norm Radder wrote:Please post your code here on the forum.  Be sure to wrap it in code tags.

edited.
 
Norm Radder
Master Rancher
Posts: 4465
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How are you trying to debug the code to see what it is doing so you can find the problem?
The code does not have many useful print statements to show the program's progress when it is trying to do an insert.
 
William Golovlev
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Norm Radder wrote:How are you trying to debug the code to see what it is doing so you can find the problem?
The code does not have many useful print statements to show the program's progress when it is trying to do an insert.


I removed some of these print statements because it looked pretty bad. But I was putting statements in the if statements, and can see they are executing as intended, but then the actual node rewiring does not work as expected and the list ends up have one to no elements upon printing out.
 
Norm Radder
Master Rancher
Posts: 4465
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

 actual node rewiring does not work as expected


Can you describe the expected results for these  cases:
node to insert is less than the current node
node to insert to go at end of list

What values need to be copied to link the the new node?

I removed some of these print statements


Put them back until the code is debugged.
For example what value is in head after the first insert is done?
 
Marshal
Posts: 74084
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

William Golovlev wrote:. . . I removed some of these print statements because it looked pretty bad. . . .

I told you earlier not to edit the code; this time I am taking action. Please post the code as it stands, complete with print instructions, so we can run the code. Edits to posts already answered simply make the thread harder to read.
 
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You have special cases when the new node needs to go at the head or the tail, other wise you have to follow a chain but this time look at current.next. This way you'll have the two nodes that the new node needs to be inserted between.
 
Rancher
Posts: 978
23
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
William, i've not looked at your code, but if you will put up with my comments, this is what i've found wrong in most linked list work:

1 -- use a true "head" and "tail", if you possibly can, rather than the concept of first and last. it eliminates the need for special cases of ever replacing the head and tail--you will always insert sometime after the head, and sometime before the tail.
2 -- remember the only comparison done in your comparable implementation is your data item or items--what ever they may be.
3 -- you need to set 4 references, to do so you have to have a reference to your current node, the node to be inserted, and a reference to your next node from the current.
4 -- the links will always go like this:

Node2Insert.previous = CurrentNode
Node2Insert.next = CurrentNode.next

CurrentNode.next = Node2Insert

NexNode.previous=Node2Insert

notice how the use of a true "head" and "tail" does away with the need of swapping our the head and tail--ever.
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Les, I hadn't taken it to the next step. Much cleaner.

 
Les Morgan
Rancher
Posts: 978
23
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Carey,

i prefer to use a look ahead type of approach and key off of current.next != tail, but that is personal preference.

Les

Carey Brown wrote:Thanks Les, I hadn't taken it to the next step. Much cleaner.
public void insert( T item )
{
Node node = new Node( item );

if( isEmpty() )
{
insertAfter( node, head );
}
else
{
Node curr = head.next;
while( curr != tail && node.item.compareTo( curr.item ) >= 0 )
curr = curr.next;
insertAfter( node, curr.prev );
}
}



 
Marshal
Posts: 16598
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

William Golovlev wrote:

Al Hobbs wrote:minimize repeating lines. ("DRY") This increases readability and makes it easier to fix things.


What specifically are you referring to? If it is something outside of the insert method, I am not worrying about that as of now.


DRY is not just about minimizing mechanical character for character duplication; it's about avoiding logical duplication. Here's an example:

Lines 29 and 30 are redundant because you have this constructor:


Line 29 does what line 11 already did and line 30 does what line 13 already did.

And technically, lines 12 and 13 are redundant because reference fields are already initialized to null by default.
 
Junilu Lacar
Marshal
Posts: 16598
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This part of your insert method has a number of flaws:

The break statements on lines 41, 49, and 57 are wrong. Since these three if-statements cover every possible outcome of compareTo(), you end up comparing the new node to just the head node. You never actually go through the list.

Another thing that's wrong is line 59 - you're clobbering the head node. You shouldn't change the value of head unless you're inserting the new node before the current head node. All your other list operation methods use a current variable, why did you get away from that in your insert() method?

Line 56 is also redundant for the same reason I pointed out in my last reply: it's already done by the Node constructor.
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The OP made several edits to the code he posted and then eventually deleted. Line 35 originally read:
Edits should be forbidden once people have responded. Now the whole context is gone.
 
Junilu Lacar
Marshal
Posts: 16598
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's the insert() method I came up with:

I have it returning a reference to the current list because that allows chaining of multiple calls to insert(), like so:
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:Thanks Les, I hadn't taken it to the next step. Much cleaner.

As Les mentioned, if head and tail are Node's instead of Node references the above method works and is very succinct. The constructor would initialize them like this:

 
Norm Radder
Master Rancher
Posts: 4465
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Would that create a list with 2 empty Nodes in it?
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, but the storage required is minimum because their "item" references will be null.

Doing things this way means that you don't have special cases for head and tail conditions, linking and unlinking are implemented uniformly.
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The nodes themselves should never be accessible external to DoublyLinkedList so nobody else needs to know about the dummy head and tail nodes.
 
Norm Radder
Master Rancher
Posts: 4465
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How does that code compile if the Node constructor takes an argument?
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
 
Norm Radder
Master Rancher
Posts: 4465
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I take it the change was to add a new constructor.
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
 
Carey Brown
Saloon Keeper
Posts: 8609
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
 
Junilu Lacar
Marshal
Posts: 16598
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:As Les mentioned, if head and tail are Node's instead of Node references the above method works and is very succinct.


Ok, I did that and got it working:
 
Junilu Lacar
Marshal
Posts: 16598
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And my toString() is very similar:
 
Junilu Lacar
Marshal
Posts: 16598
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Ok, I did that and got it working:


And I compulsively composed the method:

 
Those cherries would go best on cherry cheesecake. Don't put those cherries on this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic