Class DoublyLinkedList<E, R>

Doubly linked list with O(1) push/pop/unshift/shift and linear scans.

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];

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;

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];

Example

// 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';

Example

// 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';

Type Parameters

E = any
R = any
1. 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.
2. 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.
3. 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.
4. 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).

Hierarchy

LinearLinkedBase<E, R, DoublyLinkedListNode<E>>
- DoublyLinkedList

Constructors

constructor

new DoublyLinkedList<E, R>(elements?, options?): DoublyLinkedList<E, R>
Create a DoublyLinkedList and optionally bulk-insert elements.
Type Parameters
- E = any
- R = any
Parameters
- Optionalelements: 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).
- Optionaloptions: 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
- Defined in data-structures/linked-list/doubly-linked-list.ts:195

Properties

`Protected` `Optional`_toElementFn

_toElementFn?: ((rawElement: R) => E)

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

Remarks

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

Accessors

first

get first(): undefined | E
Get the first element value.

Returns undefined | E
First element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:253

head

get head(): undefined | DoublyLinkedListNode<E>
Get the head node.

Returns undefined | DoublyLinkedListNode<E>
Head node or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:219

last

get last(): undefined | E
Get the last element value.

Returns undefined | E
Last element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:263

length

get length(): number
Get the number of elements.

Returns number
Current length.

Remarks
Time O(1), Space O(1)
Overrides LinearLinkedBase.length
- Defined in data-structures/linked-list/doubly-linked-list.ts:243

maxLen

get maxLen(): number
Upper bound for length (if positive), or -1 when unbounded.

Returns number
Maximum allowed length.

Remarks
Time O(1), Space O(1)
Inherited from LinearLinkedBase.maxLen
- Defined in data-structures/base/linear-base.ts:100

tail

get tail(): undefined | DoublyLinkedListNode<E>
Get the tail node.

Returns undefined | DoublyLinkedListNode<E>
Tail node or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:231

toElementFn

get toElementFn(): undefined | ((rawElement: R) => E)
Exposes the current toElementFn, if configured.

Returns undefined | ((rawElement: R) => E)
The converter function or undefined when not set.

Remarks
Time O(1), Space O(1).
Inherited from LinearLinkedBase.toElementFn
- Defined in data-structures/base/iterable-element-base.ts:47

Methods

`Protected`_createInstance

_createInstance(options?): this
(Protected) Create an empty instance of the same concrete class.
Parameters
- Optionaloptions: 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
- Defined in data-structures/linked-list/doubly-linked-list.ts:824

`Protected`_createLike

_createLike<EM, RM>(elements?, options?): DoublyLinkedList<EM, RM>
(Protected) Create a like-kind instance and seed it from an iterable.
Type Parameters
- EM = E
- RM = R
Parameters
- Optionalelements: Iterable<EM, any, any> | Iterable<RM, any, any> | Iterable<DoublyLinkedListNode<EM>, any, any> = []
  Iterable used to seed the new list.
- Optionaloptions: DoublyLinkedListOptions<EM, RM>
  Options forwarded to the constructor.
Returns DoublyLinkedList<EM, RM>
A like-kind DoublyLinkedList instance.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/linked-list/doubly-linked-list.ts:842

`Protected`_ensureNode

_ensureNode(elementOrNode): DoublyLinkedListNode<E>
(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 DoublyLinkedListNode<E>
A DoublyLinkedListNode for the provided input.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:780

`Protected`_ensurePredicate

_ensurePredicate(elementNodeOrPredicate): ((node: DoublyLinkedListNode<E>) => boolean)
(Protected) Normalize input into a predicate over nodes.
Parameters
- elementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)
  Element, node, or node predicate.
Returns ((node: DoublyLinkedListNode<E>) => boolean)
A predicate function taking a node and returning true/false.
- - (node): boolean
  - Parameters
    - node: DoublyLinkedListNode<E>
    Returns boolean
Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:792

`Protected`_getIterator

_getIterator(): IterableIterator<E, any, any>
Internal iterator factory used by the default iterator.

Returns IterableIterator<E, any, any>
An iterator over elements.

Remarks
Implementations should yield in O(1) per element with O(1) extra space when possible.
Overrides LinearLinkedBase._getIterator
- Defined in data-structures/linked-list/doubly-linked-list.ts:853

`Protected`_getNodeIterator

_getNodeIterator(): IterableIterator<DoublyLinkedListNode<E>, any, any>
Iterate linked nodes from head to tail.

Returns IterableIterator<DoublyLinkedListNode<E>, any, any>
Iterator over nodes.

