从列表末尾开始迭代

Question

我知道我们可以按照以下方式迭代列表的反向顺序：

List<Object> lst;
ListIterator<Object> i = lst.listIterator(lst.size());

但是如果lst是一个LinkedList，那么它是否高效呢？我的意思是当我们获得指向列表末尾的ListIterator时，实现是否会从列表开头迭代到list.size()位置（需要O(n)时间，其中n是列表的大小）？

如果是这样，有没有办法避免这种情况发生？

- St.Antario

---

是的，它会从列表的开头到 list.size() 进行迭代。 - Ashwani

@AshwaniDausodia 那么，在C++中，我们有reverse_iterator。在Java中如何高效地实现它？ - St.Antario

列表逆序遍历 Java 中的方法是什么？ - SatyaTNV

@Satya 他们提出的解决方案正如我在问题中所提到的。 - St.Antario

@St.Antario 你可以实现自己的双向链表。 - Ashwani

Answer 1

LinkedList也实现了Deque接口。

因此，如果你将其实现为

Deque list = new LinkedList();

或者，如果您需要额外的列表方法。

LinkedList list = new LinkedList();

您可以使用

list.descendingIterator();

- Denis Lukenich

Answer 2

文档说明LinkedList是List和Deque接口的双向链表实现。因此，列表中的每个元素都有对下一个和上一个元素的引用。因此，迭代器在反向顺序中应与自然顺序一样快。

- Eric Leibenguth

Answer 3

文档说明LinkedList是一个双向链表，因此我希望返回指向列表尾部的迭代器的descendingIterator（），应该是O（1）。请注意，descendingIterator来自Deque接口。现在很难说语句lst.listIterator（lst.size（））是否也是O（1），因为没有记录listIterator方法是否优化了从lst.size（）的下一个元素是尾部的这一事实。

- UmNyobe

---

所以，我们只需要利用它是一个双端队列的事实，谢谢。 - St.Antario

Answer 4

它不会遍历列表来生成迭代器。

寻找这些问题的最佳解决方案是源代码。

  if (index < (size >> 1)) {
          next = header.next;
          for (nextIndex=0; nextIndex<index; nextIndex++)
              next = next.next;
      } else {
          next = header;
          for (nextIndex=size; nextIndex>index; nextIndex--)
              next = next.previous;
      }

正如您所看到的，它将尝试使用从第一个节点或最后一个节点开始的最短路径来达到索引。

- Codebender

Answer 5

你的代码无法工作，索引lst.size()超出了范围，也许你想用lst.size()-1。但是它仍然不是一个反向迭代器，而是一个前向迭代器，从指定的元素开始而不是从0开始。在这种情况下，您将只读取最后一个元素，然后到达结尾。 LinkedList实现了接口Deque，该接口提供Deque.descendingIterator。在这种情况下，实例化迭代器和移动到下一个（上一个）元素都是O(1)操作。在第一种情况下，这是因为Deque实现保留了队列的开头和结尾的引用，在第二种情况下，这是因为LinkedList是一个双向链表，其中每个元素都保留了对其后继和前驱的引用。

- Shepard

---

现在我明白了，你这样实例化是为了通过previous()进行迭代。在这种情况下，是的，它可以工作。但为了确保复杂性，我会选择使用Deque.reverseIterator()，即使最终它们应该执行相同的操作。 - Shepard

IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()) - UmNyobe