CODEWITHSUNDEEP
javaiteratordoubly-linked-list
Phucci
Phucci

Reputation: 1

Java listIterator() is giving me weird outputs with .next() and .prev()

I've been working on a project where I implemented a (Doubly Linked List) from scratch with a separate "Node class".

I have then gotten to the point where I need to sort my "Linked List of Nodes". Since I implemented my Linked List from scratch, so in order to sort it, I have to implement a "Merge Sort" from scratch for my Linked List as well, which is a bit of time consuming to do.

So I thought about using "Java Linked List" from java.util with the listIterator() then use Collections.sort() to sort my LinkedList, but its next() and previous() are giving me some unexpected weird outputs vs when I was traversing my LinkedList of Nodes with direct access using (.next) & (.prev). For example, let's say:

node1.time = 7;
node2.time = 8;
node3.time = 9;
node4.time = 10;

LinkedList<Node> nodeList = new LinkedList<Node>():
nodeList.add(node1); nodeList.add(node2); nodeList.add(node3); nodeList.add(node4);

void testFunction() {

  ListIterator<Node> nodesIterator = nodeList.listIterator();

  Node current;

  for (int i = 0; i < 2; i++) {
    current = nodesIterator.next();
    System.out.println("current = " + current.time);
  }
  System.out.println("outside of loop:"); 

  System.out.println("move current backward:");
  current = nodesIterator.previous();
  System.out.println("current = " + current.time);

  System.out.println("move current forward:");
  current = nodesIterator.next();
  System.out.println("current = " + current.time);

  System.out.println("Passing nodesIterator into testFunction2():");
  testFunction2(nodesIterator);   
}


void testFunction2(ListIterator<Node> nodesIterator) {

  System.out.println("inside testFunction2():");

  Node current = nodesIterator.next();
  System.out.println("current = " + current.time);

  System.out.println("move current backward:");
  current = nodesIterator.previous();
  System.out.println("current = " + current.time);

  System.out.println("move current backward again:");
  current = nodesIterator.previous();
  System.out.println("current = " + current.time);
}

Outputs:

current = 7
current = 8

outside of loop:

move current backward:
current = 8
 // -> current is suppose to be 7 if previous current inside the loop was 8?

move current forward:
current = 8
 // -> current is suppose to be 9 if previous current = 8?

Passing nodesIterator into testFunction2():

inside testFunction2():
current = 9
 // -> guess it's correct since previous current = 8?

move current backward:
current = 9
 // -> suppose to give me 8 since previous current = 9?

move current backward again:
current = 8
 // -> now it actually moved backward!

What's going on with Java's next() & prev()? My Linked List implemented from scratch would never give me these issues, plus passing nodes to other functions for traversal is way simpler with direct access to (.next) & (.prev) since I can just pass in (node.next) or (node.prev) to other functions without having to pass in the listIterator() reference to link my list of nodes.

Should I stick with my Linked List from scratch and just code out the "Merge Sort"

Upvotes: 0

Views: 157

Answers (1)

Mihir Kekkar
Mihir Kekkar

Reputation: 528

The documentation for ListIterator explains this issue. Basically the "current" location isn't a single node, it's between two nodes. Specifically, it's between the nodes that would be returned if you called prev() or if you called next(). For example, after your first two calls to next() your iterator looks like this:

7 -> 8 *->* 9 -> 10 Current is between 8 and 9.

Calling prev() will return the previous node, which is 8. Then, the iterator will look like this:

7 *->* 8 -> 9 -> 10 Current is between 7 and 8.

Following on, calling next() again will return 8, and so on. This is by design and you'd have to account for it while traversing with the ListIterator.

Upvotes: 3

Related Questions