Class DoubleLinkedList<ItemT>

A high-performance, type-safe doubly linked list implementation for TypeScript.

Features:

Full TypeScript generic support with type safety
Bidirectional traversal and insertion
Iterator protocol support (for...of, spread operator, Array.from)
Array-like methods (forEach, map, find, includes, indexOf)
Stack/Queue operations (push, pop, shift, unshift)
O(1) insertion/deletion at any position when you have the node reference
Memory-efficient with automatic cleanup
Zero dependencies

Example: Basic usage

const list = new DoubleLinkedList<number>(1, 2, 3);
const node = list.append(4);
console.log([...list]); // [1, 2, 3, 4]

Example: Iterator support

const list = new DoubleLinkedList('a', 'b', 'c');
for (const item of list) {
  console.log(item); // 'a', 'b', 'c'
}

Example: Stack operations

const stack = new DoubleLinkedList<number>();
stack.push(1); stack.push(2);
console.log(stack.pop()); // 2

Type Parameters

ItemT
The type of items stored in the list

Index

Constructors

constructor

Methods

[iterator] append clear find forEach get getHead getLength getNodeAt getTail includes indexOf insertAfterNode insertBeforeNode isEmpty map pop prepend push remove shift splice toArray unshift

Constructors

constructor

new DoubleLinkedList<ItemT>(...items: ItemT[]): DoubleLinkedList<ItemT>
Creates a new DoubleLinkedList with optional initial items.
Type Parameters
- ItemT
Parameters
- ...items: ItemT[]
  Initial items to add to the list (added in order)
Returns DoubleLinkedList<ItemT>
Example
```
const list = new DoubleLinkedList<number>();        // Empty list
const list2 = new DoubleLinkedList(1, 2, 3);       // [1, 2, 3]
const list3 = new DoubleLinkedList<string>('a');    // ['a']
```

Methods

[iterator]

"[iterator]"(): Iterator<ItemT>
Makes the list iterable, enabling use with for...of loops, spread operator, Array.from(), etc.

Returns Iterator<ItemT>
An iterator that yields each item in the list from head to tail
Remarks
Time complexity: O(1) per iteration, O(n) for complete iteration
Example: Iterator usage
```
const list = new DoubleLinkedList('a', 'b', 'c');

// for...of loop
for (const item of list) {
  console.log(item); // 'a', 'b', 'c'
}

// Spread operator
const array = [...list]; // ['a', 'b', 'c']

// Array.from()
const array2 = Array.from(list); // ['a', 'b', 'c']
```

append

append(item: ItemT): DoubleLinkedListNode<ItemT>
Adds an item to the end of the list.
Parameters
- item: ItemT
  The item to add
Returns DoubleLinkedListNode<ItemT>
A readonly reference to the newly created node
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList<string>();
const node = list.append('hello');
console.log(node.value); // 'hello'
```

clear

clear(): void
Removes all items from the list, making it empty. Properly cleans up all node references to prevent memory leaks.

Returns void
Remarks
Time complexity: O(n) where n is the number of items
Example
```
const list = new DoubleLinkedList(1, 2, 3);
list.clear();
console.log(list.isEmpty()); // true
```

find

find(
    predicate: (
        value: ItemT,
        index: number,
        list: DoubleLinkedList<ItemT>,
    ) => boolean,
): undefined | ItemT
Returns the first item in the list that satisfies the provided testing function. Similar to Array.prototype.find().
Parameters
- predicate: (value: ItemT, index: number, list: DoubleLinkedList<ItemT>) => boolean
  Function to test each item. Receives (value, index, list) as parameters.
Returns undefined | ItemT
The first item that matches the predicate, or undefined if no match is found
Remarks
Time complexity: O(n) in worst case, O(k) where k is the position of the found item
Example
```
const list = new DoubleLinkedList(1, 2, 3, 4, 5);
const found = list.find(x => x > 3);
console.log(found); // 4

