Jump to content
  • Advertisement
Sign in to follow this  
hisDudeness

traversing LinkedList

This topic is 4859 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I've scoured through the Java API Specification covering the LinkedList list structure, and I'm still confused. I want to run a simple traversal through the list, and check each node for a particular condition. This is the best that I've come up with so far: LinkedList list = new LinkedList(); /* pretend I just populated the list full of Widgets */ ListerIterator iter = new ListIterator(); iter = list.listIterator(); while(iter.hasNext()) { if(iter.next().x_val == 1) { /* blah */ } else if(iter.next().x_val == 2) { /* blah */ } // ... etc. } The problem is, every time I call iter.next(), I think I'm stepping one node further through the list. Ergo the node I'm checking in the first 'if' statement is not the same node I'm checking in the second 'else if' statement. How do I check the same node without stepping further through the list???

Share this post


Link to post
Share on other sites
Advertisement
Notice that Iterator.next() is an accessor with a side effect: It first steps to the next node of the list, and returns that. There is no other accessor defined. So you have to follow SiCrane's suggestion:

while(iter.hasNext())
{
final Widget current = (Widget)iter.next();
if(current.x_val == 1) { /* blah */ }
else if(current.x_val == 2) { /* blah */ }
// ... etc.
}



BTW: Such a behaviour is sometimes a topic of discussion about good programming style, so I don't wonder if you (hisDudeness) have a problem with it. People like Booch have mentioned that it would be better to have distinct "extractors" and "manipulators", like in

interface Iterator {

// manipulator: steps to next node
public void next();

// extractor: the value of the current node
public Object current();
}


However, that way is not such efficient as the actual implementation, and sometimes suffers from initial value problems.

Share this post


Link to post
Share on other sites
SiCrane & haegarr -- thank you!

Unfortunately my original post was a little too vague. Let me better explain the scenario:

I have a base class called AtomicExpression. It's a wrapper class for all of its children, which, naturally, are extensions of this class. Examples of these child classes are: Variable, Number, SymbolicConstant, etc. (I'm writing a math program, yuck.) So all of these classes extend AtomicExpression.

I'm storing math formulas in a LinkedList. For instance, let's take a simple expression such as "3 + 4":

Number three = new Number(3);
BinaryOp plus = new BinaryOp('+');
Number four = new Number(4);

LinkedList list = new LinkedList();
list.add(three);
list.add(plus);
list.add(four);

ListIterator iter = new ListIterator();
iter = list.listIterator();

AtomicExpression stepNode = new AtomicExpression();
while(iter.hasNext())
{
stepNode = (AtomicExpression)iter.next(); // thank you SiCrane & haegarr!!!
if(stepNode instanceof Number) {}
else if(stepNode instanceof BinaryOp) {}
// ... etc.
}

The problem is, now I'm worred that when I cast the Object returned in iter.next into an AtomicExpression, that the data members and info contained in Number, BinaryOp and Number (respectively) will be lost.

Since I have now been forced to typecast stepNode back into the wrapping parent class, how can I chec for what data type each node in the list is?

Share this post


Link to post
Share on other sites
The way you've posted is already one possible solution:

while(iter.hasNext())
{
stepNode = (AtomicExpression)iter.next(); // thank you SiCrane & haegarr!!!
if(stepNode instanceof Number) {
Number number = (Number)stepNode;
// do something with number
} else if(stepNode instanceof BinaryOp) {
BinaryOp op = (BinaryOp)stepNode;
// do something with op
}
// ... etc.
}

Share this post


Link to post
Share on other sites
However, if I'm allowed to make a totally other suggestion (I make it anyway ;-)

One of the big issues of OOP is to avoid exact knowledge of types. This could be reached by polymorphism. If you look at the iterative solution above, you'll see that evaluating an expression is somewhat problematic since you must remember previous states of evaluation.

A way to solve this problem would be letting the classes itself decide what to do. I don't know whether your problem is of such a structure, but please have a look at this:

public abstract class Expression
extends Object {

public abstract float evaluate();

}

public class Number
extends Expression {

public Number(float withValue) {
this.value = withValue;
}

private float value;

public float evaluate() {
return this.value;
}

}

public class BinaryOp
extends Expression {

public BinaryOp(Expression atLeft,Expression atRight) {
this.left = atLeft;
this.right = atRight;
}

public Expression leftExpression() {
return this.left;
}

private Expression left;

public Expression rightExpression() {
return this.right;
}

private Expression right;

}

public class BinaryPlus
extends BinaryOp {

public BinaryPlus(Expression atLeft,Expression atRight) {
super(atLeft,atRight);
}

public float evaluate() {
return leftExpression() + rightExpression();
}

}

public class BinaryMinus
extends BinaryOp {

public BinaryMinus(Expression atLeft,Expression atRight) {
super(atLeft,atRight);
}

public float evaluate() {
return leftExpression() - rightExpression();
}

}


As you could see here, the expression isn't modelled as a sequence but as a tree. This reflects immediately also bracketing. It also allows functions like min() or max() or floor() or ... whatever.

In parallel to evaluate() also a toString() may be implemented to transfer the expression back to a string. Other such things are possible, too.

EDIT: Bugs in accessing super class fields corrected.

[Edited by - haegarr on December 1, 2005 12:47:51 PM]

Share this post


Link to post
Share on other sites
You could, of course, do something similar with a linked list, but not in such an easy way. If you insist on the list paradigm, I suggest something like this:

public abstract class Expression
extends Object {

public abstract void evaluate(Stack stack);

}

public class Number
extends Expression {

public Number(float withValue) {
this.value = withValue;
}

private float value;

public void evaluate(Stack stack) {
stack.push(this.value);
}

}

public class BinaryPlus
extends Expression {

public void evaluate(Stack stack) {
float result = stack.pop() + stack.pop();
stack.push(result);
}

}

public class BinaryMinus
extends Expression {

public float evaluate(Stack stack) {
float result = stack.pop() - stack.pop();
stack.push(result);
}

}



Then you could do something like

Stack stack = new Stack();
while(iter.hasNext()) {
final Expression expression = (Expression)iter.next();
expression.evaluate(stack);
}
System.out.prinln((float)stack.pop());


Notice that, although looking smarter at the moment, this solution is less flexible in comparison to the tree solution, since each next funtionality (e.g. toString()) needs support from outside (also the stack is such a support).

(I've written this from mind, so please forgive me if there were syntax errors. Notice furthur that some state checking has to be implemented, of course, to detect usage errors.)

[Edited by - haegarr on December 1, 2005 12:03:57 PM]

Share this post


Link to post
Share on other sites
In Java, that cast will not "slice" the object like it would in C++ - no worries. The necessary layer of indirection is managed for you under the hood.

On the other hand, if you're going to do an instanceof check anyway, there's no real point in the cast to AtomicExpression (all it will accomplish is to throw ClassCastException if you put some other kind of Object into your LinkedList - of course, that's a problem too, but it would be nicer to catch it at compile-time... *). You really should be making use of polymorphism here.

* In Java 1.5, the new 'generics' feature allows for specifying a LinkedList<AtomicExpression> , similar in effect (although not nearly the same in implementation) as C++ templates. Older versions do not support this, so when you up-cast to Object, the type information is lost indefinitely. Although actually, all the generics really do at runtime is automate the down-cast :s but at least it allows for some compile-time error checking.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!