Collections: Lists (List, LinearList)

Bifurcan provides two primary list implementations that share a common IList interface: the immutable List and the mutable LinearList.

List (Immutable)

The immutable List is an implementation of a Relaxed Radix Balanced Tree (RRB-Tree). This advanced structure gives it powerful performance characteristics:

• Efficient modifications at both ends: addFirst, addLast, removeFirst, and removeLast are highly optimized.
• Fast random access and updates: nth(idx) and set(idx, val) are efficient.
• Near constant-time slicing and concatenation: Operations like slice() and concat() are exceptionally fast, making List ideal for workflows that involve splitting and joining lists.

import io.lacuna.bifurcan.List;

// Create a list
List<String> list1 = List.of("a", "b", "c");

// Add an element
List<String> list2 = list1.addLast("d"); // list1 is unchanged

// Concatenate
List<String> list3 = list2.concat(List.of("e", "f")); // [a, b, c, d, e, f]

// Slice
List<String> slice = list3.slice(1, 4); // [b, c, d]

LinearList (Mutable)

LinearList is a mutable list that combines the benefits of java.util.ArrayList and java.util.ArrayDeque. It is backed by a circular buffer, providing:

• Constant-time additions and removals from both the front and back.
• Constant-time random-access reads and writes.

It is ideal for scenarios where you need to build up a list inside a single thread of execution before potentially converting it to an immutable List using forked().

import io.lacuna.bifurcan.LinearList;

// Create a mutable list
LinearList<Integer> list = new LinearList<>();

// Efficiently build the list
for (int i = 0; i < 100; i++) {
    if (i % 2 == 0) {
        list.addLast(i);
    } else {
        list.addFirst(i);
    }
}