• Post Reply Bookmark Topic Watch Topic
  • New Topic

Doubly Linked List Insert to Middle  RSS feed

 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi there!  Hoping someone can maybe help me out.  I have a working doubly linked list program ready to turn in, but we were given an option for extra credit...insert in the middle.  I have no idea why I'm having so many issues with it.  It seems whatever I do screws up another part of my program to the point I just deleted it and am ready for a fresh try.  I'm not trying to be a programmer, this is not my strong suit.  I'm more into the hardware but this is required for my associates, so please bare with me in my lack of knowledge.  I have included the code.  I'm not looking for someone to do it for me, just maybe give me a starting point or some hints as to what to do so when I add it it doesn't affect the rest of my working program. 
Thanks in advance!




 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch!

What code changes did you try to make for adding an element in the middle? It would be easier to give you guidance if we knew what you tried that didn't work.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, by "adding in the middle" does that mean if you had 10 elements in the list, you'd add the new element between the 5th and 6th element?  Or does it really mean that you're inserting  the new element in such a way that it's not going to become either the head or tail of the list?  Are the semantics you want "insert before another element" or "insert after another element"?
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I were your instructor, I would give you double extra credit if you successfully implemented an insertBefore(Node other) method and an insertAfter(Node other) method, with the proper error checking and handling.
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is the code the teacher gave us to work with.  I tried switching it around to make it work with mine but every time I do I get an error message for another part of the program "dll.add" 
this is very frustrating.  I don't even care about the extra credit but I hate not understanding how to do it :/

I can't remember half the changes I made before I came here.  Sorry, like I said, this is not my strong suit

  
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:If I were your instructor, I would give you double extra credit if you successfully implemented an insertBefore(Node other) method and an insertAfter(Node other) method, with the proper error checking and handling.

this stuff already makes me want to cry.  doing all that would probably cause me to have a full blown meltdown.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:This is the code the teacher gave us to work with. ...  I don't even care about the extra credit but I hate not understanding how to do it :/

Well, we can certainly help you understand what this code is doing.

First of all, let's rename a few things, so the code is more expressive, and space things out a little so the code isn't so bunched up:

(continued...)
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So this is the (more expressive) code you were given as a starting point and you want to understand what

Lines 1 & 2 simply set up your "cursors" or placemarkers for where you are in the process of going through your list. You start at the head of the list so your current and your last "cursors" are going to be set to that initially.

Line 4 just does what the comment says: process the entire list until the curr variable doesn't reference any Node, which means you've reached the end of the list at that point.

Line 7 checks to see if the newData variable's value is less than the current Node's data value.  The "< 0" part is what says "is less than" -- see the documentation for compareTo()

Lines 8 & 9 - inserts newNode before the Node referenced by curr.

Lines 13 & 14 - advances your curr and [/tt]last[/tt] references forward, with last referencing the Node that curr was just referencing, then moving curr to the next Node in the List.

In summary, this code you were given to start with has "Insert Before" semantics with the additional condition that you insert newNode before the first Node in the list it finds where the newNode data is less than the other Node's data.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:this stuff already makes me want to cry.  doing all that would probably cause me to have a full blown meltdown.

It's not that hard. If you wrote all that other code yourself, you have actually done a bang-up job. you should try to show us what you did for the extra credit that didn't work. It's probably something very simple that you're missing. You already have all the code you need, all you need to do is create a method with the appropriate signature, pop in that code you were given, and you're done.
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:So this is the (more expressive) code you were given as a starting point and you want to understand what
[code=java]

Lines 1 & 2 simply set up your "cursors" or placemarkers for where you are in the process of going through your list. You start at the head of the list so your current and your last "cursors" are going to be set to that initially.

Line 4 just does what the comment says: process the entire list until the curr variable doesn't reference any Node, which means you've reached the end of the list at that point.

Line 7 checks to see if the newData variable's value is less than the current Node's data value.  The "< 0" part is what says "is less than" -- see the documentation for compareTo()

Lines 8 & 9 - inserts newNode before the Node referenced by curr.

Lines 13 & 14 - advances your curr and [/tt]last[/tt] references forward, with last referencing the Node that curr was just referencing, then moving curr to the next Node in the List.

In summary, this code you were given to start with has "Insert Before" semantics with the additional condition that you insert newNode before the first Node in the list it finds where the newNode data is less than the other Node's data.


