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 a switch, or need a stack (push, pop,
peek). For access by index, adding at the end or length, choose Vector.
List<Integer> list = List.of(1, 2, 3);
String first = switch (list) {
case Cons(var head, var tail) -> "head " + head + ", then " + tail.length() + " more";
case Nil() -> "empty";
};
// "head 1, then 2 more"
List<String> stack = List.<String>empty().push("a").push("b");
String top = stack.peek();
List<String> popped = stack.pop();
// top is "b", popped is List(a)
Costs¶
| Operation | Cost | Note |
|---|---|---|
head |
O(1) | O(1). |
tail |
O(1) | O(1); the tail is a field of the cons cell. |
last |
O(n) | O(n). |
init |
O(n) | O(n); the kept prefix is copied. |
get |
O(index) | O(index); the cells are walked one by one. |
update |
O(index) | O(index); the cells before it are copied, the rest is shared. |
prepend |
O(1) | O(1); this List becomes the tail of one new cell. |
append |
O(n) | O(n); every cell of this List is rebuilt. |
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; the elements are copied once and this List is rebuilt. |
insert |
O(index) | O(index); the cells before the insertion point are copied, the rest is shared. |
removeAt |
O(index) | O(index); the cells before the removed one are copied, the rest is shared. |
take |
O(n) | O(n) for n taken elements; the prefix is copied. |
drop |
O(n) | O(n) for n dropped elements; the rest of this List is shared, not copied. |
slice |
O(endIndex) | O(endIndex). |
splitAt(Predicate<? super T>) |
O(k) | O(k) for the k elements before the split; the suffix is shared. |
splitAt(int) |
O(n) | O(n); the prefix is copied, the suffix is shared. |
reverse |
O(n) | O(n). |
sorted |
O(n log n) | O(n log n) comparisons. |
length |
O(n) | O(n); a cons list has no length field, so the cells are counted. |
contains |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own 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 * size / step) | O(n * size / step); each window is copied into its own List. |
grouped |
O(n) | O(n); each block is copied into its own List. |
distinct |
O(n) | O(n). |
Every method: complexity page.
Sharp edges¶
length()is O(n): the list does not store its length.append,appendAll,get(i),update,lastandinitwalk or copy the list up to the position.pushisprependunder its stack name.