std.collections

Module linkedlist

Source
Description

LinkedList — doubly-linked list with O(1) push/pop at both ends.

LinkedList elem is a newtype over (Vec elem) — runtime layout matches Vec, but dispatch treats it as a nominally distinct type.

Methods currently panic at runtime; real bodies require a doubly-linked node allocation surface for O(1) splice and O(n) walks. Cursor / CursorMut are deferred; Seq-hierarchy impls (Foldable, Mappable, Filterable, Chainable, Indexed, Zippable) arrive alongside that wiring.

Not re-exported by the prelude — use :use :open silo:std.collections.linkedlist ....

Data Types

Types

LinkedList

Doubly-linked list.

Functions

Functions

linkedlist-from-vec

Convert a (Vec elem) to a (LinkedList elem), preserving order.

linkedlist-zip

.zip — free-fn form.

Trait Implementations

impl LinkedList for ?580302

.append ( (LinkedList elem) (LinkedList elem) → (LinkedList elem) )

Move all elements of the second list onto the back of the first. Spec-guaranteed O(1); on the Vec-layout stub this copies both Vecs.

.back ( (LinkedList elem) → (Option elem) )

.back returns Some with the last element or None if empty. O(1). Real body: reads the last element of the backing Vec cell.

.front ( (LinkedList elem) → (Option elem) )

.front returns Some with the first element or None if empty. O(1). Real body: reads the first element of the backing Vec cell (LinkedList is a newtype over (Vec elem)), wraps it in Some, or returns None on an empty list. Real doubly-linked-node semantics arrive with a follow-up WP; this body is correct for the Vec-layout stub.

.get ( (Int ..) (LinkedList elem) → (Option elem) )

Return Some with the element at the given 0-based index, or None if out of bounds. O(n) — walks from nearer end.

.is-empty ( (LinkedList elem) → Bool )

True iff the list contains zero elements.

.len ( (LinkedList elem) → (Int ..) )

Number of elements in O(1). Implementations MUST cache length.

.pop-back ( (LinkedList elem) → (LinkedList elem) (Option elem) )

Remove and return the back element. O(1).

.pop-front ( (LinkedList elem) → (LinkedList elem) (Option elem) )

Remove and return the front element. O(1).

.prepend ( (LinkedList elem) (LinkedList elem) → (LinkedList elem) )

Move all elements of the second list onto the front of the first. Spec-guaranteed O(1); on the Vec-layout stub this copies both Vecs.

.push-back ( elem (LinkedList elem) → (LinkedList elem) )

Append an element to the back. O(1).

.push-front ( elem (LinkedList elem) → (LinkedList elem) )

Prepend an element to the front. Spec-guaranteed O(1); on the Vec-layout stub this rebuilds the backing Vec so it is O(n) until the doubly-linked-node runtime lands.

.reverse ( (LinkedList elem) → (LinkedList elem) )

Return a new list with elements in reverse order. O(n).

.split-at ( (Int ..) (LinkedList elem) → (LinkedList elem) (LinkedList elem) )

Split the list at the given 0-based index, returning prefix + suffix. Complexity O(min(n, len - n)); negative n is a runtime error.

.to-vec ( (LinkedList elem) → (Vec elem) )

Convert a (LinkedList elem) to a (Vec elem) in front-to-back order. Runtime identity cast — the backing cell is already a Vec.