Remarks
Time O(n), Space O(1)
Overrides LinearLinkedBase._getNodeIterator
- Defined in data-structures/linked-list/doubly-linked-list.ts:869

`Protected`_getPrevNode

_getPrevNode(node): undefined | DoublyLinkedListNode<E>
(Protected) Get the previous node of a given node.
Parameters
- node: DoublyLinkedListNode<E>
  A node in the list.
Returns undefined | DoublyLinkedListNode<E>
Previous node or undefined.

Remarks
Time O(1), Space O(1)
Overrides LinearLinkedBase._getPrevNode
- Defined in data-structures/linked-list/doubly-linked-list.ts:813

`Protected`_getReverseIterator

_getReverseIterator(): IterableIterator<E, any, any>
Reverse-direction iterator over elements.

Returns IterableIterator<E, any, any>
Iterator of elements from tail to head.

Remarks
Time O(n), Space O(1)
Overrides LinearLinkedBase._getReverseIterator
- Defined in data-structures/linked-list/doubly-linked-list.ts:861

[iterator]

[iterator](...args): IterableIterator<E, any, any>
Returns an iterator over the structure's elements.
Parameters
- Rest...args: unknown[]
  Optional iterator arguments forwarded to the internal iterator.
Returns IterableIterator<E, any, any>
An IterableIterator<E> that yields the elements in traversal order.

Remarks
Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.
Inherited from LinearLinkedBase.[iterator]
- Defined in data-structures/base/iterable-element-base.ts:60

addAfter

addAfter(existingElementOrNode, newElementOrNode): boolean
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 LinearLinkedBase.addAfter
- Defined in data-structures/linked-list/doubly-linked-list.ts:542

addAt

addAt(index, newElementOrNode): boolean
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)
Overrides LinearLinkedBase.addAt
- Defined in data-structures/linked-list/doubly-linked-list.ts:491

addBefore

addBefore(existingElementOrNode, newElementOrNode): boolean
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 LinearLinkedBase.addBefore
- Defined in data-structures/linked-list/doubly-linked-list.ts:515

at

at(index): undefined | E
Get the element at a given index.
Parameters
- index: number
  Zero-based index.
Returns undefined | E
Element or undefined.

Remarks
Time O(N), Space O(1)
Overrides LinearLinkedBase.at
- Defined in data-structures/linked-list/doubly-linked-list.ts:423

clear

clear(): void
Remove all nodes and reset length.

Returns void
void

Remarks
Time O(N), Space O(1)
Overrides LinearLinkedBase.clear
- Defined in data-structures/linked-list/doubly-linked-list.ts:633

clone

clone(): this
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)
Overrides LinearLinkedBase.clone
- Defined in data-structures/linked-list/doubly-linked-list.ts:712

concat

concat(...items): this
Concatenate lists/elements preserving order.
Parameters
- Rest...items: LinearBase<E, R, LinkedListNode<E>>[]
  Elements or LinearBase instances.
Returns this
New list with combined elements (this type).

Remarks
Time O(sum(length)), Space O(sum(length))
Inherited from LinearLinkedBase.concat
- Defined in data-structures/base/linear-base.ts:481

delete

delete(elementOrNode?): boolean
Delete the first match by value/node.
Parameters
- OptionalelementOrNode: E | DoublyLinkedListNode<E>
  Element or node to remove.
Returns boolean
True if removed.

Remarks
Time O(N), Space O(1)
Overrides LinearLinkedBase.delete
- Defined in data-structures/linked-list/doubly-linked-list.ts:601

deleteAt

deleteAt(index): undefined | E
Delete the element at an index.
Parameters
- index: number
  Zero-based index.
Returns undefined | E
Removed element or undefined.

Remarks
Time O(N), Space O(1)
Overrides LinearLinkedBase.deleteAt
- Defined in data-structures/linked-list/doubly-linked-list.ts:580

every

every(predicate, thisArg?): boolean
Tests whether all elements satisfy the predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Function invoked for each element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns boolean
true if every element passes; otherwise false.

Remarks
Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).
Inherited from LinearLinkedBase.every
- Defined in data-structures/base/iterable-element-base.ts:86

fill

fill(value, start?, end?): this
Fill a range with a value.
Parameters
- value: E
  Value to set.
- start: number = 0
  Inclusive start.
- end: number = ...
  Exclusive end.
Returns this
This list.

Remarks
Time O(n), Space O(1)
Inherited from LinearLinkedBase.fill
- Defined in data-structures/base/linear-base.ts:300

filter

