java - 为什么 LinkedList 不暴露它的 Node 类？

Question

如果我从头开始开发链表，我可以在我的业务实体类中存储一个指向 Node 对象的指针，并实现常量 O(1) remove 和 insertAfter操作。在 java 标准库实现中，它们的复杂度为 O(n)，在处理大型数据集时可能相差很大。

他们为什么不公开 Node 类并在其中封装一些细节，仍然使类本身(可能通过接口(interface))可访问？这将使 LinkedList 更加灵活。

我们在 Apache Commons 或 Guava 中有类似 FlexibleLinkedList 的东西吗？

Answer 1

列表迭代器

Why don't they just made the Node class public and encapsulated some details inside it still making the class itself (via interface maybe) accessable?

没有必要。

Why don't they just made the Node class public and encapsulated some details inside it still making the class itself (via interface maybe) accessable? It would make LinkedList more flexible.

那已经存在了。

如果您想获得基于节点的操作的好处，例如:

• 根据当前节点给我下一个项目
• 删除我已有的节点，但不定位
• 在我已有的节点后插入一些东西

您只需使用 list.listIterator() 返回的 ListIterator .所有 List 都提供此方法。

此类封装了在迭代中了解当前节点的逻辑，并提供了直接使用 Node 的有效操作方法，例如:

• add - 该元素紧接在 next()
返回的元素之前插入
• set - 用指定元素替换 next() 或 previous() 返回的最后一个元素
• remove - 从列表中删除 next() 或 previous()
返回的最后一个元素

同时提供使用 next() 和 previous() 控制迭代的方法。

---

例子

例如，您可以每隔一个元素更改一次:

LinkedList<Integer> values = new LinkedList<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

int i = 0;
ListIterator<Integer> iter = values.listIterator();
while (iter.hasNext()) {
    iter.next();

    if (i % 2 == 0) {
        iter.set(100);
    }

    i++;
}

导致

[100, 2, 100, 4, 100, 6, 100, 8, 100, 10]

并且这段代码的运行时间为O(n)，它不需要每次都重新定位节点。与坏的等价物相比

for (int i = 0; i < list.size(); i++) {
    if (i % 2 == 0) {
        list.set(i, 100);
    }
}

由于您所述的原因，它在 O(n^2) 中运行。

---

隐藏Node的好处

一般来说，封装和隐藏你的私有(private)内部运作要好得多。用户不应该关心 LinkedList 在幕后是如何工作的。

此外，如果它会暴露 Node，用户可能会偷偷地编辑它们，整个列表就会变得疯狂。

例如，用户可以然后做

Node a = list.getNodeAtIndex(3);   
Node b = a.next;
Node c = b.next;

// Remove b
a.next = c;
c.previous = a;

没有同时调整列表的大小。所以 list.size() 现在会返回一个错误的数字，可能会导致迭代期间崩溃。

或者你也可以引入一个危险的循环:

a.next = b;
b.next = a;

或者忘记设置previous，导致向后迭代时不同的列表:

a.next = c;
c.previous = b;

---

ListIterator 确保此类事情不会发生，同时提供相同的功能。因此，它不是直接向用户公开节点，而是仅以其完全控制的方法的形式公开所需的功能。