I’m desperately seeking a little help with a Java program dealing with Singly Linked Lists and the insertion of nodes (which sounds almost inappropriate) at the beginning of the list. For some reason no matter what I think of to try it doesn’t want to work. Anyone out there with a helpful tip?

Hi, Fee.

I assume you’ve already looked at sites like tutorialspoint and done a quick search on Stack exchange.

Sorry, I don’t do Java. But IIRC Dropbear does.

In the mean time, you might want to post a few more details about the problem you’re having.

Are you using the standard LinkedList class or is it your own custom class?

What happens when you try to add a new node to the head of the list?

Can you insert nodes successfully at other locations in the list?

It may not be a problem with the list, per se, but with how you’re referencing the node(s)… but as I said, I know next to nothing about Java.

Maybe post a small version of your program that illustrates the problem. This forum isn’t great at handling source code, but you can post code for free and anonymously at Pastebin (i.e., no registration is required) and post the link here. Pastebin has options for syntax highlighting, which makes it easier to read source code.

PM 2Ring said:

Hi, Fee.

I assume you’ve already looked at sites like tutorialspoint and done a quick search on Stack exchange.

Sorry, I don’t do Java. But IIRC Dropbear does.

In the mean time, you might want to post a few more details about the problem you’re having.

Are you using the standard LinkedList class or is it your own custom class?

What happens when you try to add a new node to the head of the list?

Can you insert nodes successfully at other locations in the list?

It may not be a problem with the list, per se, but with how you’re referencing the node(s)… but as I said, I know next to nothing about Java.

Maybe post a small version of your program that illustrates the problem. This forum isn’t great at handling source code, but you can post code for free and anonymously at Pastebin (i.e., no registration is required) and post the link here. Pastebin has options for syntax highlighting, which makes it easier to read source code.

Hi PM

thanks for the reply. I have not tried those sites but will. I have been driving myself nuts trying to independently figure this out, I am pretty sure my logic is ok but my coding seems to be letting me down.

Its a custom class, the class definition, most of the methods and the test program have been supplied. I am required to write a method called add, which is called via another method called plus and adds expressions to a polynomial stored as a linked list. It’s the insertion at the front I am having trouble with. The insertion elsewhere seems to work ok with the data I am required to work with.

I have 8/10 of the polynomials created correctly but that was because all of them are presented in a way that I do not have to insert a node at the front. It appears that when I insert the node within the add method it is fine (using the debugger I can see everything is as it should be), but once it returns back to the calling plus method the inserted node and links disappear.

(If you wonder why I am putting myself through this I am doing a Computer Science degree :) )

I will try your suggestions :)

be nice to see the code

Hi SCIENCE