filter(callback, thisArg?): this
Filter values into a new list of the same class.
Parameters
- callback: ElementCallback<E, R, boolean>
  Predicate (value, index, list) → boolean to keep value.
- OptionalthisArg: any
  Value for this inside the callback.
Returns this
A new list with kept values.

Remarks
Time O(N), Space O(N)
Overrides LinearLinkedBase.filter
- Defined in data-structures/linked-list/doubly-linked-list.ts:726

find

find<S>(predicate, thisArg?): undefined | S
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
Parameters
- predicate: ElementCallback<E, R, S>
  Type-guard predicate: (value, index, self) => value is S.
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns undefined | S
The matched element typed as S, or undefined if not found.

Remarks
Time O(n) in the worst case; may exit early on the first match. Space O(1).
Inherited from LinearLinkedBase.find
- Defined in data-structures/base/iterable-element-base.ts:162

findIndex

findIndex(predicate, thisArg?): number
Find the first index matching a predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  (element, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns number
Index or -1.

Remarks
Time O(n), Space O(1)
Inherited from LinearLinkedBase.findIndex
- Defined in data-structures/base/linear-base.ts:151

forEach

forEach(callbackfn, thisArg?): void
Invokes a callback for each element in iteration order.
Parameters
- callbackfn: ElementCallback<E, R, void>
  Function invoked per element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the callback.
Returns void
void.

Remarks
Time O(n), Space O(1).
Inherited from LinearLinkedBase.forEach
- Defined in data-structures/base/iterable-element-base.ts:132

getBackward

getBackward(elementNodeOrPredicate): undefined | E
Find the first value matching a predicate scanning backward.
Parameters
- elementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)
  Element, node, or predicate to match.
Returns undefined | E
Matched value or undefined.

Remarks
Time O(N), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:665

getNode

getNode(elementNodeOrPredicate?): undefined | DoublyLinkedListNode<E>
Find a node by value, reference, or predicate.
Parameters
- OptionalelementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)
  Element, node, or predicate to match.
Returns undefined | DoublyLinkedListNode<E>
Matching node or undefined.

Remarks
Time O(N), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:451

getNodeAt

getNodeAt(index): undefined | DoublyLinkedListNode<E>
Get the node reference at a given index.
Parameters
- index: number
  Zero-based index.
Returns undefined | DoublyLinkedListNode<E>
Node or undefined.

Remarks
Time O(N), Space O(1)
Overrides LinearLinkedBase.getNodeAt
- Defined in data-structures/linked-list/doubly-linked-list.ts:437

has

has(element): boolean
Checks whether a strictly-equal element exists in the structure.
Parameters
- element: E
  The element to test with === equality.
Returns boolean
true if an equal element is found; otherwise false.

Remarks
Time O(n) in the worst case. Space O(1).
Inherited from LinearLinkedBase.has
- Defined in data-structures/base/iterable-element-base.ts:188

indexOf

indexOf(searchElement, fromIndex?): number
Linked-list optimized indexOf (forwards scan).
Parameters
- searchElement: E
  Value to match.
- fromIndex: number = 0
  Start position.
Returns number
Index or -1.

Remarks
Time O(n), Space O(1)
Inherited from LinearLinkedBase.indexOf
- Defined in data-structures/base/linear-base.ts:430

isEmpty

isEmpty(): boolean
Check whether the list is empty.

Returns boolean
True if length is 0.

Remarks
Time O(1), Space O(1)
Overrides LinearLinkedBase.isEmpty
- Defined in data-structures/linked-list/doubly-linked-list.ts:623

isNode

isNode(elementNodeOrPredicate): elementNodeOrPredicate is DoublyLinkedListNode<E>
Type guard: check whether the input is a DoublyLinkedListNode.
Parameters
- elementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)
  Element, node, or predicate.
Returns elementNodeOrPredicate is DoublyLinkedListNode<E>
True if the value is a DoublyLinkedListNode.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:294

join

join(separator?): string
Join all elements into a string.
Parameters
- separator: string = ','
  Separator string.
Returns string
Concatenated string.

Remarks
Time O(n), Space O(n)
Inherited from LinearLinkedBase.join
- Defined in data-structures/base/linear-base.ts:236

lastIndexOf

lastIndexOf(searchElement, fromIndex?): number
Linked-list optimized lastIndexOf (reverse scan).
Parameters
- searchElement: E
  Value to match.
- fromIndex: number = ...
  Start position.
Returns number
Index or -1.

Remarks
Time O(n), Space O(1)
Inherited from LinearLinkedBase.lastIndexOf
- Defined in data-structures/base/linear-base.ts:456

