A TypeScript implementation of Redis' List data structure

DoubleEndedList.test.ts

import { describe, it, expect, beforeEach } from "vitest";
import { DoubleEndedList, Positions } from "./DoubleEndedList.ts";

describe("DoubleEndedList", () => {
  let list: DoubleEndedList<number>;

  beforeEach(() => {
    list = new DoubleEndedList<number>();
  });

  // Test constructor and initial state
  it("should be empty on initialization", () => {
    expect(list.length()).toBe(0);
    expect(list.lPeek()).toBeUndefined();
    expect(list.rPeek()).toBeUndefined();
  });

  // Test clear method
  it("should clear the list", () => {
    list.lPush(1);
    list.rPush(2);
    expect(list.length()).toBe(2);
    list.clear();
    expect(list.length()).toBe(0);
    expect(list.lPeek()).toBeUndefined();
    expect(list.rPeek()).toBeUndefined();
  });

  // Test length method
  it("should return the correct length", () => {
    expect(list.length()).toBe(0);
    list.lPush(1);
    expect(list.length()).toBe(1);
    list.rPush(2);
    expect(list.length()).toBe(2);
    list.lPop();
    expect(list.length()).toBe(1);
    list.rPop();
    expect(list.length()).toBe(0);
  });

  // Test lPeek and rPeek
  it("should peek at the left and right elements without removing them", () => {
    list.lPush(1);
    list.rPush(2);
    list.lPush(0); // List: [0, 1, 2]

    expect(list.lPeek()).toBe(0);
    expect(list.rPeek()).toBe(2);
    expect(list.length()).toBe(3); // Should not change length
  });

  // Test lPush
  it("should add elements to the front (left) of the list", () => {
    list.lPush(1);
    expect(list.length()).toBe(1);
    expect(list.lPeek()).toBe(1);
    expect(list.rPeek()).toBe(1);

    list.lPush(0); // List: [0, 1]
    expect(list.length()).toBe(2);
    expect(list.lPeek()).toBe(0);
    expect(list.rPeek()).toBe(1);

    list.lPush([3, 4]); // List: [3, 4, 0, 1] (4 becomes the new front after 3 is pushed, then 3)
    expect(list.length()).toBe(4);
    expect(list.lPeek()).toBe(3);
    expect(list.rPeek()).toBe(1);
    expect(list.get(0)).toBe(3);
    expect(list.get(1)).toBe(4);
    expect(list.get(2)).toBe(0);
    expect(list.get(3)).toBe(1);
  });

  // Test rPush
  it("should add elements to the back (right) of the list", () => {
    list.rPush(1);
    expect(list.length()).toBe(1);
    expect(list.lPeek()).toBe(1);
    expect(list.rPeek()).toBe(1);

    list.rPush(2); // List: [1, 2]
    expect(list.length()).toBe(2);
    expect(list.lPeek()).toBe(1);
    expect(list.rPeek()).toBe(2);

    list.rPush([3, 4]); // List: [1, 2, 3, 4]
    expect(list.length()).toBe(4);
    expect(list.lPeek()).toBe(1);
    expect(list.rPeek()).toBe(4);
    expect(list.get(0)).toBe(1);
    expect(list.get(1)).toBe(2);
    expect(list.get(2)).toBe(3);
    expect(list.get(3)).toBe(4);
  });

  // Test lPop
  it("should remove and return the left-most element", () => {
    list.lPush([1, 2, 3]); // List: [1, 2, 3]
    expect(list.lPop()).toBe(1);
    expect(list.length()).toBe(2);
    expect(list.lPeek()).toBe(2);

    expect(list.lPop()).toBe(2);
    expect(list.length()).toBe(1);
    expect(list.lPeek()).toBe(3);

    expect(list.lPop()).toBe(3);
    expect(list.length()).toBe(0);
    expect(list.lPeek()).toBeUndefined();
    expect(list.rPeek()).toBeUndefined(); // Pointers should reset
  });

  // Test rPop
  it("should remove and return the right-most element", () => {
    list.rPush([1, 2, 3]); // List: [1, 2, 3]
    expect(list.rPop()).toBe(3);
    expect(list.length()).toBe(2);
    expect(list.rPeek()).toBe(2);

    expect(list.rPop()).toBe(2);
    expect(list.length()).toBe(1);
    expect(list.rPeek()).toBe(1);

    expect(list.rPop()).toBe(1);
    expect(list.length()).toBe(0);
    expect(list.lPeek()).toBeUndefined();
    expect(list.rPeek()).toBeUndefined(); // Pointers should reset
  });

  // Test get
  it("should get elements by positive index", () => {
    list.rPush([10, 20, 30, 40, 50]); // List: [10, 20, 30, 40, 50]
    expect(list.get(0)).toBe(10);
    expect(list.get(2)).toBe(30);
    expect(list.get(4)).toBe(50);
  });

  it("should get elements by negative index", () => {
    list.rPush([10, 20, 30, 40, 50]); // List: [10, 20, 30, 40, 50]
    expect(list.get(-1)).toBe(50);
    expect(list.get(-3)).toBe(30);
    expect(list.get(-5)).toBe(10);
  });

  it("should return undefined for out-of-bounds indices", () => {
    list.rPush([1, 2, 3]); // List: [1, 2, 3]
    expect(list.get(3)).toBeUndefined();
    expect(list.get(-4)).toBeUndefined();
    expect(list.get(100)).toBeUndefined();
    expect(list.get(-100)).toBeUndefined();
  });

  it("should return undefined when getting from an empty list", () => {
    expect(list.get(0)).toBeUndefined();
    expect(list.get(-1)).toBeUndefined();
  });

  // Test set
  it("should set elements by positive index", () => {
    list.rPush([10, 20, 30]); // List: [10, 20, 30]
    list.set(1, 25);
    expect(list.get(0)).toBe(10);
    expect(list.get(1)).toBe(25);
    expect(list.get(2)).toBe(30);
    expect(list.length()).toBe(3); // Length should not change
  });

  it("should set elements by negative index", () => {
    list.rPush([10, 20, 30]); // List: [10, 20, 30]
    list.set(-1, 35);
    expect(list.get(0)).toBe(10);
    expect(list.get(1)).toBe(20);
    expect(list.get(2)).toBe(35);
  });

  it("should not set elements for out-of-bounds indices", () => {
    list.rPush([1, 2, 3]);
    list.set(3, 4); // Out of bounds
    list.set(-4, 0); // Out of bounds
    expect(list.length()).toBe(3);
    expect(list.get(0)).toBe(1);
    expect(list.get(1)).toBe(2);
    expect(list.get(2)).toBe(3);
  });

  it("should do nothing when setting an empty list", () => {
    list.set(0, 100);
    expect(list.length()).toBe(0);
    expect(list.lPeek()).toBeUndefined();
  });

  // Test insert
  describe("insert", () => {
    beforeEach(() => {
      list.rPush([1, 2, 3, 4]); // Initial list: [1, 2, 3, 4]
    });

    it("should insert BEFORE the pivot", () => {
      list.insert(Positions.BEFORE, 3, 2.5); // List: [1, 2, 2.5, 3, 4]
      expect(list.length()).toBe(5);
      expect(list.get(0)).toBe(1);
      expect(list.get(1)).toBe(2);
      expect(list.get(2)).toBe(2.5);
      expect(list.get(3)).toBe(3);
      expect(list.get(4)).toBe(4);
    });

    it("should insert AFTER the pivot", () => {
      list.insert(Positions.AFTER, 2, 2.5); // List: [1, 2, 2.5, 3, 4]
      expect(list.length()).toBe(5);
      expect(list.get(0)).toBe(1);
      expect(list.get(1)).toBe(2);
      expect(list.get(2)).toBe(2.5);
      expect(list.get(3)).toBe(3);
      expect(list.get(4)).toBe(4);
    });

    it("should handle inserting at the beginning (BEFORE first element)", () => {
      list.insert(Positions.BEFORE, 1, 0.5); // List: [0.5, 1, 2, 3, 4]
      expect(list.length()).toBe(5);
      expect(list.get(0)).toBe(0.5);
      expect(list.get(1)).toBe(1);
    });

    it("should handle inserting at the end (AFTER last element)", () => {
      list.insert(Positions.AFTER, 4, 4.5); // List: [1, 2, 3, 4, 4.5]
      expect(list.length()).toBe(5);
      expect(list.get(3)).toBe(4);
      expect(list.get(4)).toBe(4.5);
    });

    it("should do nothing if pivot is not found", () => {
      list.insert(Positions.BEFORE, 99, 5);
      expect(list.length()).toBe(4);
      expect(list.getRange(0, 3)).toEqual([1, 2, 3, 4]);
    });

    it("should do nothing if list is empty", () => {
      list.clear();
      list.insert(Positions.BEFORE, 1, 100);
      expect(list.length()).toBe(0);
    });

    it("should handle duplicate pivot elements (insert at first occurrence)", () => {
      list.rPush([2, 5]); // List: [1, 2, 3, 4, 2, 5]
      list.insert(Positions.BEFORE, 2, 1.5); // Inserts before the first 2
      expect(list.getRange(0, list.length() - 1)).toEqual([1, 1.5, 2, 3, 4, 2, 5]);
      expect(list.length()).toBe(7);
    });
  });

  // Test remove
  describe("remove", () => {
    beforeEach(() => {
      list.rPush([1, 2, 1, 3, 1, 4]); // Initial list: [1, 2, 1, 3, 1, 4]
    });

    it("should remove all occurrences if count is 0", () => {
      list.remove(0, 1); // Remove all 1s
      expect(list.getRange(0, list.length() - 1)).toEqual([2, 3, 4]);
      expect(list.length()).toBe(3);
    });

    it("should remove positive count from left (front)", () => {
      list.remove(1, 1); // Remove one '1' from left
      expect(list.getRange(0, list.length() - 1)).toEqual([2, 1, 3, 1, 4]);
      expect(list.length()).toBe(5);

      list.remove(2, 1); // Remove two '1's from left
      expect(list.getRange(0, list.length() - 1)).toEqual([2, 3, 4]);
      expect(list.length()).toBe(3);
    });

    it("should remove negative count from right (back)", () => {
      list.remove(-1, 1); // Remove one '1' from right
      expect(list.getRange(0, list.length() - 1)).toEqual([1, 2, 1, 3, 4]);
      expect(list.length()).toBe(5);

      list.remove(-2, 1); // Remove two '1's from right (1 from original last '1' and 1 from middle '1')
      expect(list.getRange(0, list.length() - 1)).toEqual([1, 2, 3, 4]);
      expect(list.length()).toBe(4);
    });

    it("should handle removing elements that don't exist", () => {
      list.remove(1, 99);
      expect(list.getRange(0, list.length() - 1)).toEqual([1, 2, 1, 3, 1, 4]);
      expect(list.length()).toBe(6);
    });

    it("should handle removing more than available occurrences", () => {
      list.remove(10, 1); // Try to remove 10 '1's
      expect(list.getRange(0, list.length() - 1)).toEqual([2, 3, 4]);
      expect(list.length()).toBe(3);
    });

    it("should empty the list if all elements are removed", () => {
      list.remove(0, 1);
      list.remove(0, 2);
      list.remove(0, 3);
      list.remove(0, 4);
      expect(list.length()).toBe(0);
      expect(list.lPeek()).toBeUndefined();
      expect(list.rPeek()).toBeUndefined();
    });

    it("should work correctly with a single element list", () => {
      list.clear();
      list.rPush(5); // List: [5]
      list.remove(1, 5);
      expect(list.length()).toBe(0);
    });

    it("should do nothing if list is empty", () => {
      list.clear();
      list.remove(1, 100);
      expect(list.length()).toBe(0);
    });
  });

  // Test getRange
  describe("getRange", () => {
    beforeEach(() => {
      list.rPush([10, 20, 30, 40, 50, 60]); // Initial list: [10, 20, 30, 40, 50, 60]
    });

    it("should return a full range with positive indices", () => {
      expect(list.getRange(0, 5)).toEqual([10, 20, 30, 40, 50, 60]);
    });

    it("should return a sub-range with positive indices", () => {
      expect(list.getRange(1, 3)).toEqual([20, 30, 40]);
    });

    it("should handle negative start index", () => {
      expect(list.getRange(-3, 5)).toEqual([40, 50, 60]);
    });

    it("should handle negative stop index", () => {
      expect(list.getRange(0, -3)).toEqual([10, 20, 30, 40]);
    });

    it("should handle both negative start and stop indices", () => {
      expect(list.getRange(-4, -2)).toEqual([30, 40, 50]);
    });

    it("should return an empty array if start > stop after adjustment", () => {
      expect(list.getRange(3, 1)).toEqual([]);
      expect(list.getRange(-1, -6)).toEqual([]);
      expect(list.getRange(10, 12)).toEqual([]); // Out of bounds high
      expect(list.getRange(-10, -8)).toEqual([]); // Out of bounds low
    });

    it("should return an empty array for an empty list", () => {
      list.clear();
      expect(list.getRange(0, 5)).toEqual([]);
    });

    it("should return correct range for single element list", () => {
      list.clear();
      list.rPush(100);
      expect(list.getRange(0, 0)).toEqual([100]);
      expect(list.getRange(-1, -1)).toEqual([100]);
    });

    it("should clamp indices to valid bounds", () => {
      expect(list.getRange(-100, 100)).toEqual([10, 20, 30, 40, 50, 60]);
      expect(list.getRange(0, 100)).toEqual([10, 20, 30, 40, 50, 60]);
      expect(list.getRange(-100, 0)).toEqual([10]);
    });
  });

  // Test trim
  describe("trim", () => {
    beforeEach(() => {
      list.rPush([10, 20, 30, 40, 50, 60]); // Initial list: [10, 20, 30, 40, 50, 60]
    });

    it("should trim to a sub-range with positive indices", () => {
      list.trim(1, 3); // Keep elements at index 1, 2, 3
      expect(list.length()).toBe(3);
      expect(list.getRange(0, 2)).toEqual([20, 30, 40]);
      expect(list.lPeek()).toBe(20);
      expect(list.rPeek()).toBe(40);
    });

    it("should trim with negative start index", () => {
      list.trim(-3, 5); // Keep last 3 elements
      expect(list.length()).toBe(3);
      expect(list.getRange(0, 2)).toEqual([40, 50, 60]);
    });

    it("should trim with negative stop index", () => {
      list.trim(0, -3); // Keep first 4 elements
      expect(list.length()).toBe(4);
      expect(list.getRange(0, 3)).toEqual([10, 20, 30, 40]);
    });

    it("should trim with both negative indices", () => {
      list.trim(-4, -2); // Keep elements at conceptual indices 2, 3, 4 ([30, 40, 50])
      expect(list.length()).toBe(3);
      expect(list.getRange(0, 2)).toEqual([30, 40, 50]);
    });

    it("should make the list empty if start > stop after adjustment", () => {
      list.trim(3, 1);
      expect(list.length()).toBe(0);
      expect(list.lPeek()).toBeUndefined();
      expect(list.rPeek()).toBeUndefined();

      list.rPush([1, 2, 3]);
      list.trim(10, 12); // Out of bounds high
      expect(list.length()).toBe(0);

      list.rPush([1, 2, 3]);
      list.trim(-10, -8); // Out of bounds low
      expect(list.length()).toBe(0);
    });

    it("should clear the list if trimmed range is invalid/empty", () => {
      list.trim(1, 0);
      expect(list.length()).toBe(0);
    });

    it("should leave the list unchanged if trim range is full list", () => {
      list.trim(0, 5);
      expect(list.length()).toBe(6);
      expect(list.getRange(0, 5)).toEqual([10, 20, 30, 40, 50, 60]);
    });

    it("should do nothing if list is already empty", () => {
      list.clear();
      list.trim(0, 10);
      expect(list.length()).toBe(0);
    });

    it("should handle trimming a single element list", () => {
      list.clear();
      list.rPush(100);
      list.trim(0, 0);
      expect(list.length()).toBe(1);
      expect(list.get(0)).toBe(100);
    });
  });
});