public static void add(Polynomial polynomial, double coefficient, int power) { if (polynomial null) return; if(Math.abs(coefficient) < epsilon) coefficient = 0.0; if(coefficient 0.0)return; if (power < 0) return;

//Find insertion points for polynomial Polynomial newNode = new Polynomial(coefficient, power); Polynomial first = polynomial; //Insertion at front of linked list if(polynomial == null || polynomial.powerMax() < power) { newNode.successor = polynomial; polynomial = newNode; return; } //Insertion between nodes or at the end of the linked list Polynomial curr = polynomial; Polynomial pred = null; //navigate to point in SLL whwere node belongs while(curr != null && curr.power > power) { pred = curr; curr = curr.successor; } if(curr == null || power != curr.power) { pred.successor = newNode; newNode.successor = curr; } else { curr.coefficient += coefficient; if(curr.coefficient <= 0) { if (pred != null) { pred.successor = curr.successor; } else { first = first.successor; } } } if (polynomial.cardinality() <= 1 && polynomial.coefficient == 0) { polynomial = null; } return; }

that is the method that I believe is not working, when it returns to the calling method I lose the pointers but only on the polynomials I am creating where the node needs to be inserted at the front.

this is the calling method

final public Polynomial plus(Polynomial that) { if (that==null) return null; if (this.coefficient==0.0) return that.clone(); Polynomial result=this.clone(); if (that.coefficient==0.0) return result; Polynomial traverser=that; do { add(result,traverser.coefficient,traverser.power); traverser=traverser.successor; } while (traverser!=null); return result; }

and this is the code (and polynomials) I am meant to be creating, all but the last two appear to work :)
abstract class PolynomialTester
{ static Polynomial p=null; static Polynomial p0=new Polynomial(-1.0,0); static Polynomial q0=new Polynomial(0.0,0); static Polynomial r0=new Polynomial(1.0,0); static Polynomial p1=new Polynomial(-1.0,1). plus(new Polynomial(1.0,0)); static Polynomial p2=new Polynomial(1.0,2). plus(new Polynomial(-1.0,1)). plus(new Polynomial(1.0,0)). plus(new Polynomial(1.0,2)); static Polynomial p3=new Polynomial(-3.0,3). plus(new Polynomial(2.0,2)). plus(new Polynomial(-1.0,1)). plus(new Polynomial(0.5,0)). plus(new Polynomial(0.5,0)); static Polynomial p4=new Polynomial(4.0,4). plus(new Polynomial(-2.0,2)). plus(new Polynomial(1.0,0)); static Polynomial p5=new Polynomial(-5.0,5). plus(new Polynomial(3.0,3)). plus(new Polynomial(-1.0,1)); static Polynomial q5=new Polynomial(-0.5,1). plus(new Polynomial(-2.5,5)). plus(new Polynomial(2.5,5)). plus(new Polynomial(-5.0,5)). plus(new Polynomial(3.0,3)). plus(new Polynomial(-0.5,1)); static Polynomial s0=new Polynomial(-5.0,5). plus(new Polynomial(5.0,5)). plus(new Polynomial(3.0,3)). plus(new Polynomial(-1.0,1)). plus(new Polynomial(1.0,1)). plus(new Polynomial(-3.0,3));

Only q5 seems to involve adding to the front?

I wonder if the problem is in this part…

public static void add(Polynomial polynomial, double coefficient, int power) { ... if(polynomial == null || polynomial.powerMax() < power) { newNode.successor = polynomial; polynomial = newNode; return; } }

Your add() receives a copied reference to polynomial, but then it assigns a new value to it. The fact that this function has no return value suggests that you need a different way to update the original reference from outside the function.

The variable polynomial here is a copy with its scope within this function so assigning to it does not affect the outside reference to polynomial.

I don’t know what your task strictly specifies, but if this truly is the location of the bug, then one trick I used in my Dirty Days of C was to have an extra dummy node at the start.

Of course, I still use C, just as Real Programmers Still Use Machine Code.

sorry about the formatting, I haven’t worked out the optimal layout control tags for this forum

I’ve been there dozens of times.

dv said:

I’ve been there dozens of times.

Did you meet any experts there?

SCIENCE said:

Only q5 seems to involve adding to the front?

I wonder if the problem is in this part…

public static void add(Polynomial polynomial, double coefficient, int power) { ... if(polynomial == null || polynomial.powerMax() < power) { newNode.successor = polynomial; polynomial = newNode; return; } }

Your add() receives a copied reference to polynomial, but then it assigns a new value to it. The fact that this function has no return value suggests that you need a different way to update the original reference from outside the function.

The variable polynomial here is a copy with its scope within this function so assigning to it does not affect the outside reference to polynomial.

I don’t know what your task strictly specifies, but if this truly is the location of the bug, then one trick I used in my Dirty Days of C was to have an extra dummy node at the start.

Of course, I still use C, just as Real Programmers Still Use Machine Code.

Your formatting was better than mine :)

That is what I thought, although I can’t quite work out how to solve the problem. We were given the code for the rest of the class Polynomial and also the definition private static void add() as our starting point.

From what I can tell we are supposed to work it out from there but I have no idea how to access the original reference pointer. Ah, the joys of learning hey? I imagine all will become clear once I have handed the darn thing in and gotten my feedback :P It’s been a really interesting learning journey wrapping my head around this so I am gratified to know that at least my thinking was sound as to what the problem was.

Thank you again SCIENCE, I really appreciate your help

The Rev Dodgson said:

dv said:

I’ve been there dozens of times.

Did you meet any experts there?

From what I hear dv – you are indeed an expert…… and when you are in that part of the world that would make you an expert in Java.

thank you also to you and Rev for the laugh….needed it :)

Pass by reference dammit. Don’t make me tell you again…

http://stackoverflow.com/questions/5614562/how-to-do-the-equivalent-of-pass-by-reference-for-primitives-in-java

Dropbear said:

Pass by reference dammit. Don’t make me tell you again…

So I guessed right then. Good. :)

PM 2Ring said:

Dropbear said:

Pass by reference dammit. Don’t make me tell you again…

So I guessed right then. Good. :)

This doctoring stuff is easy, I diagnosed her fault through various hazy clues late last night over chat….

Sexy tiems…

SCIENCE said:

sorry about the formatting, I haven’t worked out the optimal layout control tags for this forum

It’s a pain. You need to disable Textile markup, and use pre-formatting. But it still sucks for posting code because the forum eats square brackets. And of course angle brackets don’t fare well, either.

---

Some fake code
    with {indenting}
    and
         even more indenting
    with [brackets]
         some <angle brackets>
         and (parentheses)

---

For small code samples, I guess it doesn’t really matter, since you can see the original layout in the reply textview when you Quote the post. But Pastebin works well…