I have the idea  of how this works.  Just not how to implement it in my code.  For example, in his code he has an accessor getData, I don't have that bc I'm avoiding it by keeping the inner class private so I don't need to use accessors or mutators. I mean I could rewrite my whole code to add those and I could probably easily insert in the middle, but I know there's got to be a way without using any accessors.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Although I should add that if you're to maintain the list as a doubly linked list, you need to add a couple of lines of code to the section where you're actually inserting the new node.  Other than that, it's very straightforward. Once you understand what needs to be done, writing the code itself takes less than 1 minute.  Understanding what needs to be done first and the rest is easy-peasy.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:... in his code he has an accessor getData, I don't have that bc I'm avoiding it by keeping the inner class private so I don't need to use accessors or mutators. I mean I could rewrite my whole code to add those and I could probably easily insert in the middle, but I know there's got to be a way without using any accessors.

You don't have to rewrite your code. You just have to declare T extends Comparable<T>  -- see this: http://stackoverflow.com/questions/8537500/java-the-meaning-of-t-extends-comparablet

This only requires the DoublyLinkedList to be used with types that support the Comparable interface, which defines the compareTo() method. When you do this, you don't need a getData() method, you just use the data values directly with compareTo(). That would actually be a better way than what your instructor gave you as an example:
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:Although I should add that if you're to maintain the list as a doubly linked list, you need to add a couple of lines of code to the section where you're actually inserting the new node.  Other than that, it's very straightforward. Once you understand what needs to be done, writing the code itself takes less than 1 minute.  Understanding what needs to be done first and the rest is easy-peasy.


none of this is easy peasy for me.  I spend hours researching to figure out my kinks.  I absolutely detest java.  no matter how hard I try I will never write any code in a few minutes.  I'd settle for a few hours as it takes me days now and has cost me 3 computers bc sometimes I'd rather throw a computer than deal with this nonsense. Teacher tells me read the book, which I have and have aced every test.  these sites tell me it's so easy, but that's all I learn...it's easy. <-- this helps me none.   I'm NOT a programmer.  I'm very NEW to this. I really need it dummied down to the fullest.   

sorry for the frustration but every time I come to one of these"helpful sites"  someone says it's easy if you figure this or that out.  If I figured this or that out I wouldn't be here. It's definitely not easy.  I guess saying it's easy triggers the inner b*tch in me lol

so again, I understand how my teacher did it. Like I said I could rewrite the whole code the way my teacher did and probably do it easy, but I want to know how I can implement the same idea w/o adding an accessor such as "getData"
What am I missing?
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Dawn Goxhaj wrote:... in his code he has an accessor getData, I don't have that bc I'm avoiding it by keeping the inner class private so I don't need to use accessors or mutators. I mean I could rewrite my whole code to add those and I could probably easily insert in the middle, but I know there's got to be a way without using any accessors.

You don't have to rewrite your code. You just have to declare T extends Comparable<T>  -- see this: http://stackoverflow.com/questions/8537500/java-the-meaning-of-t-extends-comparablet

This only requires the DoublyLinkedList to be used with types that support the Comparable interface, which defines the compareTo() method. When you do this, you don't need a getData() method, you just use the data values directly with compareTo(). That would actually be a better way than what your instructor gave you as an example:


THANK YOU!!!  That was just what I needed!! I was so focused on that darn accessor and thought it was the end of the world! 
Thank you for dummying it down for me!
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:I guess saying it's easy triggers the inner b*tch in me lol
...
What am I missing?

You missed the reply I posted just before you posted your rant

If you wrote all that code you originally posted, I guess I'm surprised why you would still say that it's very difficult to understand. That code shows a very good understanding of the inner workings of a doubly-linked list. Either you're letting your inner b*tch get the best of you or you need to get whoever wrote that code to explain it some more to you. Don't take this the wrong way but if you say it's still frustrating, that really makes me doubt whether that all that code is actually yours. Just sayin'. As I said before, that code you originally posted is actually very well written, not just in terms of style but also in substance. It's a pretty darn good job, especially for a beginner.

EDIT: Oh... and I guess you got me right back and posted something that I missed. 
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:so again, I understand how my teacher did it. Like I said I could rewrite the whole code the way my teacher did and probably do it easy, but I want to know how I can implement the same idea w/o adding an accessor such as "getData"
What am I missing?

I have to admit not having gone through the entire thread, but it would appear to me that what you're "missing" is how to use that wonderful
  public Node(T newData, Node<T> previousValue, Node<T> nextValue)
constructor that you've already written.

You appear to want to insert a value somewhere in the "middle" of your List - ie, before or after some specific Node - but you're confusing the problem by ALSO trying to find the Node. I'd say you're also compounding the problem by trying to use an iterator to do it, but I could be wrong.