DoubleEndedList.ts

export const Positions = {
  BEFORE: "BEFORE",
  AFTER: "AFTER",
} as const;

type Position = (typeof Positions)[keyof typeof Positions];

export class DoubleEndedList<T> {
  private readonly _list: Map<number, T>;

  private _left = 0;
  private _right = 0;

  constructor() {
    this._list = new Map();
  }

  /**
   * Clears the elements in the list.
   */
  public clear(): void {
    this._list.clear();

    this._left = 0;
    this._right = 0;
  }

  /**
   * Returns the current number of elements in the list.
   */
  public length(): number {
    // Map.size gives us the true number of elements stored.
    // Alternatively, we could use `this._right - this._left` if the map was guaranteed to be dense between _left and _right,
    // but `Map.size` is more robust for actual stored elements. Redis's LLEN is O(1) because it tracks length explicitly.
    // For this Map-based implementation, `_list.size` is correct.

    return this._list.size;
  }

  /**
   * Returns the element at the front (left-most) of the list without removing it.
   * Returns `undefined` if the list is empty.
   *
   * Time Complexity: O(1)
   */
  public lPeek(): T | undefined {
    if (this.length() === 0) return undefined;

    return this._list.get(this._left + 1);
  }

  /**
   * Returns the element at the back (right-most) of the list without removing it.
   * Returns `undefined` if the list is empty.
   *
   * Time Complexity: O(1)
   */
  public rPeek(): T | undefined {
    if (this.length() === 0) return undefined;

    return this._list.get(this._right);
  }

