envzn
0.8 · beta · not released

Library / Collections / Lists / LinkedList

CLASSIMPLEMENTS Cloneable, Collection<T>

LinkedList

Defines the LinkedList[T] class per ENVZN_CONSTITUTION §LinkedList.

Fields 1

int32 length

Constructors 1

INIT()

Constructs both sentinels and wires them. After this returns, head → ender (head.next owns the ender), and the list is empty.

Methods 16

METHOD clone() RETURNS LinkedList[T]
reads

Hand-written clone() — Builds a fresh empty list, walks the current chain directly (no heap iterator), and appends a deep-clone of each user value. The new list owns its own sentinel chain with correctly-wired last_node_ref (set by append() on every push).

METHOD iterator() RETURNS LinkedListIterator[T]
reads

Per spec L767, LinkedList exposes BidirectionalIterator OF T. Concrete class is LinkedListIterator (separate file). Pass .head by-& so the iterator's REFERENCE binding satisfies §REFERENCE condition 2 (mutation-locked at INIT) without moving ownership of .head out of SELF.

METHOD isEmpty() RETURNS boolean
reads
METHOD size() RETURNS int64
reads

Number of elements currently stored. Read-only, O(1).

MODIFY METHOD prepend(T value) RETURNS STATUS
modifies

FRONT-SIDE OPERATIONS (right after head sentinel) Insert value at the front. value is cloned in via LinkedListNode's INIT.

Splice ordering : step 1: newNode.next := .head.next (move old first into newNode.next; .head.next is now EMPTY) step 2: .head.next := newNode (move newNode into .head.next; local poisoned) step 3: bump last_node_ref if list was empty

MODIFY METHOD prependCopy(REFERENCE T value) RETURNS STATUS
modifies

Deep-copy form of prepend. value stays valid for the caller; the clone is the one moved into the new node.

MODIFY METHOD popFirst() RETURNS | T
modifies

Remove and return the front user value. EMPTY if empty.

Splice ordering : step 1: popped := .head.next (move; .head.next now EMPTY) step 2: .head.next := popped.next (move the new-first into .head.next) step 3: if popped was the only user node, last_node_ref bumps back to .head

METHOD peekFirst() RETURNS | REFERENCE T
reads

Read (without removing) the front user value. Pipe-XOR shape: SUCCESS populates value with the reference; empty / invariant violation populates s with FAILURE. Never PANICs.

METHOD at(int32 index) RETURNS | REFERENCE T
reads

Non-owning reference to the value at index (0-based), or FAILURE if out of bounds. O(index) forward walk from the first user node — backs index-based external walkers that cannot hold a LinkedListIterator field (iterator Rule A), e.g. ChainedHashDictionaryIterator. Read-only; the source list stays mutation-locked while the returned reference is held.

MODIFY METHOD append(T value) RETURNS STATUS
modifies

BACK-SIDE OPERATIONS (right before ender sentinel) Insert value at the back. value is cloned in via LinkedListNode's INIT (const-ref param-passing). O(n) — walks .head's owning chain to find the node whose .next is the ender (id 1), then splices newNode in front of the ender.

MODIFY METHOD appendCopy(REFERENCE T value) RETURNS STATUS
modifies

Deep-copy form of append. value stays valid for the caller; the clone is the one moved into the new node.

MODIFY METHOD popLast() RETURNS | T
modifies

Remove and return the back user value. EMPTY if empty. O(n) walk from .head to find the second-to-last user node so we can splice the ender into its .next slot. Single-element case short-circuits to popFirst().

Splice ordering : step 1: popped := wasSecondToLast.next (move popped out of the predecessor's next slot) step 2: wasSecondToLast.next := popped.next (move ender into the predecessor's next slot)

METHOD peekLast() RETURNS | REFERENCE T
reads

Read (without removing) the back user value. Pipe-XOR shape: SUCCESS populates value with the reference; empty list populates s with FAILURE. O(n) walk from .head.

MODIFY METHOD insertAt(int32 index, T value) RETURNS STATUS
modifies

MID-CHAIN OPERATIONS (insertAt / removeAt)

Used by SortedList[T] and any other consumer that needs to splice at an arbitrary position. O(index) walk to the target node, then O(1) splice via the same move-out-before-overwrite pattern as prepend/append/popFirst/popLast.

Index 0 and index .length (or .length - 1 for removeAt) delegate to the existing front/back methods to avoid duplicating splice logic. Insert value at position index. Valid range is 0..length (inclusive — index == length appends, equivalent to append). Per §10.2 the bare-named form consumes value (poisoned at the call site). STATUS == FAILURE on out-of-bounds index or kernel-invariant violation; SUCCESS otherwise.

MODIFY METHOD insertAtCopy(int32 index, REFERENCE T value) RETURNS STATUS
modifies

Deep-copy form of insertAt. value stays valid for the caller; the clone is the one moved into the new node.

MODIFY METHOD removeAt(int32 index) RETURNS | T
modifies

Remove and return the user value at position index. STATUS == FAILURE on out-of-bounds index or kernel-invariant violation (paired with EMPTY in the value slot); SUCCESS otherwise (paired with the removed value).