I’m learning about Stream in Java and want to figure out how it actually works.
And I saw an article by Brian Goetz. He wrote about the stream pipeline:
A stream pipeline is built by constructing a linked-list representation of the stream source and its intermediate operations
But, I don’t understand this. What is the role of LinkedList in here? Why do they use LinkedList instead of other implementations of List like ArrayList?
I have checked the source code of Stream but didn’t see any reference to LinkedList.
1
The author refers to linked-list as a concept, not to the LinkedList class. The actual linked list implementation can be found in the java.util.stream package’s AbstractPipeline class.
It’s a doubly linked list where each stage contains a reference to the previousStage (if present) and nextStage (if present):
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;
/* ...*/
}
Nothing here warrants the additional overhead of an ArrayList or array-like implementation as no index-based access is required.
0
I don’t think he means an actual LinkedList object, but that each stage of the stream pipeline “knows” only its upstream neighbour, thus making the pipeline a linked list in the abstract sense.
This is basically saying that a stream pipeline such as:
someCollection.stream()
.map(...)
.filter(...)
.limit(...);
Can be thought of as a linked list, where the first node is the source of the stream, and the rest of the node are the intermediate and terminal operations you do, such as
source <---> map <---> filter <---> limit
If you dig into the implementation, you will find something that looks very similar to a typical linked list implementation in 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;
// ...
}
Compare this with a typical implementation of a linked list:
class Node<T> {
T element;
Node<T> next;
Node<T> previous;
}
Note that this is unrelated to java.util.LinkedList.