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

// text editor operation history
    const actions = [
      { type: 'insert', content: 'first line of text' },
      { type: 'insert', content: 'second line of text' },
      { type: 'delete', content: 'delete the first line' }
    ];
    const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions);

    console.log(editorHistory.last?.type); // 'delete'
    console.log(editorHistory.pop()?.content); // 'delete the first line'
    console.log(editorHistory.last?.type); // 'insert'

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

// Use DoublyLinkedList to implement music player
    // Define the Song interface
    interface Song {
      title: string;
      artist: string;
      duration: number; // duration in seconds
    }

    class Player {
      private playlist: DoublyLinkedList<Song>;
      private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined;

      constructor(songs: Song[]) {
        this.playlist = new DoublyLinkedList<Song>();
        songs.forEach(song => this.playlist.push(song));
        this.currentSong = this.playlist.head;
      }

      // Play the next song in the playlist
      playNext(): Song | undefined {
        if (!this.currentSong?.next) {
          this.currentSong = this.playlist.head; // Loop to the first song
        } else {
          this.currentSong = this.currentSong.next;
        }
        return this.currentSong?.value;
      }

      // Play the previous song in the playlist
      playPrevious(): Song | undefined {
        if (!this.currentSong?.prev) {
          this.currentSong = this.playlist.tail; // Loop to the last song
        } else {
          this.currentSong = this.currentSong.prev;
        }
        return this.currentSong?.value;
      }

      // Get the current song
      getCurrentSong(): Song | undefined {
        return this.currentSong?.value;
      }

      // Loop through the playlist twice
      loopThroughPlaylist(): Song[] {
        const playedSongs: Song[] = [];
        const initialNode = this.currentSong;

        // Loop through the playlist twice
        for (let i = 0; i < this.playlist.length * 2; i++) {
          playedSongs.push(this.currentSong!.value);
          this.currentSong = this.currentSong!.next || this.playlist.head; // Loop back to the start if needed
        }

        // Reset the current song to the initial song
        this.currentSong = initialNode;
        return playedSongs;
      }
    }

    const songs = [
      { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 },
      { title: 'Hotel California', artist: 'Eagles', duration: 391 },
      { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 },
      { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }
    ];
    let player = new Player(songs);
    // should play the next song
    player = new Player(songs);
    const firstSong = player.getCurrentSong();
    const nextSong = player.playNext();

    // Expect the next song to be "Hotel California by Eagles"
    console.log(nextSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 }
    console.log(firstSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }

    // should play the previous song
    player = new Player(songs);
    player.playNext(); // Move to the second song
    const currentSong = player.getCurrentSong();
    const previousSong = player.playPrevious();

    // Expect the previous song to be "Bohemian Rhapsody by Queen"
    console.log(previousSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }
    console.log(currentSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 }

    // should loop to the first song when playing next from the last song
    player = new Player(songs);
    player.playNext(); // Move to the second song
    player.playNext(); // Move to the third song
    player.playNext(); // Move to the fourth song

    const nextSongToFirst = player.playNext(); // Should loop to the first song

    // Expect the next song to be "Bohemian Rhapsody by Queen"
    console.log(nextSongToFirst); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }

    // should loop to the last song when playing previous from the first song
    player = new Player(songs);
    player.playNext(); // Move to the first song
    player.playNext(); // Move to the second song
    player.playNext(); // Move to the third song
    player.playNext(); // Move to the fourth song

    const previousToLast = player.playPrevious(); // Should loop to the last song

    // Expect the previous song to be "Billie Jean by Michael Jackson"
    console.log(previousToLast); // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }

    // should loop through the entire playlist
    player = new Player(songs);
    const playedSongs = player.loopThroughPlaylist();

    // The expected order of songs for two loops
    console.log(playedSongs); // [
 //      { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 },
 //      { title: 'Hotel California', artist: 'Eagles', duration: 391 },
 //      { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 },
 //      { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 },
 //      { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 },
 //      { title: 'Hotel California', artist: 'Eagles', duration: 391 },
 //      { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 },
 //      { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }
 //    ]

Example

