SinglyLinkedList

Class: SinglyLinkedList<E, R>

Defined in: data-structures/linked-list/singly-linked-list.ts:194

Singly linked list with O(1) push/pop-like ends operations and linear scans.

Remarks

Time O(1), Space O(1)

Examples

// SinglyLinkedList for sequentially processed data stream
 interface LogEntry {
      timestamp: number;
      level: 'INFO' | 'WARN' | 'ERROR';
      message: string;
    }

    // SinglyLinkedList is ideal for sequential processing where you only need forward iteration
    // O(1) insertion/deletion at head, O(n) for tail operations
    const logStream = new SinglyLinkedList<LogEntry>();

    // Simulate incoming log entries
    const entries: LogEntry[] = [
      { timestamp: 1000, level: 'INFO', message: 'Server started' },
      { timestamp: 1100, level: 'WARN', message: 'Memory usage high' },
      { timestamp: 1200, level: 'ERROR', message: 'Connection failed' },
      { timestamp: 1300, level: 'INFO', message: 'Connection restored' }
    ];

    // Add entries to the stream
    for (const entry of entries) {
      logStream.push(entry);
    }

    console.log(logStream.length); // 4;

    // Process logs sequentially (only forward iteration needed)
    const processedLogs: string[] = [];
    for (const log of logStream) {
      processedLogs.push(`[${log.level}] ${log.message}`);
    }

    console.log(processedLogs); // [
 //      '[INFO] Server started',
 //      '[WARN] Memory usage high',
 //      '[ERROR] Connection failed',
 //      '[INFO] Connection restored'
 //    ];

    // Get first log (O(1) - direct head access)
    const firstLog = logStream.at(0);
    console.log(firstLog?.message); // 'Server started';

    // Remove oldest log (O(1) operation at head)
    const removed = logStream.shift();
    console.log(removed?.message); // 'Server started';
    console.log(logStream.length); // 3;

    // Remaining logs still maintain order for sequential processing
    console.log(logStream.length); // 3;

// implementation of a basic text editor
 class TextEditor {
      private content: SinglyLinkedList<string>;
      private cursorIndex: number;
      private undoStack: Stack<{ operation: string; data?: any }>;

      constructor() {
        this.content = new SinglyLinkedList<string>();
        this.cursorIndex = 0; // Cursor starts at the beginning
        this.undoStack = new Stack<{ operation: string; data?: any }>(); // Stack to keep track of operations for undo
      }

      insert(char: string) {
        this.content.addAt(this.cursorIndex, char);
        this.cursorIndex++;
        this.undoStack.push({ operation: 'insert', data: { index: this.cursorIndex - 1 } });
      }

      delete() {
        if (this.cursorIndex === 0) return; // Nothing to delete
        const deleted = this.content.deleteAt(this.cursorIndex - 1);
        this.cursorIndex--;
        this.undoStack.push({ operation: 'delete', data: { index: this.cursorIndex, char: deleted } });
      }

      moveCursor(index: number) {
        this.cursorIndex = Math.max(0, Math.min(index, this.content.length));
      }

      undo() {
        if (this.undoStack.size === 0) return; // No operations to undo
        const lastAction = this.undoStack.pop();

        if (lastAction!.operation === 'insert') {
          this.content.deleteAt(lastAction!.data.index);
          this.cursorIndex = lastAction!.data.index;
        } else if (lastAction!.operation === 'delete') {
          this.content.addAt(lastAction!.data.index, lastAction!.data.char);
          this.cursorIndex = lastAction!.data.index + 1;
        }
      }

      getText(): string {
        return [...this.content].join('');
      }
    }

    // Example Usage
    const editor = new TextEditor();
    editor.insert('H');
    editor.insert('e');
    editor.insert('l');
    editor.insert('l');
    editor.insert('o');
    console.log(editor.getText()); // 'Hello'; // Output: "Hello"

    editor.delete();
    console.log(editor.getText()); // 'Hell'; // Output: "Hell"

    editor.undo();
    console.log(editor.getText()); // 'Hello'; // Output: "Hello"

    editor.moveCursor(1);
    editor.insert('a');
    console.log(editor.getText()); // 'Haello';

// Find first matching element
 const list = new SinglyLinkedList<number>([1, 2, 3, 4, 5]);
    console.log(list.find(n => n > 3)); // 4;
    console.log(list.find(n => n > 10)); // undefined;

// Iterate over elements
 const list = new SinglyLinkedList<number>([10, 20, 30]);
    const result: number[] = [];
    list.forEach(n => result.push(n));
    console.log(result); // [10, 20, 30];

Extends

LinearLinkedBase<E, R, SinglyLinkedListNode<E>>

Extended by

LinkedListQueue

Type Parameters

E

E = any

R

R = any

