DoublyLinkedList
data-structure-typed / DoublyLinkedList
Class: DoublyLinkedList<E, R>
Defined in: data-structures/linked-list/doubly-linked-list.ts:150
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:161
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:219
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:185
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:229
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:209
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:197
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: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
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
addAfter()
addAfter(existingElementOrNode, newElementOrNode): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:794
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:743
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:767
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:604
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:1029
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:1258
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: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
delete()
delete(elementOrNode?): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:925
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:868
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
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
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
filter()
filter(callback, thisArg?): this;
Defined in: data-structures/linked-list/doubly-linked-list.ts:1311
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: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
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
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
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
getBackward()
getBackward(elementNodeOrPredicate): E | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:1134
Find the first value matching a predicate scanning backward.
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
// Find value scanning from tail
const list = new DoublyLinkedList<number>([1, 2, 3, 4]);
// getBackward scans from tail to head, returns first match
const found = list.getBackward(node => node.value < 4);
console.log(found); // 3;
getNode()
getNode(elementNodeOrPredicate?): DoublyLinkedListNode<E> | undefined;
Defined in: data-structures/linked-list/doubly-linked-list.ts:667
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:653
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
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
isEmpty()
isEmpty(): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:982
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:260
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: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
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
map()
map<EM, RM>(
callback,
options?,
thisArg?): DoublyLinkedList<EM, RM>;
Defined in: data-structures/linked-list/doubly-linked-list.ts:1395
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:1326
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:392
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: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
push()
push(elementOrNode): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:322
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:533
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:193
Parameters
callbackfn
ReduceElementCallback<E, R>
Returns
E
Inherited from
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
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
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
reverse()
reverse(): this;
Defined in: data-structures/linked-list/doubly-linked-list.ts:1191
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:1078
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:818
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:1209
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:451
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: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
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
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
splice()
splice(
start,
deleteCount?, ...
items): this;
Defined in: data-structures/base/linear-base.ts:522
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: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
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
unshift()
unshift(elementOrNode): boolean;
Defined in: data-structures/linked-list/doubly-linked-list.ts:511
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:549
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: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
fromArray()
static fromArray<E, R>(this, data): any;
Defined in: data-structures/linked-list/doubly-linked-list.ts:243
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: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
Accessors
_createInstance()
protected _createInstance(options?): this;
Defined in: data-structures/linked-list/doubly-linked-list.ts:1457
(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:1475
(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:1413
(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:1425
(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:1486
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:1502
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:1446
(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:1494
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