// Use DoublyLinkedList to implement LRU cache
    interface CacheEntry<K, V> {
      key: K;
      value: V;
    }

    class LRUCache<K = string, V = any> {
      private readonly capacity: number;
      private list: DoublyLinkedList<CacheEntry<K, V>>;
      private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>;

      constructor(capacity: number) {
        if (capacity <= 0) {
          throw new Error('lru cache capacity must be greater than 0');
        }
        this.capacity = capacity;
        this.list = new DoublyLinkedList<CacheEntry<K, V>>();
        this.map = new Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>();
      }

      // Get the current cache length
      get length(): number {
        return this.list.length;
      }

      // Check if it is empty
      get isEmpty(): boolean {
        return this.list.isEmpty();
      }

      // Get cached value
      get(key: K): V | undefined {
        const node = this.map.get(key);

        if (!node) return undefined;

        // Move the visited node to the head of the linked list (most recently used)
        this.moveToFront(node);

        return node.value.value;
      }

      // Set cache value
      set(key: K, value: V): void {
        // Check if it already exists
        const node = this.map.get(key);

        if (node) {
          // Update value and move to head
          node.value.value = value;
          this.moveToFront(node);
          return;
        }

        // Check capacity
        if (this.list.length >= this.capacity) {
          // Delete the least recently used element (the tail of the linked list)
          const removedNode = this.list.tail;
          if (removedNode) {
            this.map.delete(removedNode.value.key);
            this.list.pop();
          }
        }

        // Create new node and add to head
        const newEntry: CacheEntry<K, V> = { key, value };
        this.list.unshift(newEntry);

        // Save node reference in map
        const newNode = this.list.head;
        if (newNode) {
          this.map.set(key, newNode);
        }
      }

      // Delete specific key
      delete(key: K): boolean {
        const node = this.map.get(key);
        if (!node) return false;

        // Remove from linked list
        this.list.delete(node);
        // Remove from map
        this.map.delete(key);

        return true;
      }

      // Clear cache
      clear(): void {
        this.list.clear();
        this.map.clear();
      }

      // Move the node to the head of the linked list
      private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void {
        this.list.delete(node);
        this.list.unshift(node.value);
      }
    }

    // should set and get values correctly
    const cache = new LRUCache<string, number>(3);
    cache.set('a', 1);
    cache.set('b', 2);
    cache.set('c', 3);

    console.log(cache.get('a')); // 1
    console.log(cache.get('b')); // 2
    console.log(cache.get('c')); // 3

    // The least recently used element should be evicted when capacity is exceeded
    cache.clear();
    cache.set('a', 1);
    cache.set('b', 2);
    cache.set('c', 3);
    cache.set('d', 4); // This will eliminate 'a'

    console.log(cache.get('a')); // undefined
    console.log(cache.get('b')); // 2
    console.log(cache.get('c')); // 3
    console.log(cache.get('d')); // 4

    // The priority of an element should be updated when it is accessed
    cache.clear();
    cache.set('a', 1);
    cache.set('b', 2);
    cache.set('c', 3);

    cache.get('a'); // access 'a'
    cache.set('d', 4); // This will eliminate 'b'

    console.log(cache.get('a')); // 1
    console.log(cache.get('b')); // undefined
    console.log(cache.get('c')); // 3
    console.log(cache.get('d')); // 4

    // Should support updating existing keys
    cache.clear();
    cache.set('a', 1);
    cache.set('a', 10);

    console.log(cache.get('a')); // 10

    // Should support deleting specified keys
    cache.clear();
    cache.set('a', 1);
    cache.set('b', 2);

    console.log(cache.delete('a')); // true
    console.log(cache.get('a')); // undefined
    console.log(cache.length); // 1

    // Should support clearing cache
    cache.clear();
    cache.set('a', 1);
    cache.set('b', 2);
    cache.clear();

    console.log(cache.length); // 0
    console.log(cache.isEmpty); // true

Example