Node Structure: Each node contains three parts: a data field, a pointer (or reference) to the previous node, and a pointer to the next node. This structure allows traversal of the linked list in both directions.
Bidirectional Traversal: Unlike doubly linked lists, singly linked lists can be easily traversed forwards but not backwards.
No Centralized Index: Unlike arrays, elements in a linked list are not stored contiguously, so there is no centralized index. Accessing elements in a linked list typically requires traversing from the head or tail node.
High Efficiency in Insertion and Deletion: Adding or removing elements in a linked list does not require moving other elements, making these operations more efficient than in arrays. Caution: Although our linked list classes provide methods such as at, setAt, addAt, and indexOf that are based on array indices, their time complexity, like that of the native Array.lastIndexOf, is 𝑂(𝑛). If you need to use these methods frequently, you might want to consider other data structures, such as Deque or Queue (designed for random access). Similarly, since the native Array.shift method has a time complexity of 𝑂(𝑛), using an array to simulate a queue can be inefficient. In such cases, you should use Queue or Deque, as these data structures leverage deferred array rearrangement, effectively reducing the average time complexity to 𝑂(1).

Constructors

Constructor

new SinglyLinkedList<E, R>(elements?, options?): SinglyLinkedList<E, R>;

Defined in: data-structures/linked-list/singly-linked-list.ts:205

Create a SinglyLinkedList and optionally bulk-insert elements.

Parameters

elements?

| Iterable<E, any, any> | Iterable<R, any, any> | Iterable<SinglyLinkedListNode<E>, any, any>

Iterable of elements or nodes (or raw records if toElementFn is provided).

options?

SinglyLinkedListOptions<E, R>

Options such as maxLen and toElementFn.

Returns

SinglyLinkedList<E, R>

New SinglyLinkedList instance.

Remarks

Time O(N), Space O(N)

Overrides

LinearLinkedBase<E, R, SinglyLinkedListNode<E>>.constructor

Properties

first

Get Signature

get first(): E | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:255

Get the first element value.

Remarks

Time O(1), Space O(1)

Returns

E | undefined

First element or undefined.

head

Get Signature

get head(): SinglyLinkedListNode<E> | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:221

Get the head node.

Remarks

Time O(1), Space O(1)

Returns

SinglyLinkedListNode<E> | undefined

Head node or undefined.

last

Get Signature

get last(): E | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:265

Get the last element value.

Remarks

Time O(1), Space O(1)

Returns

E | undefined

Last element or undefined.

length

Get Signature

get length(): number;

Defined in: data-structures/linked-list/singly-linked-list.ts:245

Get the number of elements.

Remarks

Time O(1), Space O(1)

Returns

number

Current length.

Overrides

LinearLinkedBase.length

maxLen

Get Signature

get maxLen(): number;

Defined in: data-structures/base/linear-base.ts:100

Upper bound for length (if positive), or -1 when unbounded.

Remarks

Time O(1), Space O(1)

Returns

number

Maximum allowed length.

Inherited from

LinearLinkedBase.maxLen

tail

Get Signature

get tail(): SinglyLinkedListNode<E> | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:233

Get the tail node.

Remarks

Time O(1), Space O(1)

Returns

SinglyLinkedListNode<E> | undefined

Tail node or undefined.

toElementFn

Get Signature

get toElementFn(): ((rawElement) => E) | undefined;

Defined in: data-structures/base/iterable-element-base.ts:47

Exposes the current toElementFn, if configured.

Remarks

Time O(1), Space O(1).

Returns

((rawElement) => E) | undefined

The converter function or undefined when not set.

Inherited from

LinearLinkedBase.toElementFn

Methods

[iterator]()

iterator: IterableIterator<E>;

Defined in: data-structures/base/iterable-element-base.ts:60

Returns an iterator over the structure's elements.

Parameters

args

...unknown[]

Optional iterator arguments forwarded to the internal iterator.

Returns

IterableIterator<E>

An IterableIterator<E> that yields the elements in traversal order.

Remarks

Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.

Inherited from

LinearLinkedBase.[iterator]

addAfter()

addAfter(existingElementOrNode, newElementOrNode): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:1129

Insert a new element/node after an existing one.

Parameters

existingElementOrNode

E | SinglyLinkedListNode<E>

Existing element or node.

newElementOrNode

E | SinglyLinkedListNode<E>

Element or node to insert.

Returns

boolean

True if inserted.

Remarks

Time O(N), Space O(1)

Overrides

LinearLinkedBase.addAfter

addAt()

addAt(index, newElementOrNode): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:889

Insert a new element/node at an index, shifting following nodes.

Parameters

index

number

Zero-based index.

newElementOrNode

E | SinglyLinkedListNode<E>

Element or node to insert.

Returns

boolean

True if inserted.

Remarks

Time O(N), Space O(1)

Example

// Insert at index
 const list = new SinglyLinkedList<number>([1, 3]);
    list.addAt(1, 2);
    console.log(list.toArray()); // [1, 2, 3];

Overrides

LinearLinkedBase.addAt

addBefore()

addBefore(existingElementOrNode, newElementOrNode): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:1099

Insert a new element/node before an existing one.

Parameters

existingElementOrNode

E | SinglyLinkedListNode<E>

