Sign in to follow this  

list traversal

This topic is 4352 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

[again in Java] I can't seem to find a ListIterator method in the JavaDocs that allows the programmer to manually set the location of the iterator at a specific location in the list. For example, this is how you normally implement a LinkedList traversal:
LinkedList<Widget> list = new LinkedList<Widget>();
ListIterator<Widget> iter = list.listIterator();
Widget stepNode = new Widget();

while(iter.hasNext())
{
    stepNode = iter.next();

    // Then do whatever your traversal does
}

But how can I specify for my 'iter' ListIterator to begin at the, say, 4th node in the list? The 20th? The nth?

Share this post


Link to post
Share on other sites
Have you tried just for-looping from 0 to <4 iter.next? Throw in some error checking too in case you hit the end of the list.

Usually, lists are used in cases where you run through the whole collection. In what kind of circumstance would you need to go from the n-th node to the end?

Share this post


Link to post
Share on other sites
Not all containers are/can be designed for "random access". A LinkedList is conceptually, well, a linked list, where the only way to find the nth node in memory is to traverse from the beginning and follow the pointers (or to have a cached reference from a previous traversal).

So yeah, just advance (.next()) a new iterator n times (assuming you count the initial element as zeroth, as you would with arrays).

Share this post


Link to post
Share on other sites
Fair enough!

Okay so now this leads me to my 2nd question. I Have a LinkedList traversal inside a for-loop. I want the for-loop to iterate five times (five separate list traversals back to back).

Each time the for-loop iterates, I want to remove a different node from the LinkedList, thus resizing the original list each time. But my remove() calls are getting ItemsOutOfBoundsExceptions and blowing up at runtime:


int i;
int widgetToRemove = 0; // The index inside the list of the node to be removed
LinkedList<Widget> list = new LinkedList<Widget>();
ListIterator<Widget> iter = list.listIterator();
Widget stepNode = new Widget();

for(i = 0; i < 5; i+)
{
while(iter.hasNext())
{
stepNode = iter.next();

// Code that identifies which particular node we wish to remove
// during this traversal, identified at index 'widgetToRemove'
}

list.remove(widgetToRemove);
}



Now the only thing I could figure is that, since I'm resizing the list and then subsequently traversing it with the same list iterator, that perhaps by reassigning the 'iter' data to a new rendition of 'list', that it would work without complaint. And so I add the line:

iter = list.listIterator();

Underneath the calling of remove(). This way, every time the traversal finished, 'iter' is set to what I thought would essentially be a new linked list. Not the case.

Does anybody have any suggestions? And if you're wondering what I'm doing, I'm locating an arithmetic operator ('+','-','*',etc.) and removing its two operands during each of the five loops. So I'm actually looking to remove TWO nodes from the list each traversal, not just one.

Share this post


Link to post
Share on other sites
Zahlman:


ListIterator<Widget> iter = ng.group.listIterator();
int iterIndex = -1;
int lRemove, rRemove;
lRemove = rRemove = -1;
NestedGroup lOperand, rOperand, resolvedExpression;
BinaryFunction tempBF;
for( ; currPrecLevel > 0; currPrecLevel--)
{
while(iter.hasNext())
{
stepNode = iter.next();
iterIndex++;

// 4. If the current operation is of the correct precedence
// level, perform that operation.
if(stepNode instanceof BinaryFunction)
{
tempBF = (BinaryFunction)stepNode;

if(tempBF.precLevel == currPrecLevel)
{
lOperand = tempBF.lArg;
rOperand = tempBF.rArg;

if(tempBF.id == DIVISION)
resolvedExpression = divide(lOperand,rOperand);

else if(tempBF.id == MULTIPLICATION)
resolvedExpression = multiply(lOperand,rOperand);

else if(tempBF.id == ADDITION)
resolvedExpression = add(lOperand,rOperand);

else if(tempBF.id == SUBTRACTION)
resolvedExpression = subtract(lOperand,rOperand);

lRemove = iterIndex - 1;
rRemove = iterIndex + 1;

// Remove the two operands (ergo resizing the list)
ng.group.remove(lRemove);
ng.group.remove(rRemove);

// Set the resolved expression in place of the current
// operator
iter.set(resolvedExpression);
}
}
}

// Reset the index counter to -1 every new for-loop cycle
iterIndex = -1;

// Finally, set the iterator to the "new" linked list (the resized list)
iter = ng.group.listIterator();
}



This compiles but throws an IndexOutOfBoundsException at runtime. Is it possible, perhaps, that Java prohibits the resizing of a list during the traversal? I couldnt find evidence of that in the JavaDocs, but then again, I've been known to have been mistaken in the past, on one or two occassions.

If that's not the solution, then for the life of me, I can't figure out what is wrong. I'm simply removing the two nodes (the operands) to the left and right of the currently-iterated-to-node, and then reassigning the iterator to the newly-resized list at the very end.

yipes!

Share this post


Link to post
Share on other sites
I think your iterIndex is your problem. You increment it once on each loop, even though on some loops you decrease the size of the list. For a simplified example, consider the following:
import java.util.*;

class ListProblem
{

public static void main(String args[])
{
LinkedList< Character > chars = new LinkedList< Character >();
chars.add('1');
chars.add('+');
chars.add('1');
ListIterator< Character > iter = chars.listIterator();
int index = -1;
while (iter.hasNext())
{
char c = iter.next(); // equivalent of stepNode = iter.next();
++index;
if (c == '+') // if (stepNode instanceof BinaryFunction)
{
// assume tempBF.precLevel == currPrecLevel always true

// result replaces resolvedExpression
char result = (char)('0' + ((chars.get(index - 1) - '0') + (chars.get(index + 1) - '0')));

chars.remove(index - 1);
chars.remove(index + 1);
chars.set(index, result);
}
}
}

}

On the first iteration chars == {'1', '+', '1'}, c == '1' and index == 0. The conditional is false and so we move on to the next iteration. Now chars == {'1', '+', '1'}, c == '+' and index == 1. The conditional is true, so we get the chars at indices index - 1 and index + 1, which evaluate to 0 and 2 and give us chars '1' amd '1'. We add them together to get a char with value '2'. We now remove the list element at index index - 1, which evaluates to index 0. This leaves the list chars == {'+', '1'}. We then try and remove the list element at index index + 1, which evaluates to index 2. But the list no longer has a valid element at index 2, only indices 0 and 1, so the JVM throws an IndexOutOfBoundsException.

Even when you fix that I'm not sure what guarantees (if any) Java makes about the validity of iterators when you modify the underlying collection. I suspect that you'd be much safer to modify the list via the iterator, which is at least guaranteed to work under some constraints (see the JavaDocs for ListIterator).

Enigma

Share this post


Link to post
Share on other sites

This topic is 4352 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this