// finding lyrics by timestamp in Coldplay's "Fix You"
    // Create a DoublyLinkedList to store song lyrics with timestamps
    const lyricsList = new DoublyLinkedList<{ time: number; text: string }>();

    // Detailed lyrics with precise timestamps (in milliseconds)
    const lyrics = [
      { time: 0, text: "When you try your best, but you don't succeed" },
      { time: 4000, text: 'When you get what you want, but not what you need' },
      { time: 8000, text: "When you feel so tired, but you can't sleep" },
      { time: 12000, text: 'Stuck in reverse' },
      { time: 16000, text: 'And the tears come streaming down your face' },
      { time: 20000, text: "When you lose something you can't replace" },
      { time: 24000, text: 'When you love someone, but it goes to waste' },
      { time: 28000, text: 'Could it be worse?' },
      { time: 32000, text: 'Lights will guide you home' },
      { time: 36000, text: 'And ignite your bones' },
      { time: 40000, text: 'And I will try to fix you' }
    ];

    // Populate the DoublyLinkedList with lyrics
    lyrics.forEach(lyric => lyricsList.push(lyric));

    // Test different scenarios of lyric synchronization

    // 1. Find lyric at exact timestamp
    const exactTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= 36000);
    console.log(exactTimeLyric?.text); // 'And ignite your bones'

    // 2. Find lyric between timestamps
    const betweenTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= 22000);
    console.log(betweenTimeLyric?.text); // "When you lose something you can't replace"

    // 3. Find first lyric when timestamp is less than first entry
    const earlyTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= -1000);
    console.log(earlyTimeLyric); // undefined

    // 4. Find last lyric when timestamp is after last entry
    const lateTimeLyric = lyricsList.getBackward(lyric => lyric.value.time <= 50000);
    console.log(lateTimeLyric?.text); // 'And I will try to fix you'

Example

// cpu process schedules
    class Process {
      constructor(
        public id: number,
        public priority: number
      ) {}

      execute(): string {
        return `Process ${this.id} executed.`;
      }
    }

    class Scheduler {
      private queue: DoublyLinkedList<Process>;

      constructor() {
        this.queue = new DoublyLinkedList<Process>();
      }

      addProcess(process: Process): void {
        // Insert processes into a queue based on priority, keeping priority in descending order
        let current = this.queue.head;
        while (current && current.value.priority >= process.priority) {
          current = current.next;
        }

        if (!current) {
          this.queue.push(process);
        } else {
          this.queue.addBefore(current, process);
        }
      }

      executeNext(): string | undefined {
        // Execute tasks at the head of the queue in order
        const process = this.queue.shift();
        return process ? process.execute() : undefined;
      }

      listProcesses(): string[] {
        return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`);
      }

      clear(): void {
        this.queue.clear();
      }
    }

    // should add processes based on priority
    let scheduler = new Scheduler();
    scheduler.addProcess(new Process(1, 10));
    scheduler.addProcess(new Process(2, 20));
    scheduler.addProcess(new Process(3, 15));

    console.log(scheduler.listProcesses()); // [
 //      'Process 2 (Priority: 20)',
 //      'Process 3 (Priority: 15)',
 //      'Process 1 (Priority: 10)'
 //    ]

    // should execute the highest priority process
    scheduler = new Scheduler();
    scheduler.addProcess(new Process(1, 10));
    scheduler.addProcess(new Process(2, 20));

    console.log(scheduler.executeNext()); // 'Process 2 executed.'
    console.log(scheduler.listProcesses()); // ['Process 1 (Priority: 10)']

    // should clear all processes
    scheduler = new Scheduler();
    scheduler.addProcess(new Process(1, 10));
    scheduler.addProcess(new Process(2, 20));

    scheduler.clear();
    console.log(scheduler.listProcesses()); // []

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:527

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:585

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:551

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:595

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:575

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:563

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:1156

`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:1174

`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:1112

`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:1124

`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:1185

`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:1201

`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:1145

`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:1193

[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:874

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:823

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:847

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:755

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:965

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:1044

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:933

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:912

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:1058

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:997

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:783

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:769

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:955

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:626

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:1094

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:1073

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:660

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:639

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:723

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:1015

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:978

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:898

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:1033

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:680

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:701

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:739

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:609

Class DoublyLinkedList<E, R>

Remarks

Example

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]

`Protected` `Optional`_toElementFn

`Protected`_createInstance

`Protected`_createLike

`Protected`_ensureNode

`Protected`_ensurePredicate

`Protected`_getIterator

`Protected`_getNodeIterator

`Protected`_getPrevNode

`Protected`_getReverseIterator