为什么 LinkedList 不公开其 Node 类？

Question

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

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

我们有像Apache Commons 或 Guava 中的FlexibleLinkedList 之类的东西吗？

Answer 1

ListIterator

为什么他们不只是公开 Node 类并在其中封装一些细节仍然使类本身（可能通过接口）可访问？

没有必要。

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

那已经存在了。

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

• 给我下一个项目，基于当前节点
• 删除我已有的节点，不定位
• 在我已经拥有的节点之后插入一些东西

你只需要使用ListIterator由list.listIterator()返回的a。此方法由所有Lists提供。

该类封装了在迭代中知道当前节点的逻辑，并提供了直接使用Nodes进行操作的有效方法，例如：

• add - 元素被插入到将要返回的元素之前 next()
• set-用指定元素替换next()或返回的最后一个previous()元素
• remove- 从列表中删除由next()or返回的最后一个元素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

一般来说，封装和隐藏你的私人内部运作要好得多。用户不应该打扰LinkedList它在幕后如何工作。

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

例如，用户然后可以做

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

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

无需也调整size列表的。所以list.size()现在会返回错误的数字，可能会导致迭代过程中崩溃。

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

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

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

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

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