Production-grade Cons List implementation

ConsList is an immutable singly-linked list: ConsList.java.

This reliable and performant version of singly-linked Cons List in Java implements the java.util.Collection interface, giving the programmers the access to all its methods such as stream(), toString() and others.

This implementation of Cons List does not use recursion, so it will not cause a StackOverflowError. A list is allowed to contain more than Integer.MAX_VALUE elements and will produce an overhead of two object references per element.

For further performance increase, primitive-type specializations can be used: IntConsList, LongConsList, and DoubleConsList, all of which extend the parent ConsList interface, while adding their own primitive-based methods on top.

Collection methods are implemented:

• size() iterates through the list to avoid storing list length
• isEmpty() does not try to calculate the size to see if it is 0.

Java 8 Streams support:

• spliterator() has the right characteristics for the cons list: ORDERED and IMMUTABLE.
• a custom Collector toConsCollector() is provided.

Methods equals(Object o) and hashCode() are also implemented without recursion.

Finally, the class is Serializable. The serialization and de-serialization operations are implemented using loops instead of recursion, thereby safeguarding against a StackOverflowError.

---

Cons List, due to its simplicity and immutability, is an ideal data structure for multi-threaded processing of ordered collections of data. Direct implementations however, suffer from heavy recsive calls and may cause high stack memory consumption, if not more severe issues. This implementation fuses the power of the immutable cons list with the wide range of functionality offered by the Java Collections and Streams API.

Maven

<dependency>
    <groupId>io.github.nblxa</groupId>
    <artifactId>cons-list</artifactId>
    <version>2.1.0</version>
</dependency>

The library uses Semantic Versioning.

Usage

Static imports for ease of use:

import static io.github.nblxa.cons.ConsList.*;

Create an empty Cons list:

Collection<?> empty = nil();

Create a list of an arbitrary length:

Collection<String> strings = list("Hello", "functional", "programming", "!");

Adding new elements to a list is just creating new immutable lists:

Collection<String> strings2 = cons("ConsList", cons("says:", strings));

Note that since Cons List is immutable, it must be initialized with elements at the time of creation. Another option is to initialize it with elements of another Iterable:

Collection<String> colors = consList(Arrays.asList("red", "black", "magenta"));

Create a primitive-based list of long values:

LongConsList<Long> longs = longList(1L, 1L, 2L, 3L, 5L, 8L, 13L);

Create a list from a Stream:

ConsList<String> fruit = Arrays.stream(new String[] {"Apples", "Bananas", "Oranges"})
    .filter(f -> !f.startsWith("O"))
    .collect(toConsCollector());

Performance

Being an immutable collection, ConsList lets one save resources on defensive copying where it would otherwise have been necessary for mutable collections, such as ArrayList.

See ConsListBenchmark.java.

Specific problems like flattening a tree-like hierarchical structure can be solved more optimally with ConsList, however the trivial list-growth and iteration operations perform better using java.util.ArrayList.

Specialized implementations for primitive types, like the IntConsList, for instance, may outperform ArrayList in some benchmarks due to the lack of boxing.

Here are the benchmark results on the author's machine:

Benchmark: Flatten a hierarchy

Collection	Avg time, ms/op
io.github.nblxa.cons.ConsList	29,659
java.util.ArrayList	78,018
java.util.LinkedList	112,173

Benchmark: Grow a list of integers

Collection	Avg time, ms/op
io.github.nblxa.cons.IntConsList	6,767
io.github.nblxa.cons.ConsList	22,137
java.util.ArrayList	9,507
java.util.LinkedList	14,763

Note: The values for ConsList and IntConsList assume creating the list with the reversed order of input values compared to those for ArrayList and LinkedList. If the reversed order is not possible, a somewhat slower reverse() or intReverse() operation is required, adding one single list iteration and re-construction.

Benchmark: Iterate over a list of integers

Collection	Avg time, ms/op
io.github.nblxa.cons.IntConsList	3,058
io.github.nblxa.cons.ConsList	4,845
java.util.ArrayList	1,989
java.util.LinkedList	10,451

Running the benchmarks

The benchmark is written with JMH. To test the performance on your machine, build the project:

./mvnw clean package

and the benchmarks run:

java -jar cons-list-jmh/target/benchmarks.jar