Existing element or node.

newElementOrNode

E | SinglyLinkedListNode<E>

Element or node to insert.

Returns

boolean

True if inserted.

Remarks

Time O(N), Space O(1)

Overrides

LinearLinkedBase.addBefore

at()

at(index): E | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:661

Get the element at a given index.

Parameters

index

number

Zero-based index.

Returns

E | undefined

Element or undefined.

Remarks

Time O(N), Space O(1)

Example

// Access element by index
 const list = new SinglyLinkedList<string>(['a', 'b', 'c', 'd']);
    console.log(list.at(0)); // 'a';
    console.log(list.at(2)); // 'c';
    console.log(list.at(3)); // 'd';

Overrides

LinearLinkedBase.at

clear()

clear(): void;

Defined in: data-structures/linked-list/singly-linked-list.ts:1004

Remove all nodes and reset length.

Returns

void

void

Remarks

Time O(N), Space O(1)

Example

// Remove all
 const list = new SinglyLinkedList<number>([1, 2, 3]);
    list.clear();
    console.log(list.isEmpty()); // true;

Overrides

LinearLinkedBase.clear

clone()

clone(): this;

Defined in: data-structures/linked-list/singly-linked-list.ts:1302

Deep clone this list (values are copied by reference).

Returns

this

A new list with the same element sequence.

Remarks

Time O(N), Space O(N)

Example

// Deep copy
 const list = new SinglyLinkedList<number>([1, 2, 3]);
    const copy = list.clone();
    copy.pop();
    console.log(list.length); // 3;
    console.log(copy.length); // 2;

Overrides

LinearLinkedBase.clone

concat()

concat(...items): this;

Defined in: data-structures/base/linear-base.ts:473

Concatenate lists/elements preserving order.

Parameters

items

...( | E | LinearBase<E, R, LinkedListNode<E>>)[]

Elements or LinearBase instances.

Returns

this

New list with combined elements (this type).

Remarks

Time O(sum(length)), Space O(sum(length))

Inherited from

LinearLinkedBase.concat

countOccurrences()

countOccurrences(elementOrNode): number;

Defined in: data-structures/linked-list/singly-linked-list.ts:1205

Count how many nodes match a value/node/predicate.

Parameters

elementOrNode

| E | SinglyLinkedListNode<E> | ((node) => boolean)

Element, node, or node predicate to match.

Returns

number

Number of matches in the list.

Remarks

Time O(N), Space O(1)

delete()

delete(elementOrNode?): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:828

Delete the first match by value/node.

Parameters

elementOrNode?

E | SinglyLinkedListNode<E>

Element or node to remove; if omitted/undefined, nothing happens.

Returns

boolean

True if removed.

Remarks

Time O(N), Space O(1)

Example

// Remove first occurrence
 const list = new SinglyLinkedList<number>([1, 2, 3, 2]);
    list.delete(2);
    console.log(list.toArray()); // [1, 3, 2];

Overrides

LinearLinkedBase.delete

deleteAt()

deleteAt(index): E | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:773

Delete the element at an index.

Parameters

index

number

Zero-based index.

Returns

E | undefined

Removed element or undefined.

Remarks

Time O(N), Space O(1)

Example

// Remove by index
 const list = new SinglyLinkedList<string>(['a', 'b', 'c']);
    list.deleteAt(1);
    console.log(list.toArray()); // ['a', 'c'];

Overrides

LinearLinkedBase.deleteAt

deleteWhere()

deleteWhere(predicate): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:1235

Delete the first node whose value matches a predicate.

Parameters

predicate

(value, index, list) => boolean

Predicate (value, index, list) → boolean to decide deletion.

Returns

boolean

True if a node was removed.

Remarks

Time O(N), Space O(1)

every()

every(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-element-base.ts:86

Tests whether all elements satisfy the predicate.

Parameters

predicate

ElementCallback<E, R, boolean>

Function invoked for each element with signature (value, index, self).

thisArg?

unknown

Optional this binding for the predicate.

Returns

boolean

true if every element passes; otherwise false.

Remarks

Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).

Inherited from

LinearLinkedBase.every

fill()

fill(
   value, 
   start?, 
   end?): this;

Defined in: data-structures/base/linear-base.ts:292

Fill a range with a value.

Parameters

value

E

Value to set.

start?

number = 0

Inclusive start.

end?

number = ...

Exclusive end.

Returns

this

This list.

Remarks

Time O(n), Space O(1)

Inherited from

LinearLinkedBase.fill

filter()

filter(callback, thisArg?): this;

Defined in: data-structures/linked-list/singly-linked-list.ts:1365

Filter values into a new list of the same class.

Parameters

callback

ElementCallback<E, R, boolean>

Predicate (value, index, list) → boolean to keep value.

thisArg?

unknown

Value for this inside the callback.

Returns

this

A new list with kept values.

Remarks

Time O(N), Space O(N)

Example