map

map<EM, RM>(callback, options?, thisArg?): DoublyLinkedList<EM, RM>
Map values into a new list (possibly different element type).
Type Parameters
- EM
- RM
Parameters
- callback: ElementCallback<E, R, EM>
  Mapping function (value, index, list) → newElement.
- Optionaloptions: DoublyLinkedListOptions<EM, RM>
  Options for the output list (e.g., maxLen, toElementFn).
- OptionalthisArg: any
  Value for this inside the callback.
Returns DoublyLinkedList<EM, RM>
A new DoublyLinkedList with mapped values.

Remarks
Time O(N), Space O(N)
Overrides LinearLinkedBase.map
- Defined in data-structures/linked-list/doubly-linked-list.ts:762

mapSame

mapSame(callback, thisArg?): this
Map values into a new list of the same class.
Parameters
- callback: ElementCallback<E, R, E>
  Mapping function (value, index, list) → newValue.
- OptionalthisArg: any
  Value for this inside the callback.
Returns this
A new list with mapped values.

Remarks
Time O(N), Space O(N)
Overrides LinearLinkedBase.mapSame
- Defined in data-structures/linked-list/doubly-linked-list.ts:741

pop

pop(): undefined | E
Remove and return the tail element.

Returns undefined | E
Removed element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:328

print

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

Returns void
void.

Remarks
Time O(n) due to materialization, Space O(n) for the intermediate representation.
Inherited from LinearLinkedBase.print
- Defined in data-structures/base/iterable-element-base.ts:268

push

push(elementOrNode): boolean
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)
Overrides LinearLinkedBase.push
- Defined in data-structures/linked-list/doubly-linked-list.ts:307

pushMany

pushMany(elements): boolean[]
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 LinearLinkedBase.pushMany
- Defined in data-structures/linked-list/doubly-linked-list.ts:391

reduce

reduce(callbackfn): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
Returns E
Inherited from LinearLinkedBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:193
reduce(callbackfn, initialValue): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
- initialValue: E
Returns E
Inherited from LinearLinkedBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:194
reduce<U>(callbackfn, initialValue): U
Type Parameters
- U
Parameters
- callbackfn: ReduceElementCallback<E, R, U>
- initialValue: U
Returns U
Inherited from LinearLinkedBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:195

reduceRight

reduceRight<U>(callbackfn, initialValue): U
Right-to-left reduction using reverse iterator.
Type Parameters
- U
Parameters
- callbackfn: ReduceLinearCallback<E, U>
  (acc, element, index, self) => acc.
- initialValue: U
  Initial accumulator.
Returns U
Final accumulator.

Remarks
Time O(n), Space O(1)
Inherited from LinearLinkedBase.reduceRight
- Defined in data-structures/base/linear-base.ts:584

reverse

reverse(): this
Reverse the list in place.

Returns this
This list.

Remarks
Time O(N), Space O(1)
Overrides LinearLinkedBase.reverse
- Defined in data-structures/linked-list/doubly-linked-list.ts:683

search

search(elementNodeOrPredicate): undefined | E
Find the first value matching a predicate scanning forward.
Parameters
- elementNodeOrPredicate: E | DoublyLinkedListNode<E> | ((node: DoublyLinkedListNode<E>) => boolean)
  Element, node, or predicate to match.
Returns undefined | E
Matched value or undefined.

Remarks
Time O(N), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:646

setAt

setAt(index, value): boolean
Set the element value at an index.
Parameters
- index: number
  Zero-based index.
- value: E
  New value.
Returns boolean
True if updated.

Remarks
Time O(N), Space O(1)
Overrides LinearLinkedBase.setAt
- Defined in data-structures/linked-list/doubly-linked-list.ts:566

setEquality

setEquality(equals): this
Set the equality comparator used to compare values.
Parameters
- equals: ((a: E, b: E) => boolean)
  Equality predicate (a, b) → boolean.
  - - (a, b): boolean
    - Parameters
      a: E
      b: E
      Returns boolean
Returns this
This list.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:701

shift

shift(): undefined | E
Remove and return the head element.

Returns undefined | E
Removed element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/linked-list/doubly-linked-list.ts:348

slice

slice(start?, end?): this
Slice via forward iteration (no random access required).
Parameters
- start: number = 0
  Inclusive start (supports negative index).
- end: number = ...
  Exclusive end (supports negative index).
Returns this
New list (this type).

Remarks
Time O(n), Space O(n)
Inherited from LinearLinkedBase.slice
- Defined in data-structures/base/linear-base.ts:504

some

