英文:
Java listIterator() is giving me weird outputs with .next() and .prev()
问题
我一直在一个项目上工作,我在其中从头开始实现了一个带有单独的“Node类”的“双向链表”。
然后,我已经到了需要对我的“Node链表”进行排序的阶段。由于我是从头开始实现的链表,所以为了对其进行排序,我还必须从头开始实现一个“归并排序”,这需要一些时间来完成。
因此,我考虑使用java.util中的“Java链表”,然后使用listIterator(),然后使用Collections.sort()来对我的LinkedList进行排序,但是其next()和previous()与我以前使用(.next)和(.prev)直接访问LinkedList的节点时给我一些意外的奇怪输出。例如,假设:
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);
}
输出结果:
current = 7
current = 8
outside of loop:
move current backward:
current = 8
// -> 如果循环内之前的current是8,那么current应该是7吗?
move current forward:
current = 8
// -> 如果之前的current是8,那么current应该是9吗?
Passing nodesIterator into testFunction2():
inside testFunction2():
current = 9
// -> 如果之前的current是8,那么应该是正确的吗?
move current backward:
current = 9
// -> 如果之前的current是9,那么应该是8吗?
move current backward again:
current = 8
// -> 现在实际上向后移动了!
Java的next()和prev()出了什么问题?我从头开始实现的链表永远不会给我这些问题,而且通过直接访问(.next)和(.prev)进行遍历后,将节点传递给其他函数也更加简单,因为我可以只需将(node.next)或(node.prev)传递给其他函数,而无需传递listIterator()引用以链接我的节点链表。
我应该坚持使用我从头开始实现的链表,然后编写“归并排序”的代码吗?
英文:
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"
答案1
得分: 3
ListIterator
的文档解释了这个问题。基本上,“当前”位置不是单个节点,而是位于两个节点之间。具体来说,它位于如果你调用了prev()
或者调用了next()
时将返回的节点之间。例如,在第一次连续两次调用了next()
之后,迭代器的状态如下:
7 -> 8 *->* 9 -> 10
当前位于 8
和 9
之间。
调用prev()
会返回前一个节点,也就是 8
。然后,迭代器的状态变为:
7 *->* 8 -> 9 -> 10
当前位于 7
和 8
之间。
接着,再次调用next()
将会再次返回 8
,以此类推。这是设计如此,你在使用ListIterator
进行遍历时需要考虑到这一点。
英文:
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
.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论