List¶
A linked list: a sealed interface with two records, Cons(T head, List<T> tail) and Nil().
Adding at the front, head and tail are O(1) and share the rest of the list. Anything that reaches the end walks
the whole list.
When to choose it¶
When you take a sequence apart from the front, recursively or with pattern matching, or need a stack (push, pop,
peek). For access by index, adding at the end or size, choose Vector.
var list = List.of(1, 2, 3);
var first = switch (list) {
case Cons(var head, var tail) -> "head " + head + ", then " + tail.size() + " more";
case Nil() -> "empty";
};
// "head 1, then 2 more"
var stack = List.<String>empty().push("a").push("b"); // List<String>
var top = stack.peek(); // String
var popped = stack.pop(); // List<String>
// top is "b", popped is List(a)
Costs¶
| Operation | Cost | Note |
|---|---|---|
head |
O(1) | O(1): the first element is stored directly. |
tail |
O(1) | O(1): the rest of the List is stored directly, nothing is copied. |
last |
O(n) | O(n); the whole List is walked. |
init |
O(n) | O(n); every element but the last is copied. |
get |
O(i) | O(i); the elements before i are walked one by one. |
update |
O(i) | O(i); the elements before i are copied, the rest of this List is shared. |
prepend |
O(1) | O(1): one new element is put in front; this List is shared, not copied. |
append |
O(n) | O(n); every element of this List is copied. |
prependAll |
O(m) | O(m) for m prepended elements; this List is shared, not copied. |
appendAll |
O(n + m) | O(n + m) for m appended elements: this List is copied. A List argument is shared, not copied; any other argument is copied into a new List first. |
insert |
O(i) | O(i); the elements before i are copied, the rest of this List is shared. |
removeAt |
O(i) | O(i); the elements before i are copied, the rest of this List is shared. |
take |
O(k) | O(k) for k taken elements; they are copied. A List of at most k elements is returned as is. |
drop |
O(k) | O(k) for k dropped elements; the rest of this List is shared, not copied. |
slice |
O(j) | O(j); the elements before i are skipped, the ones from i to j are copied. |
splitAt(Predicate<? super T>) |
O(k) | O(k) for the k elements before the split; the suffix is shared. |
splitAt(int) |
O(k) | O(k) for the first k elements; they are copied, the rest of this List is shared. |
reverse |
O(n) | O(n). |
sorted |
O(n log n) | O(n log n) comparisons; the elements are copied to an array and sorted there. |
size |
O(n) | O(n): a List does not store its size, so every call counts the elements. isEmpty is O(1). |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
sizeCompare(int) |
O(min(n, k)) | O(min(n, k)) for k = otherSize: at most k + 1 cells are walked, where size() walks them all. |
contains |
O(n) | O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a lookup. |
indexOf |
O(n) | O(n). |
zip |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
sliding(int) |
O(n * size) | O(n * size); each window is copied into its own List. |
sliding(int, int) |
O(n + (n / step) * size) | O(n + (n / step) * size); each window is copied into its own List, and the elements between two windows are still walked. |
grouped |
O(n) | O(n); each group is copied into its own List. |
distinct |
O(n) | O(n): one hash lookup per element. |
Every method: complexity page.
Sharp edges¶
size()is O(n): the list does not store its size.equals,toArray()andstream()count the elements first too. To compare the size with a number,sizeCompare(n)walks at mostn + 1elements.append,appendAll,last,init,takeRightanddropRightwalk the whole list, and all butlastcopy it.get(i)walks the list up to position i;update,insertandremoveAtalso copy the elements before it.take,drop,sliceandsplitAtwalk only the elements they take or skip, never the rest of the list.- A loop by index over
asJava()is O(n^2), because eachget(i)walks the list: use its iterator. containsAllis O(n * m): each element of the argument is looked for by a walk.pushisprependunder its stack name.