Library / Collections / Lists / LinkedList
LinkedList
Defines the LinkedList[T] class per ENVZN_CONSTITUTION §LinkedList.
Fields 1
int32 lengthConstructors 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 booleanreads
METHOD size() RETURNS int64reads
Number of elements currently stored. Read-only, O(1).
MODIFY METHOD prepend(T value) RETURNS STATUSmodifies
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 STATUSmodifies
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 | Tmodifies
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 Treads
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 Treads
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 STATUSmodifies
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 STATUSmodifies
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 | Tmodifies
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 Treads
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 STATUSmodifies
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 STATUSmodifies
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 | Tmodifies
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).