// SinglyLinkedList filter and map operations
 const list = new SinglyLinkedList<number>([1, 2, 3, 4, 5]);

    // Filter even numbers
    const filtered = list.filter(value => value % 2 === 0);
    console.log(filtered.length); // 2;

    // Map to double values
    const doubled = list.map(value => value * 2);
    console.log(doubled.length); // 5;

    // Use reduce to sum
    const sum = list.reduce((acc, value) => acc + value, 0);
    console.log(sum); // 15;

Overrides

LinearLinkedBase.filter

find()

Call Signature

find<S>(predicate, thisArg?): S | undefined;

Defined in: data-structures/base/iterable-element-base.ts:162

Finds the first element that satisfies the predicate and returns it.

Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.

Type Parameters

S

S

Parameters

predicate

ElementCallback<E, R, S>

Type-guard predicate: (value, index, self) => value is S.

thisArg?

unknown

Optional this binding for the predicate.

Returns

S | undefined

The matched element typed as S, or undefined if not found.

Remarks

Time O(n) in the worst case; may exit early on the first match. Space O(1).

Inherited from

LinearLinkedBase.find

Call Signature

find(predicate, thisArg?): E | undefined;

Defined in: data-structures/base/iterable-element-base.ts:163

Finds the first element that satisfies the predicate and returns it.

Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.

Parameters

predicate

ElementCallback<E, R, unknown>

Type-guard predicate: (value, index, self) => value is S.

thisArg?

unknown

Optional this binding for the predicate.

Returns

E | undefined

The matched element typed as S, or undefined if not found.

Remarks

Time O(n) in the worst case; may exit early on the first match. Space O(1).

Inherited from

LinearLinkedBase.find

findIndex()

findIndex(predicate, thisArg?): number;

Defined in: data-structures/base/linear-base.ts:151

Find the first index matching a predicate.

Parameters

predicate

ElementCallback<E, R, boolean>

(element, index, self) => boolean.

thisArg?

unknown

Optional this for callback.

Returns

number

Index or -1.

Remarks

Time O(n), Space O(1)

Inherited from

LinearLinkedBase.findIndex

forEach()

forEach(callbackfn, thisArg?): void;

Defined in: data-structures/base/iterable-element-base.ts:132

Invokes a callback for each element in iteration order.

Parameters

callbackfn

ElementCallback<E, R, void>

Function invoked per element with signature (value, index, self).

thisArg?

unknown

Optional this binding for the callback.

Returns

void

void.

Remarks

Time O(n), Space O(1).

Inherited from

LinearLinkedBase.forEach

getNode()

getNode(elementNodeOrPredicate?): SinglyLinkedListNode<E> | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:1077

Find a node by value, reference, or predicate.

Parameters

elementNodeOrPredicate?

| E | SinglyLinkedListNode<E> | ((node) => boolean)

Element, node, or node predicate to match.

Returns

SinglyLinkedListNode<E> | undefined

Matching node or undefined.

Remarks

Time O(N), Space O(1)

getNodeAt()

getNodeAt(index): SinglyLinkedListNode<E> | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:723

Get the node reference at a given index.

Parameters

index

number

Zero-based index.

Returns

SinglyLinkedListNode<E> | undefined

Node or undefined.

Remarks

Time O(N), Space O(1)

Example

// Get node at index
 const list = new SinglyLinkedList<string>(['a', 'b', 'c']);
    console.log(list.getNodeAt(1)?.value); // 'b';

Overrides

LinearLinkedBase.getNodeAt

has()

has(element): boolean;

Defined in: data-structures/base/iterable-element-base.ts:188

Checks whether a strictly-equal element exists in the structure.

Parameters

element

E

The element to test with === equality.

Returns

boolean

true if an equal element is found; otherwise false.

Remarks

Time O(n) in the worst case. Space O(1).

Inherited from

LinearLinkedBase.has

indexOf()

indexOf(searchElement, fromIndex?): number;

Defined in: data-structures/base/linear-base.ts:422

Linked-list optimized indexOf (forwards scan).

Parameters

searchElement

E

Value to match.

fromIndex?

number = 0

Start position.

Returns

number

Index or -1.

Remarks

Time O(n), Space O(1)

Inherited from

LinearLinkedBase.indexOf

isEmpty()

isEmpty(): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:957

Check whether the list is empty.

Returns

boolean

True if length is 0.

Remarks

Time O(1), Space O(1)

Example

// Check empty
 console.log(new SinglyLinkedList().isEmpty()); // true;

Overrides

LinearLinkedBase.isEmpty

isNode()

isNode(elementNodeOrPredicate): elementNodeOrPredicate is SinglyLinkedListNode<E>;

Defined in: data-structures/linked-list/singly-linked-list.ts:675

Type guard: check whether the input is a SinglyLinkedListNode.

Parameters

elementNodeOrPredicate

| E | SinglyLinkedListNode<E> | ((node) => boolean)

Element, node, or predicate.

Returns

elementNodeOrPredicate is SinglyLinkedListNode<E>

True if the value is a SinglyLinkedListNode.

