Module collections/linked_list
Doubly-linked list with O(1) push/pop at both ends.
Every node is a separate reference-counted allocation holding next and
prev handles, so indexing is an O(n) walk and each element costs a
pointer pair on top of its value: reach for ArrayList unless the point
is cheap splicing at the ends, and for Deque when both ends are what you
want. Positional insert/remove report a bad index as a Result rather
than panicking (D1) — deliberately unlike ArrayList, where the same
mistake panics, because a list that has to walk to the index is already
answering a question that can fail.
Stability
stable — names mirror Rust's LinkedList
(push_front/push_back/pop_front/pop_back/front/back), the
Result shape of insert/remove is the settled D1 decision, and
plans/STD_API_STABILIZATION.md §4 lists nothing open against this
module. tests/collections/linked_list.test.yo covers the surface.
Missing trait impls (Debug, Ord, Hash) would be additive.
Types
Doubly-linked list with O(1) push/pop at both ends.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), LinkedList(T), ...)
new : (fn() -> Self)Empty list. Allocates nothing — each push_* allocates its own node.
Returns: Self
len : (fn(self : Self) -> usize)Number of elements. O(1) — the count is maintained, not walked.
Returns: usize
is_empty : (fn(self : Self) -> bool)True when the list holds no elements.
Returns: bool
push_front : (fn(self : Self, value : T) -> unit)Add an element at the front — O(1), one node allocation. Rust's
push_front. Existing element positions shift by one; no pointer or
iterator into another node is disturbed.
Returns: unit
push_back : (fn(self : Self, value : T) -> unit)Add an element at the back — O(1), one node allocation. Rust's
push_back. This is the cheap append; ArrayList.push is cheaper
still if you do not need stable node identity.
Returns: unit
pop_front : (fn(self : Self) -> Option(T))Remove and return the first element, or .None when empty — O(1).
Clears the new head's prev handle, which is what breaks the
reference cycle every adjacent node pair forms (see dispose).
Returns: Option(T)
pop_back : (fn(self : Self) -> Option(T))Remove and return the last element, or .None when empty — O(1),
because the list keeps a tail handle.
Returns: Option(T)
front : (fn(self : Self) -> Option(T))Copy of the first element without removing it, or .None — Rust's
front. The value is dup'd for a refcounted T; iter() yields
pointers if that matters.
Returns: Option(T)
back : (fn(self : Self) -> Option(T))Copy of the last element without removing it, or .None — Rust's
back.
Returns: Option(T)
get : (fn(self : Self, index : usize) -> Option(T))Copy of the element at index, or .None when out of range.
O(n): it walks from the head — there is no random access. Rust has no
LinkedList::get at all, for exactly this reason; a full traversal
belongs in iter(), and a get in a loop is quadratic.
Returns: Option(T)
insert : (fn(self : Self, index : usize, value : T) -> Result(unit, LinkedListError))Insert value so that it ends up at index, shifting the rest along
— O(n) to walk there, O(1) to splice. index == len() appends.
.Err(.IndexOutOfBounds) when index > len(). This is the D1 line:
an out-of-range index is a CALLER MISTAKE and stays a Result here,
while an allocation failure panics; ArrayList.insert panics on the
same mistake, and that difference is deliberate.
Returns: Result(unit, LinkedListError)
remove : (fn(self : Self, index : usize) -> Result(T, LinkedListError))Remove the element at index and return it — O(n) to walk there.
.Err(.IndexOutOfBounds) when index >= len(), where
ArrayList.remove panics — the same deliberate D1 difference as
insert. The first and last indices are routed through
pop_front/pop_back.
Returns: Result(T, LinkedListError)
clear : (fn(self : Self) -> unit)Drop every element — O(n).
Pops from the front rather than releasing the head handle, because each
adjacent node pair is a reference CYCLE (a.next == b, b.prev == a):
dropping the head alone would leave the whole chain with a nonzero
refcount. pop_front clears each new head's prev, which unlinks the
chain as it goes.
Returns: unit
contains : (
fn(
self : Self,
value : T,
where(T <: Eq(T))
) -> bool
)Whether any element equals value — a walk from the head, O(n),
stopping at the first match.
Returns: bool
reverse : (fn(self : Self) -> unit)Reverse the list in place — O(n).
Swaps each node's next and prev handles and then exchanges head and
tail, so no element is moved or copied and node identity is preserved.
Returns: unit
impl(generic(T : Type), LinkedList(T), Dispose(...))
dispose : (fn(self : Self) -> unit)Unlinks and drops every node when the last reference to the list goes
away. Delegates to clear because the prev handles make the chain
cyclic — see clear.
Returns: unit
impl(generic(T : Type), LinkedList(T), IntoIterator(...))
Item : TIntoIter : LinkedListIter(T)into_iter : (fn(self : Self) -> LinkedListIter(T))Returns: LinkedListIter(T)
impl(generic(T : Type), LinkedList(T), ...)
iter : (fn(self : Self) -> LinkedListIterPtr(T))Borrowing walk from the head: yields a *(T) into each node, leaving
the list intact — for(list.iter(), p => ...), where into_iter
moves the list and yields values (D14).
Returns: LinkedListIterPtr(T)
impl(generic(T : Type), LinkedList(T), Index(usize)(...))
Output : Tindex : (fn(inout(self) : Self, idx : usize) -> *Self.Output)impl(generic(T : Type), LinkedList(T), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
What a positional insert / remove can fail with.
Variants
| Variant | Fields | Description |
|---|---|---|
IndexOutOfBounds | index: usize, length: usize | Index is out of bounds for the current length. |
EmptyList | Attempted to access an element from an empty list. |
Value iterator over a LinkedList — follows next from the head and
yields each element BY VALUE (dup'd for a refcounted T). This is what
into_iter(), and therefore for(list, ...), returns.
It holds only the current NODE, so the walk survives elements being removed behind it, but removing the node it is parked on cuts the walk short.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), LinkedListIter(T), Iterator(...))
Item : Tnext : (fn(inout(self) : Self) -> Option(T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(T)
Pointer iterator over a LinkedList — yields &(node.value) for each
node, so nothing is dup'd and writing through the pointer updates the
element in place. This is what iter() returns (D14).
A yielded pointer is valid only while its node is alive: removing that element during the walk leaves it dangling.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), LinkedListIterPtr(T), Iterator(...))
Item : *Tnext : (fn(inout(self) : Self) -> Option(*T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(*T)