  /**
   * Adds one or more elements to the front (left-most) of the list.
   * If an array is provided, elements are added in the order they appear,
   * meaning the first element of the array will be the new front of the list.
   *
   * Time Complexity: O(k) where k is the number of elements pushed.
   *
   * @param value The element(s) to add.
   */
  public lPush(value: T | T[]): void {
    if (Array.isArray(value)) {
      // Iterate in reverse to push them so that the first element in the array becomes the new head
      for (let i = value.length - 1; i >= 0; i--) {
        this._list.set(this._left--, value[i]!);
      }
    } else {
      this._list.set(this._left--, value);
    }
  }

  /**
   * Adds one or more elements to the back (right-most) of the list.
   * If an array is provided, elements are added in the order they appear,
   * meaning the last element of the array will be the new back of the list.
   *
   * Time Complexity: O(k) where k is the number of elements pushed.
   *
   * @param value The element(s) to add.
   */
  public rPush(value: T | T[]): void {
    if (Array.isArray(value)) {
      for (const v of value) {
        this._list.set(++this._right, v);
      }
    } else {
      this._list.set(++this._right, value);
    }
  }

  /**
   * Removes and returns the element from the front (left-most) of the list.
   * Returns `undefined` if the list is empty.
   *
   * Time Complexity: O(1)
   */
  public lPop(): T | undefined {
    if (this.length() === 0) return undefined;

    // Get value before incrementing _left
    const value = this.lPeek();

    this._list.delete(++this._left);

    // If the list becomes empty, reset pointers to initial state for cleanliness
    if (this.length() === 0) {
      this._left = 0;
      this._right = 0;
    }

    return value;
  }