Remarks

Time O(1), Space O(1)

join()

join(separator?): string;

Defined in: data-structures/base/linear-base.ts:228

Join all elements into a string.

Parameters

separator?

string = ','

Separator string.

Returns

string

Concatenated string.

Remarks

Time O(n), Space O(n)

Inherited from

LinearLinkedBase.join

lastIndexOf()

lastIndexOf(searchElement, fromIndex?): number;

Defined in: data-structures/base/linear-base.ts:448

Linked-list optimized lastIndexOf (reverse scan).

Parameters

searchElement

E

Value to match.

fromIndex?

number = ...

Start position.

Returns

number

Index or -1.

Remarks

Time O(n), Space O(1)

Inherited from

LinearLinkedBase.lastIndexOf

map()

map<EM, RM>(
   callback, 
   options?, 
thisArg?): SinglyLinkedList<EM, RM>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1440

Map values into a new list (possibly different element type).

Type Parameters

EM

EM

RM

RM = any

Parameters

callback

ElementCallback<E, R, EM>

Mapping function (value, index, list) → newElement.

options?

SinglyLinkedListOptions<EM, RM>

Options for the output list (e.g., maxLen, toElementFn).

thisArg?

unknown

Value for this inside the callback.

Returns

SinglyLinkedList<EM, RM>

A new SinglyLinkedList with mapped values.

Remarks

Time O(N), Space O(N)

Example

// Transform elements
 const list = new SinglyLinkedList<number>([1, 2, 3]);
    const doubled = list.map(n => n * 2);
    console.log([...doubled]); // [2, 4, 6];

Overrides

LinearLinkedBase.map

mapSame()

mapSame(callback, thisArg?): this;

Defined in: data-structures/linked-list/singly-linked-list.ts:1380

Map values into a new list of the same class.

Parameters

callback

ElementCallback<E, R, E>

Mapping function (value, index, list) → newValue.

thisArg?

unknown

Value for this inside the callback.

Returns

this

A new list with mapped values.

Remarks

Time O(N), Space O(N)

Overrides

LinearLinkedBase.mapSame

pop()

pop(): E | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:418

Remove and return the tail element.

Returns

E | undefined

Removed element or undefined.

Remarks

Time O(N), Space O(1)

Example

// SinglyLinkedList pop and shift operations
 const list = new SinglyLinkedList<number>([10, 20, 30, 40, 50]);

    // Pop removes from the end
    const last = list.pop();
    console.log(last); // 50;

    // Shift removes from the beginning
    const first = list.shift();
    console.log(first); // 10;

    // Verify remaining elements
    console.log([...list]); // [20, 30, 40];
    console.log(list.length); // 3;

print()

print(): void;

Defined in: data-structures/base/iterable-element-base.ts:268

Prints toVisual() to the console. Intended for quick debugging.

Returns

void

void.

Remarks

Time O(n) due to materialization, Space O(n) for the intermediate representation.

Inherited from

LinearLinkedBase.print

push()

push(elementOrNode): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:350

Append an element/node to the tail.

Parameters

elementOrNode

E | SinglyLinkedListNode<E>

Element or node to append.

Returns

boolean

True when appended.

Remarks

Time O(1), Space O(1)

Example

// basic SinglyLinkedList creation and push operation
 // Create a simple SinglyLinkedList with initial values
    const list = new SinglyLinkedList([1, 2, 3, 4, 5]);

    // Verify the list maintains insertion order
    console.log([...list]); // [1, 2, 3, 4, 5];

    // Check length
    console.log(list.length); // 5;

    // Push a new element to the end
    list.push(6);
    console.log(list.length); // 6;
    console.log([...list]); // [1, 2, 3, 4, 5, 6];

Overrides

LinearLinkedBase.push

pushMany()

pushMany(elements): boolean[];

Defined in: data-structures/linked-list/singly-linked-list.ts:570

Append a sequence of elements/nodes.

Parameters

elements

| Iterable<E, any, any> | Iterable<R, any, any> | Iterable<SinglyLinkedListNode<E>, any, any>

Iterable of elements or nodes (or raw records if toElementFn is provided).

Returns

boolean[]

Array of per-element success flags.

Remarks

Time O(N), Space O(1)

Overrides

LinearLinkedBase.pushMany

reduce()

Reduces all elements to a single accumulated value.

Param

Reducer of signature (acc, value, index, self) => nextAcc. The first element is used as the initial accumulator.

Param

Reducer of signature (acc, value, index, self) => nextAcc.

Param

The initial accumulator value of type E.

Template

The accumulator type when it differs from E.

Param

Reducer of signature (acc: U, value, index, self) => U.

Param

The initial accumulator value of type U.

Remarks

Time O(n), Space O(1). Throws if called on an empty structure without initialValue.

Call Signature

reduce(callbackfn): E;

Defined in: data-structures/base/iterable-element-base.ts:193

Parameters

callbackfn

ReduceElementCallback<E, R>

Returns

E

Inherited from