const notFound = list.find(x => x > 10);
console.log(notFound); // undefined
```

forEach

forEach(
    callback: (
        value: ItemT,
        index: number,
        list: DoubleLinkedList<ItemT>,
    ) => void,
): void
Executes a provided function once for each item in the list. Similar to Array.prototype.forEach().
Parameters
- callback: (value: ItemT, index: number, list: DoubleLinkedList<ItemT>) => void
  Function to execute for each item. Receives (value, index, list) as parameters.
Returns void
Remarks
Time complexity: O(n)
Example
```
const list = new DoubleLinkedList('a', 'b', 'c');
list.forEach((value, index) => {
  console.log(`${index}: ${value}`); // "0: a", "1: b", "2: c"
});
```

get

get(index: number): undefined | ItemT
Gets the item at the specified index (array-like access). Supports negative indices to access from the end.
Parameters
- index: number
  The zero-based index of the item to retrieve (supports negative indices)
Returns undefined | ItemT
The item at the specified index, or undefined if index is out of bounds
Remarks
Time complexity: O(n) where n is the distance to the index
Example: Basic usage
```
const list = new DoubleLinkedList('a', 'b', 'c', 'd');
console.log(list.get(0));  // 'a' (first item)
console.log(list.get(2));  // 'c' (third item)
console.log(list.get(10)); // undefined (out of bounds)
```
Example: Negative indices
```
const list = new DoubleLinkedList(1, 2, 3, 4);
console.log(list.get(-1)); // 4 (last item)
console.log(list.get(-2)); // 3 (second to last)
console.log(list.get(-10)); // undefined (out of bounds)
```

getHead

getHead(): undefined | DoubleLinkedListNode<ItemT>
Gets the first node in the list.

Returns undefined | DoubleLinkedListNode<ItemT>
The first node, or undefined if the list is empty
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList('a', 'b', 'c');
const head = list.getHead();
console.log(head?.value); // 'a'
```

getLength

getLength(): number
Gets the number of items in the list.

Returns number
The number of items in the list
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList(1, 2, 3);
console.log(list.getLength()); // 3
```

getNodeAt

getNodeAt(index: number): undefined | DoubleLinkedListNode<ItemT>
Gets the node at the specified index. Supports negative indices to access from the end.
Parameters
- index: number
  The zero-based index of the node to retrieve (supports negative indices)
Returns undefined | DoubleLinkedListNode<ItemT>
The node at the specified index, or undefined if index is out of bounds
Remarks
Time complexity: O(n) where n is the distance to the index
Example
```
const list = new DoubleLinkedList('a', 'b', 'c');
const node = list.getNodeAt(1);
console.log(node?.value); // 'b'
```

getTail

getTail(): undefined | DoubleLinkedListNode<ItemT>
Gets the last node in the list.

Returns undefined | DoubleLinkedListNode<ItemT>
The last node, or undefined if the list is empty
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList('a', 'b', 'c');
const tail = list.getTail();
console.log(tail?.value); // 'c'
```

includes

includes(searchElement: ItemT, fromIndex?: number): boolean
Determines whether the list includes a certain item. Similar to Array.prototype.includes().
Parameters
- searchElement: ItemT
  The item to search for
- fromIndex: number = 0
  The index to start the search from (default: 0)
Returns boolean
true if the item is found, false otherwise
Remarks
Time complexity: O(n) in worst case, O(k) where k is the position of the found item
Example
```
const list = new DoubleLinkedList(1, 2, 3);
console.log(list.includes(2));    // true
console.log(list.includes(4));    // false
console.log(list.includes(1, 1)); // false (starting from index 1)
```

indexOf

indexOf(searchElement: ItemT, fromIndex?: number): number
Returns the first index at which a given item can be found in the list. Similar to Array.prototype.indexOf().
Parameters
- searchElement: ItemT
  The item to search for
- fromIndex: number = 0
  The index to start the search from (default: 0)
Returns number
The index of the first occurrence of the item, or -1 if not found
Remarks
Time complexity: O(n) in worst case, O(k) where k is the position of the found item
Example
```
const list = new DoubleLinkedList('a', 'b', 'c', 'b');
console.log(list.indexOf('b'));    // 1 (first occurrence)
console.log(list.indexOf('b', 2)); // 3 (starting from index 2)
console.log(list.indexOf('z'));    // -1 (not found)
```

insertAfterNode

insertAfterNode(
node: DoubleLinkedListNode<ItemT>,
item: ItemT,
): undefined | DoubleLinkedListNode<ItemT>
Inserts a new item immediately after the specified node.
Parameters
- node: DoubleLinkedListNode<ItemT>
  The node after which to insert the new item
- item: ItemT
  The item to insert
