DoublyLinkedList
data-structure-typed / DoublyLinkedList
Class: DoublyLinkedList<E, R>
Defined in: data-structures/linked-list/doubly-linked-list.ts:144
Doubly linked list with O(1) push/pop/unshift/shift and linear scans.
Remarks
Time O(1), Space O(1)
Examples
// Browser history
const browserHistory = new DoublyLinkedList<string>();
browserHistory.push('home page');
browserHistory.push('search page');
browserHistory.push('details page');
console.log(browserHistory.last); // 'details page';
console.log(browserHistory.pop()); // 'details page';
console.log(browserHistory.last); // 'search page';
// DoublyLinkedList for LRU cache implementation
interface CacheEntry {
key: string;
value: string;
}
// Simulate LRU cache using DoublyLinkedList
// DoublyLinkedList is perfect because:
// - O(1) delete from any position
// - O(1) push to end
// - Bidirectional traversal for LRU policy
const cacheList = new DoublyLinkedList<CacheEntry>();
const maxSize = 3;
// Add cache entries
cacheList.push({ key: 'user:1', value: 'Alice' });
cacheList.push({ key: 'user:2', value: 'Bob' });
cacheList.push({ key: 'user:3', value: 'Charlie' });
// Try to add a new entry when cache is full
if (cacheList.length >= maxSize) {
// Remove the oldest (first) entry
const evicted = cacheList.shift();
console.log(evicted?.key); // 'user:1';
}
// Add new entry
cacheList.push({ key: 'user:4', value: 'Diana' });
// Verify current cache state
console.log(cacheList.length); // 3;
const cachedKeys = [...cacheList].map(entry => entry.key);
console.log(cachedKeys); // ['user:2', 'user:3', 'user:4'];
// Access entry (in real LRU, this would move it to end)
const foundEntry = [...cacheList].find(entry => entry.key === 'user:2');
console.log(foundEntry?.value); // 'Bob';
// Find first matching element
const list = new DoublyLinkedList<number>([5, 10, 15, 20]);
console.log(list.find(n => n >= 12)); // 15;
// Iterate over elements
const list = new DoublyLinkedList<number>([1, 2, 3]);
const sum: number[] = [];
list.forEach(n => sum.push(n));
console.log(sum); // [1, 2, 3];
Extends
LinearLinkedBase<E,R,DoublyLinkedListNode<E>>
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 singly linked lists, doubly linked lists can be easily traversed forwards or backwards. This makes insertions and deletions in the list more flexible and efficient.
- 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 DoublyLinkedList<E, R>(elements?, options?): DoublyLinkedList<E, R>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:152
Create a DoublyLinkedList and optionally bulk-insert elements.
Parameters
elements?
| Iterable<E, any, any>
| Iterable<R, any, any>
| Iterable<DoublyLinkedListNode<E>, any, any>
Iterable of elements or nodes (or raw records if toElementFn is provided).
options?
DoublyLinkedListOptions<E, R>
Options such as maxLen and toElementFn.
Returns
DoublyLinkedList<E, R>
New DoublyLinkedList instance.
Remarks
Time O(N), Space O(N)
Overrides
LinearLinkedBase<E, R, DoublyLinkedListNode<E>>.constructor
Properties
first
Get Signature
get first(): E | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:204
Get the first element value.
Remarks
Time O(1), Space O(1)
Returns
E | undefined
First element or undefined.
head
Get Signature
get head(): DoublyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:173
Get the head node.
Remarks
Time O(1), Space O(1)
Returns
DoublyLinkedListNode<E> | undefined
Head node or undefined.
last
Get Signature
get last(): E | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:213
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/doubly-linked-list.ts:195
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(): DoublyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:184
Get the tail node.
Remarks
Time O(1), Space O(1)
Returns
DoublyLinkedListNode<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/doubly-linked-list.ts:526
Insert a new element/node after an existing one.
Parameters
existingElementOrNode
E | DoublyLinkedListNode<E>
Existing element or node.
newElementOrNode
E | DoublyLinkedListNode<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/doubly-linked-list.ts:479
Insert a new element/node at an index, shifting following nodes.
Parameters
index
number
Zero-based index.
newElementOrNode
E | DoublyLinkedListNode<E>
Element or node to insert.
Returns
boolean
True if inserted.
Remarks
Time O(N), Space O(1)
Example
// Insert at position
const list = new DoublyLinkedList<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/doubly-linked-list.ts:501
Insert a new element/node before an existing one.
Parameters
existingElementOrNode
E | DoublyLinkedListNode<E>
Existing element or node.
newElementOrNode
E | DoublyLinkedListNode<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/doubly-linked-list.ts:409
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 by index
const list = new DoublyLinkedList<string>(['a', 'b', 'c']);
console.log(list.at(1)); // 'b';
console.log(list.at(2)); // 'c';
Overrides
clear()
clear(): void;
Defined in: data-structures/linked-list/doubly-linked-list.ts:627
Remove all nodes and reset length.
Returns
void
void
Remarks
Time O(N), Space O(1)
Example
// Remove all
const list = new DoublyLinkedList<number>([1, 2]);
list.clear();
console.log(list.isEmpty()); // true;
Overrides
clone()
clone(): this;
Defined in: data-structures/linked-list/doubly-linked-list.ts:781
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 DoublyLinkedList<number>([1, 2, 3]);
const copy = list.clone();
copy.pop();
console.log(list.length); // 3;
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
delete()
delete(elementOrNode?): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:590
Delete the first match by value/node.
Parameters
elementOrNode?
E | DoublyLinkedListNode<E>
Element or node to remove.
Returns
boolean
True if removed.
Remarks
Time O(N), Space O(1)
Example
// Remove first occurrence
const list = new DoublyLinkedList<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/doubly-linked-list.ts:566
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 DoublyLinkedList<string>(['a', 'b', 'c']);
list.deleteAt(1);
console.log(list.toArray()); // ['a', 'c'];
Overrides
deleteWhere()
deleteWhere(predicate): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:745
Delete the first element that satisfies a predicate.
Parameters
predicate
(value, index, list) => boolean
Function (value, index, list) → boolean to decide deletion.
Returns
boolean
True if a match 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/doubly-linked-list.ts:799
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
// Filter elements
const list = new DoublyLinkedList<number>([1, 2, 3, 4, 5]);
const evens = list.filter(n => n % 2 === 0);
console.log([...evens]); // [2, 4];
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
findLast()
findLast(elementNodeOrPredicate): E | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:689
Find the first value matching a predicate scanning backward (tail → head).
Parameters
elementNodeOrPredicate
| E
| DoublyLinkedListNode<E>
| ((node) => boolean)
Element, node, or predicate to match.
Returns
E | undefined
Matching value or undefined.
Remarks
Time O(N), Space O(1)
Example
// Find value scanning from tail
const list = new DoublyLinkedList<number>([1, 2, 3, 4]);
// findLast scans from tail to head, returns first match
const found = list.findLast(node => node.value < 4);
console.log(found); // 3;
findLastIndex()
findLastIndex(predicate): number;
Defined in: data-structures/linked-list/doubly-linked-list.ts:707
Find the index of the last value matching a predicate (scans tail → head).
Parameters
predicate
(value, index, list) => boolean
Function called with (value, index, list).
Returns
number
Matching index, or -1 if not found.
Remarks
Provided for familiarity when migrating from Array. Time O(n), Space O(1).
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
getBackward()
getBackward(elementNodeOrPredicate): E | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:671
Parameters
elementNodeOrPredicate
| E
| DoublyLinkedListNode<E>
| ((node) => boolean)
Returns
E | undefined
Deprecated
Use findLast instead. Will be removed in a future major version.
getNode()
getNode(elementNodeOrPredicate?): DoublyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:439
Find a node by value, reference, or predicate.
Parameters
elementNodeOrPredicate?
| E
| DoublyLinkedListNode<E>
| ((node) => boolean)
Element, node, or predicate to match.
Returns
DoublyLinkedListNode<E> | undefined
Matching node or undefined.
Remarks
Time O(N), Space O(1)
getNodeAt()
getNodeAt(index): DoublyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:426
Get the node reference at a given index.
Parameters
index
number
Zero-based index.
Returns
DoublyLinkedListNode<E> | undefined
Node or undefined.
Remarks
Time O(N), Space O(1)
Example
// Get node at index
const list = new DoublyLinkedList<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/doubly-linked-list.ts:613
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 DoublyLinkedList().isEmpty()); // true;
Overrides
isNode()
isNode(elementNodeOrPredicate): elementNodeOrPredicate is DoublyLinkedListNode<E>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:242
Type guard: check whether the input is a DoublyLinkedListNode.
Parameters
elementNodeOrPredicate
| E
| DoublyLinkedListNode<E>
| ((node) => boolean)
Element, node, or predicate.
Returns
elementNodeOrPredicate is DoublyLinkedListNode<E>
True if the value is a DoublyLinkedListNode.
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?): DoublyLinkedList<EM, RM>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:847
Map values into a new list (possibly different element type).
Type Parameters
EM
EM
RM
RM
Parameters
callback
ElementCallback<E, R, EM>
Mapping function (value, index, list) → newElement.
options?
DoublyLinkedListOptions<EM, RM>
Options for the output list (e.g., maxLen, toElementFn).
thisArg?
unknown
Value for this inside the callback.
Returns
DoublyLinkedList<EM, RM>
A new DoublyLinkedList with mapped values.
Remarks
Time O(N), Space O(N)
Example
// DoublyLinkedList for...of iteration and map operation
const list = new DoublyLinkedList<number>([1, 2, 3, 4, 5]);
// Iterate through list
const doubled = list.map(value => value * 2);
console.log(doubled.length); // 5;
// Use for...of loop
const result: number[] = [];
for (const item of list) {
result.push(item);
}
console.log(result); // [1, 2, 3, 4, 5];
Overrides
mapSame()
mapSame(callback, thisArg?): this;
Defined in: data-structures/linked-list/doubly-linked-list.ts:813
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/doubly-linked-list.ts:304
Remove and return the tail element.
Returns
E | undefined
Removed element or undefined.
Remarks
Time O(1), Space O(1)
Example
// DoublyLinkedList pop and shift operations
const list = new DoublyLinkedList<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/doubly-linked-list.ts:269
Append an element/node to the tail.
Parameters
elementOrNode
E | DoublyLinkedListNode<E>
Element or node to append.
Returns
boolean
True when appended.
Remarks
Time O(1), Space O(1)
Example
// basic DoublyLinkedList creation and push operation
// Create a simple DoublyLinkedList with initial values
const list = new DoublyLinkedList([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/doubly-linked-list.ts:374
Append a sequence of elements/nodes.
Parameters
elements
| Iterable<E, any, any>
| Iterable<R, any, any>
| Iterable<DoublyLinkedListNode<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/doubly-linked-list.ts:728
Reverse the list in place.
Returns
this
This list.
Remarks
Time O(N), Space O(1)
Example
// Reverse in-place
const list = new DoublyLinkedList<number>([1, 2, 3]);
list.reverse();
console.log([...list]); // [3, 2, 1];
Overrides
search()
search(elementNodeOrPredicate): E | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:644
Find the first value matching a predicate scanning forward.
Parameters
elementNodeOrPredicate
| E
| DoublyLinkedListNode<E>
| ((node) => boolean)
Element, node, or predicate to match.
Returns
E | undefined
Matched value or undefined.
Remarks
Time O(N), Space O(1)
Example
// Search with predicate
const list = new DoublyLinkedList<number>([10, 20, 30]);
const found = list.search(node => node.value > 15);
console.log(found); // 20;
setAt()
setAt(index, value): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:548
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/doubly-linked-list.ts:765
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/doubly-linked-list.ts:328
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 DoublyLinkedList<number>([10, 20, 30]);
console.log(list.shift()); // 10;
console.log(list.first); // 20;
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/base/linear-base.ts:507
Splice by walking node iterators from the start index.
Parameters
start
number
Start index.
deleteCount?
number = 0
How many elements to remove.
items
...E[]
Elements to insert after the splice point.
Returns
this
Removed elements as a new list (this type).
Remarks
Time O(n + m), Space O(min(n, m)) where m = items.length
Inherited from
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/doubly-linked-list.ts:353
Prepend an element/node to the head.
Parameters
elementOrNode
E | DoublyLinkedListNode<E>
Element or node to prepend.
Returns
boolean
True when prepended.
Remarks
Time O(1), Space O(1)
Example
// Add to the front
const list = new DoublyLinkedList<number>([2, 3]);
list.unshift(1);
console.log([...list]); // [1, 2, 3];
unshiftMany()
unshiftMany(elements): boolean[];
Defined in: data-structures/linked-list/doubly-linked-list.ts:389
Prepend a sequence of elements/nodes.
Parameters
elements
| Iterable<E, any, any>
| Iterable<R, any, any>
| Iterable<DoublyLinkedListNode<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
fromArray()
static fromArray<E, R>(this, data): any;
Defined in: data-structures/linked-list/doubly-linked-list.ts:226
Create a new list from an array of elements.
Type Parameters
E
E
R
R = any
Parameters
this
Object
The constructor (subclass) to instantiate.
data
E[]
Array of elements to insert.
Returns
any
A new list populated with the array'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/doubly-linked-list.ts:907
(Protected) Create an empty instance of the same concrete class.
Parameters
options?
LinearBaseOptions<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?): DoublyLinkedList<EM, RM>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:924
(Protected) Create a like-kind instance and seed it from an iterable.
Type Parameters
EM
EM = E
RM
RM = R
Parameters
elements?
| Iterable<EM, any, any>
| Iterable<RM, any, any>
| Iterable<DoublyLinkedListNode<EM>, any, any>
Iterable used to seed the new list.
options?
DoublyLinkedListOptions<EM, RM>
Options forwarded to the constructor.
Returns
DoublyLinkedList<EM, RM>
A like-kind DoublyLinkedList instance.
Remarks
Time O(N), Space O(N)
_ensureNode()
protected _ensureNode(elementOrNode): DoublyLinkedListNode<E>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:866
(Protected) Create or return a node for the given input (node or raw element).
Parameters
elementOrNode
E | DoublyLinkedListNode<E>
Element value or node to normalize.
Returns
A DoublyLinkedListNode for the provided input.
Remarks
Time O(1), Space O(1)
_ensurePredicate()
protected _ensurePredicate(elementNodeOrPredicate): (node) => boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:877
(Protected) Normalize input into a predicate over nodes.
Parameters
elementNodeOrPredicate
| E
| DoublyLinkedListNode<E>
| ((node) => boolean)
Element, node, or node predicate.
Returns
A predicate function 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/doubly-linked-list.ts:935
Internal iterator factory used by the default iterator.
Returns
IterableIterator<E>
An iterator over elements.
Remarks
Implementations should yield in O(1) per element with O(1) extra space when possible.
Overrides
_getNodeIterator()
protected _getNodeIterator(): IterableIterator<DoublyLinkedListNode<E>>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:951
Iterate linked nodes from head to tail.
Returns
IterableIterator<DoublyLinkedListNode<E>>
Iterator over nodes.
Remarks
Time O(n), Space O(1)
Overrides
LinearLinkedBase._getNodeIterator
_getPrevNode()
protected _getPrevNode(node): DoublyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:897
(Protected) Get the previous node of a given node.
Parameters
node
A node in the list.
Returns
DoublyLinkedListNode<E> | undefined
Previous node or undefined.
Remarks
Time O(1), Space O(1)
Overrides
_getReverseIterator()
protected _getReverseIterator(): IterableIterator<E>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:943
Reverse-direction iterator over elements.
Returns
IterableIterator<E>
Iterator of elements from tail to head.
Remarks
Time O(n), Space O(1)
Overrides
LinearLinkedBase._getReverseIterator