Deal with the two problems separately:
1. Find the Node you want to insert before or after.
2. Write methods that will insert a new Node before or after ANY Node in your List - including 'head' and 'tail'.
Your add() method already adds a new Node after 'tail', so maybe have a think how you could make it a bit more generic.

HIH

Winston
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you're still inclined to do so, please post your final code. It will be very interesting to see the solution you end up going with and maybe we can still point out something you may have missed.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:it would appear to me that what you're "missing" is how to use that wonderful
  public Node(T newData, Node<T> previousValue, Node<T> nextValue)
constructor that you've already written.

This is a great hint that invalidates what I said earlier about having to add a few lines of code to what you were given. Do what Winston suggests and all you have to do is replace everything that your instructor gave you with ONE line of code.

Edit: to clarify, by "everything", I mean:


Excellent point, Winston! 
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:Thank you for dummying it down for me!

You give yourself too little credit. That wasn't a dumbing down, it was showing you a better way to do it. Better ways to do things are often simpler and easier to understand; that's what's called "elegance".  It takes a certain level of sophistication to understand and appreciate elegance, so rather than dumbing it down, I was actually raising it up a level and apparently it's a level at which you currently feel comfortable working. 
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:If you're still inclined to do so, please post your final code. It will be very interesting to see the solution you end up going with and maybe we can still point out something you may have missed.


Sorry, didn't check this after I got what I needed and was occupied with holiday cooking for last couple days. My bad lol
How I did it:
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:Sorry, didn't check this after I got what I needed and was occupied with holiday cooking for last couple days. My bad lol
How I did it:

Hmmm. +1 for providing your solution, but I see some possible problems with it:

It would appear to use a variable called 'position', but doesn't actually set it (or "find" it) anywhere; which suggests to me that it's in the body of your class somewhere.
Now if this method is in your DllIterator class, that's probably fine, but if it's in your DoublyLinkedList one, it's almost certainly wrong; because that would mean that your list has a permanent "current element" pointer, which doesn't make much sense.

Tip: Instead of doing all the insertion in addMiddle(), what about adding an addBefore() method to your Node class? Perhaps something like:The advantage of doing it that way is that you know that 'this' cannot be null, and in the case where the list is empty, addMiddle() can still use its add() method instead.

BTW: Did you notice that I added 'static' to your Node declaration? There's no real need for it to be an inner class, because you never use any of the outer class's data.

HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:Sorry, didn't check this after I got what I needed and was occupied with holiday cooking for last couple days.

I've also noticed another problem (I think). You've set all the forward pointers correctly; but I suspect that you haven't set the backwards ones. Easiest is probably to get your Node constructor to do everything, viz:
Happy Thanksgiving!

Winston
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks for pointing that out which made me see another mistake.  I wasn't getting a compiler error bc I had it plugged in with my iterator...so position was set.  I moved it outside and I got the exact error you said...could not "find" it. 
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
and Happy Thanksgiving to you as well ;)
 
Dawn Goxhaj
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It would appear to use a variable called 'position', but doesn't actually set it (or "find" it) anywhere; which suggests to me that it's in the body of your class somewhere.
Now if this method is in your DllIterator class, that's probably fine, but if it's in your DoublyLinkedList one, it's almost certainly wrong; because that would mean that your list has a permanent "current element" pointer, which doesn't make much sense.

that was an easy fix (I think) by just adding this before my if statement:

also when I said I added to the iterator...I misspoke...it was the doublylinkedlist :/

it is compiling now w/ no errors. 

not to build my main method.  blah.  at least that should be way easier haha
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dawn Goxhaj wrote:that was an easy fix (I think) by just adding this before my if statement:

I don't think that'll be enough because that means that when you execute the if statement, 'position' will always be null, which means it will throw a NullPointerException whenever the list is empty.

However, it's now a bit difficult to follow everything that you've changed, so could you post the latest version of the whole thing?

Winston
 
Anton Golovin
Ranch Hand
Posts: 531
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, Dawn,

In general...

You must iterate a linked list in O(N) fashion, meaning just iterate to the middle of the list (this list must know how many items are in it with a simple method call) and rearrange the references in the item just before the middle and just after the middle to point to a new item that you are inserting.

You have to account for a fact that a doubly linked list is traversable in both directions, so references must be re-assigned not in one (for a singly linked list it is ok) but in two objects just before and after the insertion point.

With best regards,

Anton.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!