SinglyLinkedList
data-structure-typed / SinglyLinkedList
Class: SinglyLinkedList<E, R>
Defined in: data-structures/linked-list/singly-linked-list.ts:190
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
Type Parameters
E
E = any
R
R = any
- Node Structure: Each node contains two parts: a data field and a pointer (or reference) to the next node. This structure allows forward-only traversal of the linked list.
- 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:198
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:244
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:213
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:253
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:235
Get the number of elements.
Remarks
Time O(1), Space O(1)
Returns
number
Current length.
Overrides
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
tail
Get Signature
get tail(): SinglyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/singly-linked-list.ts:224
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:48
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
Methods
[iterator]()
iterator: IterableIterator<E>;
Defined in: data-structures/base/iterable-element-base.ts:61
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
addAfter()
addAfter(existingElementOrNode, newElementOrNode): boolean;
Defined in: data-structures/linked-list/singly-linked-list.ts:702
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
addAt()
addAt(index, newElementOrNode): boolean;
Defined in: data-structures/linked-list/singly-linked-list.ts:568
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
addBefore()
addBefore(existingElementOrNode, newElementOrNode): boolean;
Defined in: data-structures/linked-list/singly-linked-list.ts:674
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
at()
at(index): E | undefined;
Defined in: data-structures/linked-list/singly-linked-list.ts:470
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
clear()
clear(): void;
Defined in: data-structures/linked-list/singly-linked-list.ts:616
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
clone()
clone(): this;
Defined in: data-structures/linked-list/singly-linked-list.ts:830
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
concat()
concat(...items): this;
Defined in: data-structures/base/linear-base.ts:462
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
countOccurrences()
countOccurrences(elementOrNode): number;
Defined in: data-structures/linked-list/singly-linked-list.ts:768
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:540
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
deleteAt()
deleteAt(index): E | undefined;
Defined in: data-structures/linked-list/singly-linked-list.ts:517
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
deleteWhere()
deleteWhere(predicate): boolean;
Defined in: data-structures/linked-list/singly-linked-list.ts:796
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)
entries()
entries(): IterableIterator<[number, E]>;
Defined in: data-structures/base/iterable-element-base.ts:207
Return an iterator of [index, value] pairs (Array-compatible).
Returns
IterableIterator<[number, E]>
Remarks
Provided for familiarity when migrating from Array. Time O(n), Space O(1) per step.
Inherited from
every()
every(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-element-base.ts:87
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
fill()
fill(
value,
start?,
end?): this;
Defined in: data-structures/base/linear-base.ts:279
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
filter()
filter(callback, thisArg?): this;
Defined in: data-structures/linked-list/singly-linked-list.ts:858
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
find()
Call Signature
find<S>(predicate, thisArg?): S | 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.
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
Call Signature
find(predicate, thisArg?): E | undefined;
Defined in: data-structures/base/iterable-element-base.ts:164
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
findIndex()
findIndex(predicate, thisArg?): number;
Defined in: data-structures/base/linear-base.ts:147
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
forEach()
forEach(callbackfn, thisArg?): void;
Defined in: data-structures/base/iterable-element-base.ts:133
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
getNode()
getNode(elementNodeOrPredicate?): SinglyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/singly-linked-list.ts:653
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:499
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
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
includes()
includes(element): boolean;
Defined in: data-structures/base/iterable-element-base.ts:199
Check whether a value exists (Array-compatible alias for has).
Parameters
element
E
Element to search for (uses ===).
Returns
boolean
true if found.
Remarks
Provided for familiarity when migrating from Array. Time O(n), Space O(1).
Inherited from
indexOf()
indexOf(searchElement, fromIndex?): number;
Defined in: data-structures/base/linear-base.ts:417
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
isEmpty()
isEmpty(): boolean;
Defined in: data-structures/linked-list/singly-linked-list.ts:602
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
isNode()
isNode(elementNodeOrPredicate): elementNodeOrPredicate is SinglyLinkedListNode<E>;
Defined in: data-structures/linked-list/singly-linked-list.ts:483
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:218
Join all elements into a string.
Parameters
separator?
string = ','
Separator string.
Returns
string
Concatenated string.
Remarks
Time O(n), Space O(n)
Inherited from
keys()
keys(): IterableIterator<number>;
Defined in: data-structures/base/iterable-element-base.ts:218
Return an iterator of numeric indices (Array-compatible).
Returns
IterableIterator<number>
Remarks
Provided for familiarity when migrating from Array. Time O(n), Space O(1) per step.
Inherited from
lastIndexOf()
lastIndexOf(searchElement, fromIndex?): number;
Defined in: data-structures/base/linear-base.ts:440
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
map()
map<EM, RM>(
callback,
options?,
thisArg?): SinglyLinkedList<EM, RM>;
Defined in: data-structures/linked-list/singly-linked-list.ts:897
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
mapSame()
mapSame(callback, thisArg?): this;
Defined in: data-structures/linked-list/singly-linked-list.ts:872
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
pop()
pop(): E | undefined;
Defined in: data-structures/linked-list/singly-linked-list.ts:335
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:298
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
push()
push(elementOrNode): boolean;
Defined in: data-structures/linked-list/singly-linked-list.ts:302
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
pushMany()
pushMany(elements): boolean[];
Defined in: data-structures/linked-list/singly-linked-list.ts:416
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
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:225
Parameters
callbackfn
ReduceElementCallback<E, R>
Returns
E
Inherited from
Call Signature
reduce(callbackfn, initialValue): E;
Defined in: data-structures/base/iterable-element-base.ts:226
Parameters
callbackfn
ReduceElementCallback<E, R>
initialValue
E
Returns
E
Inherited from
Call Signature
reduce<U>(callbackfn, initialValue): U;
Defined in: data-structures/base/iterable-element-base.ts:227
Type Parameters
U
U
Parameters
callbackfn
ReduceElementCallback<E, R, U>
initialValue
U
Returns
U
Inherited from
reduceRight()
reduceRight<U>(callbackfn, initialValue): U;
Defined in: data-structures/base/linear-base.ts:552
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
reverse()
reverse(): this;
Defined in: data-structures/linked-list/singly-linked-list.ts:632
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
search()
search(elementNodeOrPredicate): E | undefined;
Defined in: data-structures/linked-list/singly-linked-list.ts:446
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:587
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
setEquality()
setEquality(equals): this;
Defined in: data-structures/linked-list/singly-linked-list.ts:785
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:363
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:481
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
some()
some(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-element-base.ts:110
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
sort()
sort(compareFn?): this;
Defined in: data-structures/base/linear-base.ts:179
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
splice()
splice(
start,
deleteCount?, ...
items?): this;
Defined in: data-structures/linked-list/singly-linked-list.ts:721
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
toArray()
toArray(): E[];
Defined in: data-structures/base/iterable-element-base.ts:275
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
toReversed()
toReversed(): this;
Defined in: data-structures/base/linear-base.ts:319
Return a new instance of the same type with elements in reverse order (non-mutating).
Returns
this
A new reversed instance.
Remarks
Provided for familiarity when migrating from Array (ES2023 toReversed). Time O(n), Space O(n).
Inherited from
toReversedArray()
toReversedArray(): E[];
Defined in: data-structures/base/linear-base.ts:227
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:287
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
unshift()
unshift(elementOrNode): boolean;
Defined in: data-structures/linked-list/singly-linked-list.ts:398
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:431
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:72
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
from()
static from<E, R, S>(
this,
data,
options?): S;
Defined in: data-structures/linked-list/singly-linked-list.ts:268
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:39
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
Accessors
_createInstance()
protected _createInstance(options?): this;
Defined in: data-structures/linked-list/singly-linked-list.ts:1013
(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:1030
(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:938
(Protected) Normalize input into a node instance.
Parameters
elementOrNode
E | SinglyLinkedListNode<E>
Element or node.
Returns
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:949
(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:976
(Protected) Iterate values from head to tail.
Returns
IterableIterator<E>
Iterator of values (E).
Remarks
Time O(N), Space O(1)
Overrides
_getNodeIterator()
protected _getNodeIterator(): IterableIterator<SinglyLinkedListNode<E>>;
Defined in: data-structures/linked-list/singly-linked-list.ts:999
(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:964
(Protected) Get the previous node of a given node.
Parameters
node
A node in the list.
Returns
SinglyLinkedListNode<E> | undefined
Previous node or undefined.
Remarks
Time O(N), Space O(1)
Overrides
_getReverseIterator()
protected _getReverseIterator(): IterableIterator<E>;
Defined in: data-structures/linked-list/singly-linked-list.ts:989
(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:926
(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:1049
(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:916
(Protected) Create a node from a value.
Parameters
value
E
Value to wrap in a node.
Returns
A new SinglyLinkedListNode instance.
Remarks
Time O(1), Space O(1)