This week's book giveaway is in the Mac OS forum.
We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line!
See this thread for details.
The moose likes Java in General and the fly likes Creating a linked list with nodes from different list. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Java in General
Bookmark "Creating a linked list with nodes from different list." Watch "Creating a linked list with nodes from different list." New topic
Author

Creating a linked list with nodes from different list.

akash negi
Greenhorn

Joined: Feb 24, 2010
Posts: 27
Hi all, I am given the following:

IntNode IntNode findAfter(IntNode head, int value): Find all values that occur immediately after an occurrence of value, and return the results as a new IntList object containing those values in the same order as in the original list. This method should not alter the input list.
For example, if the list is currently

4 -> 9 -> 7 -> 3 -> 12 -> 4 -> 1 -> 10
and we call findAfter(list, 4), the original list should be unchanged, and we should receive this new list:

9 -> 1



for the above question, I have the following code. However my code only extracts one occurrence..
Instead of 9 and 1, it only extracts 1.

I think that it also extracts 9 but I don't have any code to save that and add on the next occurrence.

This is one of the practice problems for Final exam on monday. So if there is a trivial addition needed, please feel free to add the line explicitly.




Thanks!!
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

Don't you think it'd be better if you worked a little harder on these questions yourself? You've already discovered that the simple act of using a pen/pencil and paper helps--why not try it with this problem as well?
akash negi
Greenhorn

Joined: Feb 24, 2010
Posts: 27
David, not to sound rude or anything, but if everything was solvable with a pen a paper, then why would java help forums exist? I tried to solve it with a pen and paper. Then I went one level up and sought help from a friend. Neither of these two helped.
So, in hopes to get an answer from helpful volunteers, I posted it here.

I know that self help is the best help, but it is not "always" the case. Sometimes we need to get help from outside sources as well and given my level of java knowledge, it is tough for me to get self help.

I have modified this code many times but the most accurate answer I could get is the one posted here with this code..

Thanks.


David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

not to sound rude or anything, but if everything was solvable with a pen a paper, then why would java help forums exist?

It's never rude to simply disagree--people disagree with me all the time. But the Java forums exist for Java questions--so far this is an algorithmic one, and if you don't figure out how to figure out this kind of question, the point of the practice exam will be lost.

A single iteration via pencil-and-paper, preferably with a picture of the resulting data structure, is enough to pinpoint what's gone wrong: I honestly don't believe you've done this, because if you had, you would immediately see why the code above isn't working--the problem is visible within an iteration or two if pointer.data == value evaluates to true.

How about this--post a text description of what you think is happening using the data you've given as the example. Post the picture (or a link to it) of the data structure you're building in the code, and we'll take it from there.
Ireneusz Kordal
Ranch Hand

Joined: Jun 21, 2008
Posts: 423
I think you should rewrite your code and divide it into basic steps - this will make it easier to read and correct errors.
Maybe like this (pseudo-code):
akash negi
Greenhorn

Joined: Feb 24, 2010
Posts: 27
The text description:-

4 -> 9 -> 7 -> 3 -> 12 -> 4 -> 1 -> 10

9 -> 1

IntNode object head is passed on to this method.

The while loop will execute until the pointer is null - (traversing through the list)

First Iteration:

pointer.data = 4
value = 4
so the if condition is true. A IntNode temp will be made equal to 9 which is to be extracted. - - - - This is the value which we wish to keep.
pointer is then equal to pointer.next. So now the pointer is 9 -> 7 -> 3 -> 12 -> 4 -> 1 -> 10

Second Iteration

pointer.data = 9
value = 4
so the if condition is false. So nothing happens except for the pointer now changing to 7 -> 3 -> 12 -> 4 -> 1 -> 10

This goes on for many more iterations until pointer.data = 4 again

Many iterations later

pointer.data = 4
value = 4
so the if condition is true. IntNode temp is initialized again but now with a different value. Now the value is 1. The old value of 9 (from 1st iteration) is now lost.

- - - - New value is stored but the old one is lost. How to link those two?

There are a few more iterations until the pointer becomes null. When it does become null, the loop is stopped and temp is returned.

When temp is created outside the loop, the default value stored is 0. and when we say "temp.next = tempforever" (in the while loop), the new node is AFTER the 0. so after first iteration temp list looks like this:

0->1
So the list that is returned is as above, this could easily be corrected be saying return temp.next instead of temp. temp.next will return only 1.

The problem is that I do not have anything to link the different values together. the code works as expected but it never saves the older value. It replaces the old value with the most recent one.
How could that be corrected?


David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

If you need to save a value--how does one do that in Java? Create a variable and set it.
akash negi
Greenhorn

Joined: Feb 24, 2010
Posts: 27
David Newton wrote:If you need to save a value--how does one do that in Java? Create a variable and set it.


but the total number of possible elements in the given list could be 1 (where we have to extract only 1) or it could be 100. So I think that creating variables should be the last option.

4->1->5->4->23->55->4->99 - - extract 1->23->99 (3 elements)

or

1->5->4->2->43 - extract 2 (1 element)
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

But you're creating a list: each node has a variable that points to the next element--the only one you need to keep a local reference to is the one you're returning: the head node of the returned list.
akash negi
Greenhorn

Joined: Feb 24, 2010
Posts: 27
Hi, so finally I decided to go with recursion.. I think recursion is just a tad easier.






I was very close to getting the answer without recursion but the whole reference thing just ate up my mind and I thought it would be better to start with a new idea from scratch.


Thanks David !


David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

That's awesome--some folks would consider the recursive version harder, too.

You were very close with the iterative version--you just needed to return a reference to the original head of the new list, and keep a reference of the most-recently-added node in order to set its "next" element. You actually do the same thing in the recursive version, just in a different way :)
 
GeeCON Prague 2014
 
subject: Creating a linked list with nodes from different list.