LinearLinkedBase.reduce

Call Signature

reduce(callbackfn, initialValue): E;

Defined in: data-structures/base/iterable-element-base.ts:194

Parameters

callbackfn

ReduceElementCallback<E, R>

initialValue

E

Returns

E

Inherited from

LinearLinkedBase.reduce

Call Signature

reduce<U>(callbackfn, initialValue): U;

Defined in: data-structures/base/iterable-element-base.ts:195

Type Parameters

U

U

Parameters

callbackfn

ReduceElementCallback<E, R, U>

initialValue

U

Returns

U

Inherited from

LinearLinkedBase.reduce

reduceRight()

reduceRight<U>(callbackfn, initialValue): U;

Defined in: data-structures/base/linear-base.ts:574

Right-to-left reduction using reverse iterator.

Type Parameters

U

U

Parameters

callbackfn

ReduceLinearCallback<E, U>

(acc, element, index, self) => acc.

initialValue

U

Initial accumulator.

Returns

U

Final accumulator.

Remarks

Time O(n), Space O(1)

Inherited from

LinearLinkedBase.reduceRight

reverse()

reverse(): this;

Defined in: data-structures/linked-list/singly-linked-list.ts:1055

Reverse the list in place.

Returns

this

This list.

Remarks

Time O(N), Space O(1)

Example

// Reverse the list in-place
 const list = new SinglyLinkedList<number>([1, 2, 3, 4]);
    list.reverse();
    console.log([...list]); // [4, 3, 2, 1];

Overrides

LinearLinkedBase.reverse

search()

search(elementNodeOrPredicate): E | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:602

Find the first value matching a predicate (by node).

Parameters

elementNodeOrPredicate

| E | SinglyLinkedListNode<E> | ((node) => boolean)

Element, node, or node predicate to match.

Returns

E | undefined

Matched value or undefined.

Remarks

Time O(N), Space O(1)

setAt()

setAt(index, value): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:909

Set the element value at an index.

Parameters

index

number

Zero-based index.

value

E

New value.

Returns

boolean

True if updated.

Remarks

Time O(N), Space O(1)

Overrides

LinearLinkedBase.setAt

setEquality()

setEquality(equals): this;

Defined in: data-structures/linked-list/singly-linked-list.ts:1223

Set the equality comparator used to compare values.

Parameters

equals

(a, b) => boolean

Equality predicate (a, b) → boolean.

Returns

this

This list.

Remarks

Time O(1), Space O(1)

shift()

shift(): E | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:481

Remove and return the head element.

Returns

E | undefined

Removed element or undefined.

Remarks

Time O(1), Space O(1)

Example

// Remove from the front
 const list = new SinglyLinkedList<number>([10, 20, 30]);
    console.log(list.shift()); // 10;
    console.log(list.length); // 2;

slice()

slice(start?, end?): this;

Defined in: data-structures/base/linear-base.ts:494

Slice via forward iteration (no random access required).

Parameters

start?

number = 0

Inclusive start (supports negative index).

end?

number = ...

Exclusive end (supports negative index).

Returns

this

New list (this type).

Remarks

Time O(n), Space O(n)

Inherited from

LinearLinkedBase.slice

some()

