Understanding Streams in Java: The Role of LinkedList in Stream Pipelines

QUESTION:

I’m learning about Stream in Java and want to figure out how it actually works. I read an article by Brian Goetz where he mentioned that a stream pipeline is built by constructing a linked-list representation of the stream source and its intermediate operations. However, 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.

ANSWER:

Introduction to Java Streams

Java Streams, introduced in Java 8, provide a powerful and expressive way to work with sequences of elements. Streams allow for functional-style operations on collections of objects, enabling developers to write clean, concise, and efficient code. Understanding how streams work internally can provide deeper insights into their performance characteristics and help you make better design decisions.

What is a Stream Pipeline?

A stream pipeline in Java consists of three components:

1. Source: The data source from which the stream is derived, such as a collection, array, or I/O channel.
2. Intermediate Operations: Operations that transform the stream into another stream, such as filter, map, or sorted. These operations are lazy and are not executed until a terminal operation is invoked.
3. Terminal Operation: An operation that produces a result or a side effect, such as forEach, reduce, or collect. The invocation of a terminal operation triggers the execution of the entire stream pipeline.

Understanding the Linked-List Representation

In his article, Brian Goetz mentions that a stream pipeline is built by constructing a linked-list representation of the stream source and its intermediate operations. This description can be a bit abstract, so let’s break it down.

Role of Linked-List in Stream Pipelines

When we talk about a “linked-list representation,” we’re referring to the conceptual structure used to build and execute the stream pipeline. This does not mean that Java’s LinkedList class is used internally by the Stream API. Instead, the idea is that each intermediate operation in the pipeline is linked to the next operation, forming a chain of operations.

Key Points:

• Intermediate Operations: Each intermediate operation in the stream pipeline is represented by an internal object that holds a reference to the next operation in the chain. This creates a linked structure, where each operation points to the next.
• Lazy Evaluation: Intermediate operations are lazy, meaning they do not perform any computations until a terminal operation is invoked. This linked structure allows the Stream API to efficiently manage and defer computations until they are actually needed.
• Pipeline Execution: When a terminal operation is invoked, the entire linked structure of intermediate operations is traversed, and the operations are applied to the elements of the stream in a single pass.

Why Not ArrayList?

You might wonder why a LinkedList-like structure is preferred conceptually over an ArrayList. Here are a few reasons:

1. Efficiency in Chaining: LinkedList allows efficient insertion and deletion of elements, which is beneficial when constructing a pipeline of operations. Each intermediate operation can be added to the chain without the need to resize or copy an underlying array.
2. Lazy Evaluation: The linked structure supports the lazy evaluation model of streams, where operations are only executed when necessary. This avoids the overhead of creating intermediate data structures.
3. Traversal and Execution: When the terminal operation triggers the pipeline, the traversal of the linked structure is straightforward and efficient. Each operation is applied in sequence to the elements of the stream.

Examining the Source Code

While the conceptual linked-list representation helps understand the structure, it is also useful to look at the actual implementation in the source code. The Stream API uses various internal classes to manage the pipeline of operations.

Key Classes

1. AbstractPipeline: This is the base class for all stream pipelines. It holds references to the source stage, previous stage, and next stage in the pipeline.
2. ReferencePipeline: This class extends AbstractPipeline and provides concrete implementations for reference streams (i.e., streams of objects).
3. StatelessOp and StatefulOp: These classes represent intermediate operations that are stateless (e.g., filter) and stateful (e.g., sorted), respectively.

Example: AbstractPipeline

abstract class AbstractPipeline<E_IN, E_OUT, S extends BaseStream<E_OUT, S>>
        extends PipelineHelper<E_OUT>
        implements BaseStream<E_OUT, S> {
    final AbstractPipeline<?, E_IN, ?> previousStage;
    final AbstractPipeline<?, ?, ?> nextStage;
    ...
    @Override
    public final S sequential() {
        sourceStage.parallel = false;
        return (S) this;
    }
    ...
}

Example: ReferencePipeline

class ReferencePipeline<P_IN, P_OUT>
        extends AbstractPipeline<P_IN, P_OUT, Stream<P_OUT>>
        implements Stream<P_OUT> {
    ...
    public final Stream<P_OUT> filter(Predicate<? super P_OUT> predicate) {
        Objects.requireNonNull(predicate);
        return new StatelessOp<P_OUT, P_OUT>(this, StreamShape.REFERENCE,
                                             StreamOpFlag.NOT_SIZED) {
            @Override
            Sink<P_OUT> opWrapSink(int flags, Sink<P_OUT> sink) {
                return new Sink.ChainedReference<P_OUT, P_OUT>(sink) {
                    @Override
                    public void begin(long size) {
                        downstream.begin(-1);
                    }
                    @Override
                    public void accept(P_OUT u) {
                        if (predicate.test(u))
                            downstream.accept(u);
                    }
                };
            }
        };
    }
    ...
}

Practical Example: Stream Pipeline in Action

To better understand how streams work, let’s look at a practical example. We’ll create a stream pipeline that filters, maps, and collects data.

Code Example

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class StreamExample {
    public static void main(String[] args) {
        List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David");

        List<String> result = names.stream()
            .filter(name -> name.startsWith("A") || name.startsWith("C"))
            .map(String::toUpperCase)
            .collect(Collectors.toList());

        System.out.println(result); // Output: [ALICE, CHARLIE]
    }
}

In this example:

• Source: The names list is the stream source.
• Intermediate Operations: filter and map are the intermediate operations, forming a chain.
• Terminal Operation: collect is the terminal operation, triggering the execution of the pipeline.

Conclusion

Understanding the internal workings of Java Streams, particularly the linked-list representation of the pipeline, provides valuable insights into their efficiency and design. Although the Stream API does not use Java’s LinkedList class, the conceptual model of linking intermediate operations helps explain how streams manage lazy evaluation and efficient execution.

By grasping these concepts, you can leverage the power of Java Streams to write more efficient and expressive code, enhancing your software development practices.

Useful Links

• Java Streams Documentation
• Brian Goetz’s Article on Java Streams
• Java LinkedList Documentation