  /**
   * Removes and returns the element from the back (right-most) of the list.
   * Returns `undefined` if the list is empty.
   *
   * Time Complexity: O(1)
   */
  public rPop(): T | undefined {
    if (this.length() === 0) return undefined;

    // Get value before decrementing _right
    const value = this.rPeek();

    this._list.delete(this._right--);

    // If the list becomes empty, reset pointers to initial state for cleanliness
    if (this.length() === 0) {
      this._left = 0;
      this._right = 0;
    }

    return value;
  }

  /**
   * Returns the element at the specified index.
   * Negative indices are supported (e.g., -1 for the last element, -2 for the second to last).
   * Returns `undefined` if the index is out of bounds or the list is empty.
   *
   * Time Complexity: O(1)
   *
   * @param index The zero-based index of the element to retrieve.
   */
  public get(index: number): T | undefined {
    if (this.length() === 0) return undefined;

    let idx: number;

    if (index < 0) {
      // Convert negative index to positive relative to the end
      idx = this._right + index + 1;
    } else {
      // Convert positive index to actual Map key
      idx = this._left + 1 + index;
    }

    // Check if the calculated actual index falls within our current logical range
    // _left is before the first element, _right is at the last element.
    // So valid indices are ( _left + 1 ) to _right inclusive.
    if (idx > this._left && idx <= this._right) {
      return this._list.get(idx);
    }

    return undefined;
  }