some(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-element-base.ts:109

Tests whether at least one element satisfies the predicate.

Parameters

predicate

ElementCallback<E, R, boolean>

Function invoked for each element with signature (value, index, self).

thisArg?

unknown

Optional this binding for the predicate.

Returns

boolean

true if any element passes; otherwise false.

Remarks

Time O(n) in the worst case; may exit early on first success. Space O(1).

Inherited from

LinearLinkedBase.some

sort()

sort(compareFn?): this;

Defined in: data-structures/base/linear-base.ts:185

In-place stable order via array sort semantics.

Parameters

compareFn?

(a, b) => number

Comparator (a, b) => number.

Returns

this

This container.

Remarks

Time O(n log n), Space O(n) (materializes to array temporarily)

Inherited from

LinearLinkedBase.sort

splice()

splice(
   start, 
   deleteCount?, ...
   items?): this;

Defined in: data-structures/linked-list/singly-linked-list.ts:1149

Remove and/or insert elements at a position (array-like behavior).

Parameters

start

number

Start index (clamped to [0, length]).

deleteCount?

number = 0

Number of elements to remove (default 0).

items?

...E[]

Elements to insert after start.

Returns

this

A new list containing the removed elements (typed as this).

Remarks

Time O(N + M), Space O(M)

Overrides

LinearLinkedBase.splice

toArray()

toArray(): E[];

Defined in: data-structures/base/iterable-element-base.ts:245

Materializes the elements into a new array.

Returns

E[]

A shallow array copy of the iteration order.

Remarks

Time O(n), Space O(n).

Inherited from

LinearLinkedBase.toArray

toReversedArray()

toReversedArray(): E[];

Defined in: data-structures/base/linear-base.ts:237

Snapshot elements into a reversed array.

Returns

E[]

New reversed array.

Remarks

Time O(n), Space O(n)

Inherited from

LinearLinkedBase.toReversedArray

toVisual()

toVisual(): E[];

Defined in: data-structures/base/iterable-element-base.ts:257

Returns a representation of the structure suitable for quick visualization. Defaults to an array of elements; subclasses may override to provide richer visuals.

Returns

E[]

A visual representation (array by default).

Remarks

Time O(n), Space O(n).

Inherited from

LinearLinkedBase.toVisual

unshift()

unshift(elementOrNode): boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:551

Prepend an element/node to the head.

Parameters

elementOrNode

E | SinglyLinkedListNode<E>

Element or node to prepend.

Returns

boolean

True when prepended.

Remarks

Time O(1), Space O(1)

Example

// SinglyLinkedList unshift and forward traversal
 const list = new SinglyLinkedList<number>([20, 30, 40]);

    // Unshift adds to the beginning
    list.unshift(10);
    console.log([...list]); // [10, 20, 30, 40];

    // Access elements (forward traversal only for singly linked)
    const second = list.at(1);
    console.log(second); // 20;

    // SinglyLinkedList allows forward iteration only
    const elements: number[] = [];
    for (const item of list) {
      elements.push(item);
    }
    console.log(elements); // [10, 20, 30, 40];

    console.log(list.length); // 4;

unshiftMany()

unshiftMany(elements): boolean[];

Defined in: data-structures/linked-list/singly-linked-list.ts:586

Prepend a sequence of elements/nodes.

Parameters

elements

| Iterable<E, any, any> | Iterable<R, any, any> | Iterable<SinglyLinkedListNode<E>, any, any>

Iterable of elements or nodes (or raw records if toElementFn is provided).

Returns

boolean[]

Array of per-element success flags.

Remarks

Time O(N), Space O(1)

values()

values(): IterableIterator<E>;

Defined in: data-structures/base/iterable-element-base.ts:71

Returns an iterator over the values (alias of the default iterator).

Returns

IterableIterator<E>

An IterableIterator<E> over all elements.

Remarks

Creating the iterator is O(1); full iteration is Time O(n), Space O(1).

Inherited from

LinearLinkedBase.values

from()

static from<E, R, S>(
   this, 
   data, 
   options?): S;

Defined in: data-structures/linked-list/singly-linked-list.ts:281

Create a new list from an iterable of elements.

Type Parameters

E

E

R

R = any

S

S extends SinglyLinkedList<E, R> = SinglyLinkedList<E, R>

Parameters

this

Object

The constructor (subclass) to instantiate.

data

Iterable<E>

Iterable of elements to insert.

options?

SinglyLinkedListOptions<E, R>

Options forwarded to the constructor.

Returns

S

A new list populated with the iterable's elements.

Remarks

Time O(N), Space O(N)

Protected Members

_toElementFn?

protected optional _toElementFn?: (rawElement) => E;

Defined in: data-structures/base/iterable-element-base.ts:38

The converter used to transform a raw element (R) into a public element (E).

Parameters

rawElement

R

Returns

E

Remarks

Time O(1), Space O(1).

Inherited from

LinearLinkedBase._toElementFn

Accessors

_createInstance()

protected _createInstance(options?): this;

Defined in: data-structures/linked-list/singly-linked-list.ts:1563

(Protected) Create an empty instance of the same concrete class.

Parameters

options?

SinglyLinkedListOptions<E, R>

Options forwarded to the constructor.

Returns

this

An empty like-kind list instance.

Remarks

Time O(1), Space O(1)

Overrides

LinearLinkedBase._createInstance

_createLike()

protected _createLike<EM, RM>(elements?, options?): SinglyLinkedList<EM, RM>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1581

(Protected) Create a like-kind instance and seed it from an iterable.

Type Parameters

EM

EM

RM

RM

Parameters

elements?

| Iterable<EM, any, any> | Iterable<RM, any, any> | Iterable<SinglyLinkedListNode<EM>, any, any>

Iterable used to seed the new list.

options?

SinglyLinkedListOptions<EM, RM>

Options forwarded to the constructor.

Returns

SinglyLinkedList<EM, RM>

A like-kind SinglyLinkedList instance.

Remarks

Time O(N), Space O(N)

_ensureNode()

protected _ensureNode(elementOrNode): SinglyLinkedListNode<E>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1482

(Protected) Normalize input into a node instance.

Parameters

elementOrNode

E | SinglyLinkedListNode<E>

Element or node.

Returns

SinglyLinkedListNode<E>

A SinglyLinkedListNode for the provided input.

Remarks

Time O(1), Space O(1)

_ensurePredicate()

protected _ensurePredicate(elementNodeOrPredicate): (node) => boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:1494

(Protected) Normalize input into a node predicate.

Parameters

elementNodeOrPredicate

| E | SinglyLinkedListNode<E> | ((node) => boolean)

Element, node, or predicate.

Returns

A predicate taking a node and returning true/false.

(node) => boolean

Remarks

Time O(1), Space O(1)

_getIterator()

protected _getIterator(): IterableIterator<E>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1523

(Protected) Iterate values from head to tail.

Returns

IterableIterator<E>

Iterator of values (E).

Remarks

Time O(N), Space O(1)

Overrides

LinearLinkedBase._getIterator

_getNodeIterator()

protected _getNodeIterator(): IterableIterator<SinglyLinkedListNode<E>>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1548

(Protected) Iterate nodes from head to tail.

Returns

IterableIterator<SinglyLinkedListNode<E>>

Iterator of nodes.

Remarks

Time O(N), Space O(1)

Overrides

LinearLinkedBase._getNodeIterator

_getPrevNode()

protected _getPrevNode(node): SinglyLinkedListNode<E> | undefined;

Defined in: data-structures/linked-list/singly-linked-list.ts:1510

(Protected) Get the previous node of a given node.

Parameters

node

SinglyLinkedListNode<E>

A node in the list.

Returns

SinglyLinkedListNode<E> | undefined

Previous node or undefined.

Remarks

Time O(N), Space O(1)

Overrides

LinearLinkedBase._getPrevNode

_getReverseIterator()

protected _getReverseIterator(): IterableIterator<E>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1537

(Protected) Iterate values from tail to head.

Returns

IterableIterator<E>

Iterator of values (E).

Remarks

Time O(N), Space O(N)

Overrides

LinearLinkedBase._getReverseIterator

_isPredicate()

protected _isPredicate(elementNodeOrPredicate): elementNodeOrPredicate is (node: SinglyLinkedListNode<E>) => boolean;

Defined in: data-structures/linked-list/singly-linked-list.ts:1469

(Protected) Check if input is a node predicate function.

Parameters

elementNodeOrPredicate

| E | SinglyLinkedListNode<E> | ((node) => boolean)

Element, node, or node predicate.

Returns

elementNodeOrPredicate is (node: SinglyLinkedListNode<E>) => boolean

True if input is a predicate function.

Remarks

Time O(1), Space O(1)

_spawnLike()

protected _spawnLike<EM, RM>(options?): SinglyLinkedList<EM, RM>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1601

(Protected) Spawn an empty like-kind list instance.

Type Parameters

EM

EM

RM

RM

Parameters

options?

SinglyLinkedListOptions<EM, RM>

Options forwarded to the constructor.

Returns

SinglyLinkedList<EM, RM>

An empty like-kind SinglyLinkedList instance.

Remarks

Time O(1), Space O(1)

createNode()

protected createNode(value): SinglyLinkedListNode<E>;

Defined in: data-structures/linked-list/singly-linked-list.ts:1458

(Protected) Create a node from a value.

Parameters

value

E

Value to wrap in a node.

Returns

SinglyLinkedListNode<E>

A new SinglyLinkedListNode instance.

Remarks

Time O(1), Space O(1)

Class: SinglyLinkedList<E, R>

Remarks​

Examples​

Extends​

Extended by​

Type Parameters​

E​

R​

Constructors​

Constructor​

Parameters​

elements?​

options?​

Returns​

Remarks​

Overrides​

Properties​

first​

Get Signature​

Remarks​

Returns​

head​

Get Signature​

Remarks​

Returns​

last​

Get Signature​

Remarks​

Returns​

length​

Get Signature​

Remarks​

Returns​

Overrides​

maxLen​

Get Signature​

Remarks​

Returns​

Inherited from​

tail​

Get Signature​

Remarks​

Returns​

toElementFn​

Get Signature​

Remarks​

Returns​

Inherited from​

Methods​

[iterator]()​

Parameters​

args​

Returns​

Remarks​

Inherited from​

addAfter()​

Parameters​

existingElementOrNode​

newElementOrNode​

Returns​

Remarks​

Overrides​

addAt()​

Parameters​

index​

newElementOrNode​

Returns​

Remarks​

Example​

Overrides​

addBefore()​

Parameters​

existingElementOrNode​

newElementOrNode​

Returns​

Remarks​

Overrides​

at()​

Parameters​

index​

Remarks

Examples

Extends

Extended by

Type Parameters

E

R

Constructors

Constructor

Parameters

elements?

options?

Returns

Remarks

Overrides

Properties

first

Get Signature

Remarks

Returns

head

Get Signature

Remarks

Returns

last

Get Signature

Remarks

Returns

length

Get Signature

Remarks

Returns

Overrides

maxLen

Get Signature

Remarks

Returns

Inherited from

tail

Get Signature

Remarks

Returns

toElementFn

Get Signature

Remarks

Returns

Inherited from

Methods

[iterator]()

Parameters

args

Returns

Remarks

Inherited from

addAfter()

Parameters

existingElementOrNode

newElementOrNode

Returns

Remarks

Overrides

addAt()

Parameters

index

newElementOrNode

Returns

Remarks

Example

Overrides

addBefore()

Parameters

existingElementOrNode

newElementOrNode

Returns

Remarks

Overrides

at()

Parameters

index

Returns