java - 循环链表和迭代器 API 缺乏确定性

Question

我正在尝试使用 List 接口(interface)创建一个循环链表实现，并注意到一个有趣的副作用。

虽然CircularLinkedList满足List契约，但它打破了其他当前实现的collection类!

问题是这样的 - ListIterator 接口(interface)给出以下内容hasNext() 和 hasPrevious() 方法的约定:

public boolean hasNext()

Returns true if this list iterator has more elements when traversing the list in the forward direction. (In other words, returns true if next would return an element rather than throwing an exception.)

public boolean hasPrevious()

Returns true if this list iterator has more elements when traversing the list in the reverse direction. (In other words, returns true if previous would return an element rather than throwing an exception.)

现在，在循环列表中，当且仅当列表为空时，每个列表都应按照约定返回false。

当您尝试使用 addAll() 方法将具有适当列表迭代器的循环列表添加到另一个 Collection 时，问题就会出现 - 该方法使用 hasNext()在添加每个元素时限制迭代。因此循环永远不会终止!

我目前正在考虑打破 ListIterator 的契约，使列表看起来像一个链接列表(如果您正在查看 hasNext() 方法)，或者创建一个迭代器的子类，并重写 hasNext 来返回iterator() 方法。

两个问题:

1. 有没有更好的方法可以在不破坏迭代器的情况下做到这一点或者 ListIterator 合约？

2. 有没有其他人认为这是 AbstractCollection 类(这是继承行为的来源)中的缺陷。请注意，某些集合确实以更稳健的方式执行添加，通过调用要添加的集合的 toArray() 方法，并添加数组的每个元素。

Answer 1

在我看来，这既不是 Collections API 的缺陷，也不是 hasNext 和 hasPrevious 方法的契约定义方式的缺陷.

问题源于您对循环列表的思考方式:

• 列表的元素大小是固定的，因此迭代器应该能够以有开始和结束的方式对它们进行排序。
• 如何组织列表中的元素来回答 hasNext 和 hasPrevious 并不重要。排序仅定义何时返回哪个元素。

如果您的迭代器返回相同的元素(以列表中的绝对位置表示的同一性)，那么您的迭代器实现是错误的。

您必须将如何对元素排序的想法与列表包含的元素数量分开。列表中元素的数量由size的结果定义。因此，如果仅向前导航，hasNext 应该以 true 准确回答 size 次。当从 hasNext 得到 false 作为答案后向后导航时，hasPrevious 也是如此。