Years ago, as a junior Java developer, I expected concatenating two linked lists to be a constant-time operation. A linked list already has a tail, the other list has a head, so why not connect the two structures directly?
The data-structure intuition was reasonable. The assumption about the List contract was not.
The apparent mismatch
For two compatible doubly linked lists, the pointer work required to join them is small and fixed:
- Connect the target tail to the source head.
- Connect the source head back to the target tail.
- Move the target tail reference to the source tail.
- Update the sizes.
None of those steps depends on the number of elements in the source list. Structurally, this is O(1).
Yet Java's normal addAll(Collection) operation processes the source sequence element by element.
For n inserted elements, the work is O(n).
The missing distinction: copying versus transfer
The important difference is semantic, not merely algorithmic.
addAll is a copying-style collection operation. After the call, the source collection must still contain
its elements. It also accepts any compatible Collection, not only another list with an internal node
representation that can be attached directly.
A linked node cannot safely belong to two independently mutable lists at the same time. If both lists retained the same nodes, changing one list could corrupt the other list's structure, size, iteration, or ownership assumptions.
Therefore, true O(1) concatenation requires a different contract: transfer the source list's internal structure to the target and leave the source empty.
Make the destructive operation explicit
This is what splice-list models. It remains compatible with the Java List abstraction for
ordinary operations, while exposing separate methods for structural whole-list transfer:
SpliceList<String> target = SpliceList.of("a");
SpliceList<String> source = SpliceList.of("b", "c");
target.spliceTail(source);
// target: ["a", "b", "c"]
// source: []
The method name communicates that this is not ordinary addAll. The source is consumed because its nodes
have moved into the target list.
The library also provides spliceHead for prepending a whole list. Both operations are O(1), independent
of the number of transferred elements.
Normal List behavior remains normal
When callers need non-destructive behavior, they still use addAll:
SpliceList<String> target = SpliceList.of("a");
SpliceList<String> source = SpliceList.of("b", "c");
target.addAll(source);
// target: ["a", "b", "c"]
// source: ["b", "c"]This operation is O(n), because preserving the source requires inserting the elements into separate target nodes.
Where splicing is useful
Explicit splicing is useful when a program builds intermediate sequences that no longer need independent ownership. Examples include combining staged results, joining partitions, merging list-producing workflows, and reducing several temporary lists into one final list.
It is not a universal replacement for ArrayList. Indexed access retains linked-list complexity, instances
are mutable and not thread-safe, and splicing is intentionally destructive. The optimization is valuable only when
the ownership model and access pattern match it.
The broader API-design lesson
Sometimes an operation is theoretically cheap at the data-structure level but cannot be added transparently to an existing abstraction because its semantics differ.
In this case, O(1) concatenation is not a faster implementation of addAll. It is a different operation
with a different responsibility boundary: copying preserves the source; splicing transfers ownership.
Project: splice-list on GitHub · Maven Central