  /**
   * Sets the element at the specified index to a new value.
   * Negative indices are supported (e.g., -1 for the last element, -2 for the second to last).
   * This method only modifies existing elements; it does not add new ones if the index is out of bounds.
   *
   * Time Complexity: O(1)
   *
   * @param index - The zero-based index of the element to set.
   * @param value - The new value for the element.
   */
  public set(index: number, value: T): void {
    if (this.length() === 0) return;

    let idx: number;

    if (index < 0) {
      // Convert negative index to positive relative to the end
      idx = this._right + index + 1;
    } else {
      // Convert positive index to actual Map key
      idx = this._left + 1 + index;
    }

    // Check if the calculated actual index falls within our current logical range
    // _left is before the first element, _right is at the last element.
    // So valid indices are ( _left + 1 ) to _right inclusive.
    if (idx > this._left && idx <= this._right) {
      this._list.set(idx, value);
    }
  }

  /**
   * Inserts a new element into the list either before or after a specified pivot element.
   * The first occurrence of the pivot element is used.
   *
   * Time Complexity: O(N) in the worst case (needs to find pivot, then shift elements).
   *
   * @param position Whether to insert `value` 'BEFORE' or 'AFTER' the `pivot`.
   * @param pivot The existing element to use as a reference point.
   * @param value The element to insert.
   */
  public insert(position: Position, pivot: T, value: T): void {
    if (this.length() === 0) return;

    let pivotIdx: number = -1;

    // Iterate through the current logical range of the Map to find the pivot
    for (let i = this._left + 1; i <= this._right; i++) {
      if (this._list.get(i) === pivot) {
        pivotIdx = i;

        break;
      }
    }

    // Pivot not found
    if (pivotIdx === -1) return;

    const idx = position === Positions.BEFORE ? pivotIdx : pivotIdx + 1;

    // Shift elements to the right to make space for the new value
    // Iterate from the current _right down to the insertion point
    for (let i = this._right; i >= idx; i--) {
      const val = this._list.get(i);

      if (val !== undefined) {
        this._list.set(i + 1, val);
      }
    }

    // Insert the new value
    this._list.set(idx, value);
    // Increment right pointer as a new element is added
    this._right++;
  }