some(predicate, thisArg?): boolean
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).
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns boolean
true if any element passes; otherwise false.

Remarks
Time O(n) in the worst case; may exit early on first success. Space O(1).
Inherited from LinearLinkedBase.some
- Defined in data-structures/base/iterable-element-base.ts:109

sort

sort(compareFn?): this
In-place stable order via array sort semantics.
Parameters
- OptionalcompareFn: ((a: E, b: E) => number)
  Comparator (a, b) => number.
  - - (a, b): number
    - Parameters
      a: E
      b: E
      Returns number
Returns this
This container.

Remarks
Time O(n log n), Space O(n) (materializes to array temporarily)
Inherited from LinearLinkedBase.sort
- Defined in data-structures/base/linear-base.ts:193

splice

splice(start, deleteCount?, ...items): this
Splice by walking node iterators from the start index.
Parameters
- start: number
  Start index.
- deleteCount: number = 0
  How many elements to remove.
- Rest...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 LinearLinkedBase.splice
- Defined in data-structures/base/linear-base.ts:532

toArray

toArray(): E[]
Materializes the elements into a new array.

Returns E[]
A shallow array copy of the iteration order.

Remarks
Time O(n), Space O(n).
Inherited from LinearLinkedBase.toArray
- Defined in data-structures/base/iterable-element-base.ts:245

toReversedArray

toReversedArray(): E[]
Snapshot elements into a reversed array.

Returns E[]
New reversed array.

Remarks
Time O(n), Space O(n)
Inherited from LinearLinkedBase.toReversedArray
- Defined in data-structures/base/linear-base.ts:245

toVisual

toVisual(): E[]
Returns a representation of the structure suitable for quick visualization. Defaults to an array of elements; subclasses may override to provide richer visuals.

Returns E[]
A visual representation (array by default).

Remarks
Time O(n), Space O(n).
Inherited from LinearLinkedBase.toVisual
- Defined in data-structures/base/iterable-element-base.ts:257

unshift

unshift(elementOrNode): boolean
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)
- Defined in data-structures/linked-list/doubly-linked-list.ts:369

unshiftMany

unshiftMany(elements): boolean[]
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)
- Defined in data-structures/linked-list/doubly-linked-list.ts:407

values

values(): IterableIterator<E, any, any>
Returns an iterator over the values (alias of the default iterator).

Returns IterableIterator<E, any, any>
An IterableIterator<E> over all elements.

Remarks
Creating the iterator is O(1); full iteration is Time O(n), Space O(1).
Inherited from LinearLinkedBase.values
- Defined in data-structures/base/iterable-element-base.ts:71

`Static`fromArray

fromArray<E, R>(this, data): any
Create a new list from an array of elements.
Type Parameters
- E
- 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)
- Defined in data-structures/linked-list/doubly-linked-list.ts:277

Class DoublyLinkedList<E, R>

Remarks

Example

Example

Example

Example

Example

Type Parameters

Hierarchy

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns DoublyLinkedList<E, R>

Remarks

Properties

Protected Optional_toElementFn

Remarks

Accessors

first

Returns undefined | E

Remarks

head

Returns undefined | DoublyLinkedListNode<E>

Remarks

last

Returns undefined | E

Remarks

length

Returns number

Remarks

maxLen

Returns number

Remarks

tail

Returns undefined | DoublyLinkedListNode<E>

Remarks

toElementFn

Returns undefined | ((rawElement: R) => E)

Remarks

Methods

Protected_createInstance

Parameters

Returns this

Remarks

Protected_createLike

Type Parameters

Parameters

Returns DoublyLinkedList<EM, RM>

Remarks

Protected_ensureNode

Parameters

Returns DoublyLinkedListNode<E>

Remarks

Protected_ensurePredicate

Parameters

Returns ((node: DoublyLinkedListNode<E>) => boolean)

Parameters

Returns boolean

Remarks

Protected_getIterator

Returns IterableIterator<E, any, any>

Remarks

Protected_getNodeIterator

Returns IterableIterator<DoublyLinkedListNode<E>, any, any>

Remarks

Protected_getPrevNode

Parameters

Returns undefined | DoublyLinkedListNode<E>

Remarks

Protected_getReverseIterator

Returns IterableIterator<E, any, any>

Remarks

[iterator]

Parameters

`Protected` `Optional`_toElementFn

`Protected`_createInstance

`Protected`_createLike

`Protected`_ensureNode

`Protected`_ensurePredicate

`Protected`_getIterator

`Protected`_getNodeIterator

`Protected`_getPrevNode

`Protected`_getReverseIterator