Returns undefined | DoubleLinkedListNode<ItemT>
The newly created node, or undefined if the reference node doesn't belong to this list
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList(1, 3);
const firstNode = list.getHead();
if (firstNode) {
  list.insertAfterNode(firstNode, 2);
  console.log([...list]); // [1, 2, 3]
}
```

insertBeforeNode

insertBeforeNode(
node: DoubleLinkedListNode<ItemT>,
item: ItemT,
): undefined | DoubleLinkedListNode<ItemT>
Inserts a new item immediately before the specified node.
Parameters
- node: DoubleLinkedListNode<ItemT>
  The node before which to insert the new item
- item: ItemT
  The item to insert
Returns undefined | DoubleLinkedListNode<ItemT>
The newly created node, or undefined if the reference node doesn't belong to this list
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList(1, 3);
const lastNode = list.getTail();
if (lastNode) {
  list.insertBeforeNode(lastNode, 2);
  console.log([...list]); // [1, 2, 3]
}
```

isEmpty

isEmpty(): boolean

Checks if the list is empty.

Returns boolean

true if the list has no items, false otherwise

Remarks

Time complexity: O(1)

Example

const list = new DoubleLinkedList<number>();
console.log(list.isEmpty()); // true
list.append(42);
console.log(list.isEmpty()); // false

map

map<U>(
    callback: (
        value: ItemT,
        index: number,
        list: DoubleLinkedList<ItemT>,
    ) => U,
): DoubleLinkedList<U>
Creates a new DoubleLinkedList with the results of calling a provided function on every item. Similar to Array.prototype.map().
Type Parameters
- U
  The type of items in the returned list
Parameters
- callback: (value: ItemT, index: number, list: DoubleLinkedList<ItemT>) => U
  Function that produces an item of the new list. Receives (value, index, list) as parameters.
Returns DoubleLinkedList<U>
A new DoubleLinkedList with the transformed items
Remarks
Time complexity: O(n)
Example
```
const numbers = new DoubleLinkedList(1, 2, 3);
const doubled = numbers.map(x => x * 2);
console.log([...doubled]); // [2, 4, 6]

const strings = numbers.map(x => x.toString());
console.log([...strings]); // ['1', '2', '3']
```

pop

pop(): undefined | ItemT
Removes and returns the last item from the list (stack-like operation).

Returns undefined | ItemT
The last item, or undefined if the list is empty
Remarks
Time complexity: O(1)
Example: Stack usage
```
const stack = new DoubleLinkedList(1, 2, 3);
console.log(stack.pop()); // 3
console.log(stack.pop()); // 2
console.log([...stack]);  // [1]
```

prepend

prepend(item: ItemT): DoubleLinkedListNode<ItemT>
Adds an item to the beginning of the list.
Parameters
- item: ItemT
  The item to add
Returns DoubleLinkedListNode<ItemT>
A readonly reference to the newly created node
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList(2, 3);
const node = list.prepend(1);
console.log([...list]); // [1, 2, 3]
```

push

push(item: ItemT): DoubleLinkedListNode<ItemT>
Adds an item to the end of the list (stack/array-like operation). Alias for append() method.
Parameters
- item: ItemT
  The item to add
Returns DoubleLinkedListNode<ItemT>
A readonly reference to the newly created node
Remarks
Time complexity: O(1)
Example: Stack usage
```
const stack = new DoubleLinkedList<number>();
stack.push(1);
stack.push(2);
console.log(stack.pop()); // 2 (LIFO)
```

remove

remove(node: DoubleLinkedListNode<ItemT>): boolean
Removes a specific node from the list. Safely handles removal of head, tail, or middle nodes.
Parameters
- node: DoubleLinkedListNode<ItemT>
  The node to remove
Returns boolean
true if the node was removed, false if it doesn't belong to this list
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList(1, 2, 3);
const node = list.getHead();
if (node) {
  const removed = list.remove(node);
  console.log(removed); // true
  console.log([...list]); // [2, 3]
}
```

shift

shift(): undefined | ItemT
Removes and returns the first item from the list (queue-like operation).

Returns undefined | ItemT
The first item, or undefined if the list is empty
Remarks
Time complexity: O(1)
Example: Queue usage
```
const queue = new DoubleLinkedList(1, 2, 3);
queue.push(4); // Add to end
console.log(queue.shift()); // 1 (remove from start - FIFO)
console.log([...queue]);    // [2, 3, 4]
```

splice