  /**
   * Removes the first `count` occurrences of elements equal to `value` from the list.
   * If `count` is positive, elements are removed starting from the front (left).
   * If `count` is negative, elements are removed starting from the back (right).
   * If `count` is 0, all elements equal to `value` are removed.
   *
   * Time Complexity: O(N) because it might require iterating through and rebuilding the list.
   *
   * @param count The number of occurrences to remove.
   * @param value The value to remove.
   */
  public remove(count: number, value: T): void {
    if (this.length() === 0) return;

    // Temporarily store the elements that will remain
    const remainingElements: T[] = [];

    if (count === 0) {
      // Remove all occurrences
      for (let i = this._left + 1; i <= this._right; i++) {
        if (this._list.get(i) !== value) {
          remainingElements.push(this._list.get(i)!);
        }
      }
    } else if (count > 0) {
      // Remove 'count' occurrences from left to right
      let toRemove = count;

      for (let i = this._left + 1; i <= this._right; i++) {
        if (this._list.get(i) === value && toRemove > 0) {
          toRemove--;
        } else {
          remainingElements.push(this._list.get(i)!);
        }
      }
    } else {
      // count < 0, remove from right to left
      const absCount = Math.abs(count);
      let toRemove = absCount;
      const indicesToRemove = new Set<number>();

      // First pass: identify actual Map indices to remove from the right
      for (let i = this._right; i >= this._left + 1 && toRemove > 0; i--) {
        if (this._list.get(i) === value) {
          indicesToRemove.add(i);

          toRemove--;
        }
      }

      // Second pass: add elements to remainingElements, skipping marked indices
      for (let i = this._left + 1; i <= this._right; i++) {
        if (!indicesToRemove.has(i)) {
          remainingElements.push(this._list.get(i)!);
        }
      }
    }

    // Clear the old map and rebuild it with remaining elements
    this.clear();

    for (const item of remainingElements) {
      // Populate from index 1 onwards
      this._list.set(++this._right, item);
    }

    // If the list becomes empty, ensure _right is properly 0
    if (this.length() === 0) {
      this._right = 0;
      this._left = 0;
    }
  }

