Java中Stream（java.util.stream）和LinkedList数据结构有什么关系？

Question

我正在学习 Java 中的

Stream

，想弄清楚它实际上是如何工作的。

我看到了 Brian Goetz 的一篇文章。他写了关于流管道的文章：

流管道是通过构建流源及其中间操作的链表表示来构建的

但是，我不明白这一点。

LinkedList

在这里起什么作用？为什么他们使用

LinkedList

而不是

List

的其他实现（例如

ArrayList

）？ 我检查了

Stream

的源代码，但没有看到任何对

LinkedList

的引用。

Answer 1

作者将 linked-list 作为一个概念，而不是

LinkedList

类。实际的链表实现可以在

java.util.stream

包的

AbstractPipeline

类中找到。

这是一个双向链表，其中每个阶段都包含对

previousStage

（如果存在）和

nextStage

（如果存在）的引用：

abstract class AbstractPipeline<E_IN, E_OUT, S extends BaseStream<E_OUT, S>>
        extends PipelineHelper<E_OUT> implements BaseStream<E_OUT, S> {
    /* ... */
    
    /**
     * The "upstream" pipeline, or null if this is the source stage.
     */
    @SuppressWarnings("rawtypes")
    protected final AbstractPipeline previousStage;

    /* ... */
    
    /**
    * The next stage in the pipeline, or null if this is the last stage.
    * Effectively final at the point of linking to the next pipeline.
    */
    @SuppressWarnings("rawtypes")
    private AbstractPipeline nextStage;
    
    /* ...*/
}

这里没有任何内容可以保证

ArrayList

或类似数组的实现的额外开销，因为不需要基于索引的访问。

Answer 2

我不认为他指的是一个实际的

LinkedList

对象，而是流管道的每个阶段仅“知道”其上游邻居，从而使管道成为抽象意义上的链表。

Answer 3

这基本上是说流管道，例如：

someCollection.stream()
    .map(...)
    .filter(...)
    .limit(...);

可以认为是一个链表，其中第一个节点是流的源头，其余节点是你所做的中间和终端操作，比如

source <---> map <---> filter <---> limit

如果深入研究实现，您会发现与 AbstractPipeline.java 中的典型链表实现非常相似。

abstract class AbstractPipeline<E_IN, E_OUT, S extends BaseStream<E_OUT, S>>
        extends ... {

    // ...

    @SuppressWarnings("rawtypes")
    private final AbstractPipeline previousStage;

    @SuppressWarnings("rawtypes")
    private AbstractPipeline nextStage;

    // ...
}

将此与链表的典型实现进行比较：

class Node<T> {
    T element;
    Node<T> next;
    Node<T> previous;
}

请注意，这与

java.util.LinkedList

无关。