splice(
    start: undefined | number | DoubleLinkedListNode<ItemT>,
    deleteCount?: number,
    ...items: ItemT[],
): DoubleLinkedList<ItemT>
Changes the contents of the list by removing existing items and/or adding new items. Similar to Array.prototype.splice() but with enhanced node-based operations.
Parameters
- start: undefined | number | DoubleLinkedListNode<ItemT>
  Zero-based index, DoubleLinkedListNode, or undefined to specify where to start changing the list. - number: Zero-based index (supports negative indices) - DoubleLinkedListNode: Start at the position of this node (O(1) lookup) - undefined: Start at the end of the list (equivalent to list.length)
- deleteCount: number = 0
  Number of items to remove from the list (default: 0)
- ...items: ItemT[]
  Items to add to the list, beginning from the start position
Returns DoubleLinkedList<ItemT>
A new DoubleLinkedList containing the deleted items
Remarks
Time complexity: O(n) for index-based, O(1) for node-based start position
Example: Remove items by index
```
const list = new DoubleLinkedList('a', 'b', 'c', 'd');
const removed = list.splice(1, 2); // Remove 2 items starting at index 1
console.log([...list]); // ['a', 'd']
console.log([...removed]); // ['b', 'c']
```
Example: Add items by node reference (O(1) performance)
```
const list = new DoubleLinkedList('a', 'd');
const nodeA = list.getHead();
if (nodeA) {
  list.splice(nodeA.nextNode, 0, 'b', 'c'); // Insert at node position
  console.log([...list]); // ['a', 'b', 'c', 'd']
}
```
Example: Replace items using node reference
```
const list = new DoubleLinkedList(1, 2, 3, 4);
const secondNode = list.getHead()?.nextNode;
if (secondNode) {
  const removed = list.splice(secondNode, 2, 10, 20);
  console.log([...list]); // [1, 10, 20, 4]
  console.log([...removed]); // [2, 3]
}
```
Example: Append to end using undefined
```
const list = new DoubleLinkedList('a', 'b');
list.splice(undefined, 0, 'c', 'd'); // Append to end
console.log([...list]); // ['a', 'b', 'c', 'd']
```
Example: Negative start index
```
const list = new DoubleLinkedList('a', 'b', 'c', 'd');
list.splice(-2, 1, 'x'); // Remove 1 item from 2nd to last position, add 'x'
console.log([...list]); // ['a', 'b', 'x', 'd']
```

toArray

toArray(): readonly ItemT[]
Converts the list to a readonly array. Uses internal caching for performance - the array is only rebuilt when the list is modified.

Returns readonly ItemT[]
A readonly array containing all items in the list
Remarks
Time complexity: O(n)
Example
```
const list = new DoubleLinkedList('x', 'y', 'z');
const array = list.toArray();
console.log(array); // ['x', 'y', 'z'] (readonly)
```

unshift

unshift(item: ItemT): DoubleLinkedListNode<ItemT>
Adds an item to the beginning of the list (array-like operation). Alias for prepend() method.
Parameters
- item: ItemT
  The item to add
Returns DoubleLinkedListNode<ItemT>
A readonly reference to the newly created node
Remarks
Time complexity: O(1)
Example
```
const list = new DoubleLinkedList(2, 3);
list.unshift(1);
console.log([...list]); // [1, 2, 3]
```

Class DoubleLinkedList<ItemT>

Example: Basic usage

Example: Iterator support

Example: Stack operations

Type Parameters

Index

Constructors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns DoubleLinkedList<ItemT>

Example

Methods

[iterator]

Returns Iterator<ItemT>

Remarks

Example: Iterator usage

append

Parameters

Returns DoubleLinkedListNode<ItemT>

Remarks

Example

clear

Returns void

Remarks

Example

find

Parameters

Returns undefined | ItemT

Remarks

Example

forEach

Parameters

Returns void

Remarks

Example

get

Parameters

Returns undefined | ItemT

Remarks

Example: Basic usage

Example: Negative indices

getHead

Returns undefined | DoubleLinkedListNode<ItemT>

Remarks

Example

getLength

Returns number

Remarks

Example

getNodeAt

Parameters

Returns undefined | DoubleLinkedListNode<ItemT>

Remarks

Example

getTail

Returns undefined | DoubleLinkedListNode<ItemT>

Remarks

Example

includes

Parameters

Returns boolean

Remarks

Example

indexOf

Parameters

Returns number

Remarks

Example

insertAfterNode

Parameters

Returns undefined | DoubleLinkedListNode<ItemT>

Remarks

Example

insertBeforeNode

Parameters

Returns undefined | DoubleLinkedListNode<ItemT>

Remarks