  /**
   * Returns a range of elements from the list.
   * `start` and `stop` are zero-based indices. Negative indices are supported.
   * If `start` is greater than `stop`, an empty array is returned.
   *
   * Time Complexity: O(N) where N is the length of the requested range.
   *
   * @param start The starting index (inclusive).
   * @param stop The ending index (inclusive).
   */
  public getRange(start: number, stop: number): T[] {
    const result: T[] = [];

    if (this.length() === 0) return result;

    const currentLength = this.length();
    let effectiveStart = start;
    let effectiveStop = stop;

    // Adjust negative indices
    if (effectiveStart < 0) {
      effectiveStart = currentLength + effectiveStart;
    }

    if (effectiveStop < 0) {
      effectiveStop = currentLength + effectiveStop;
    }

    // Clamp to valid 0-based conceptual indices
    effectiveStart = Math.max(0, effectiveStart);
    effectiveStop = Math.min(currentLength - 1, effectiveStop);

    if (effectiveStart > effectiveStop) return result;

    // Iterate through the actual indices in the map to collect the range
    // The first element is at _left + 1, so the conceptual 0-index corresponds to _left + 1.
    // The conceptual `effectiveStart` corresponds to `_left + 1 + effectiveStart`.
    for (
      let i = this._left + 1 + effectiveStart;
      i <= this._left + 1 + effectiveStop;
      i++
    ) {
      const value = this._list.get(i);

      if (value !== undefined) {
        result.push(value);
      }
    }

    return result;
  }

  /**
   * Trims the list to contain only elements within the specified range.
   * `start` and `stop` are zero-based indices. Negative indices are supported.
   * If the resulting range is empty (e.g., `start` > `stop` after adjustments), the list becomes empty.
   *
   * Time Complexity: O(N) due to deletions and potential re-indexing.
   *
   * @param start The starting index (inclusive) of the range to keep.
   * @param stop The ending index (inclusive) of the range to keep.
   */
  public trim(start: number, stop: number): void {
    if (this.length() === 0) return;

    const currentLength = this.length();
    let effectiveStart = start;
    let effectiveStop = stop;

    // Adjust negative indices
    if (effectiveStart < 0) {
      effectiveStart = currentLength + effectiveStart;
    }

    if (effectiveStop < 0) {
      effectiveStop = currentLength + effectiveStop;
    }

    // Clamp to valid 0-based conceptual indices
    effectiveStart = Math.max(0, effectiveStart);
    effectiveStop = Math.min(currentLength - 1, effectiveStop);

    // If the effective range is empty or invalid after adjustment
    if (effectiveStart > effectiveStop) {
      this.clear();

      // List is now empty
      return;
    }

    // Collect elements that should remain
    const elementsToKeep: T[] = [];

    for (let i = effectiveStart; i <= effectiveStop; i++) {
      // Use `get` to handle mapping to actual Map keys
      const value = this.get(i);

      if (value !== undefined) {
        elementsToKeep.push(value);
      }
    }

    // Clear the existing map and rebuild with only the desired elements
    this.clear();

    for (const item of elementsToKeep) {
      this._list.set(++this._right, item);
    }

    // After re-population, _left remains 0, and _right is the new count of elements.
    // If elementsToKeep was empty, _right remains 0.
  }
}