std-doublell

The most type-safe, performant, and developer-friendly doubly linked list for TypeScript and JavaScript

A production-ready doubly linked list implementation that works seamlessly in both browsers and Node.js. Combines the performance of low-level data structures with the convenience of modern JavaScript APIs. Perfect for algorithms, data processing, and any application requiring efficient insertion/deletion operations.

🚀 Quick Start

npm install std-doublell
# or
yarn add std-doublell

import { DoubleLinkedList } from "std-doublell";

// Create and populate
const list = new DoubleLinkedList(1, 2, 3);

// Modern iteration
for (const item of list) {
  console.log(item); // 1, 2, 3
}

// Array-like methods
const doubled = list.map((x) => x * 2);
console.log([...doubled]); // [2, 4, 6]

// Stack/Queue operations
list.push(4); // Add to end
const last = list.pop(); // Remove from end
const first = list.shift(); // Remove from start

✨ Why Choose doublell?

🎯 Type-Safe by Design

// Full TypeScript generics support
const numbers = new DoubleLinkedList<number>(1, 2, 3);
const strings = numbers.map((n) => n.toString()); // DoubleLinkedList<string>

// AI assistants and IDEs love the complete type information
const found = list.find((x) => x > 5); // number | undefined

⚡ Performance Optimized

• O(1) insertion/deletion at any position (when you have the node reference)
• O(1) push/pop/shift/unshift operations
• Zero dependencies - minimal bundle impact for web and Node.js

🧑‍💻 Universal Developer Experience

// Array-like index access with optimization
console.log(list.get(0)); // First item
console.log(list.get(-1)); // Last item (optimized from tail)
console.log(list.get(5)); // Item at index 5

// Familiar Array-like API
list.forEach((item, index) => console.log(item, index));
const found = list.find((x) => x > 10);
const includes = list.includes(42);
const index = list.indexOf("hello");

// Iterator protocol support
const array = [...list]; // Spread operator
const mapped = Array.from(list); // Array.from
for (const item of list) {
  /* */
} // for...of loops

// Stack and Queue operations (works in browser and Node.js)
const stack = new DoubleLinkedList<string>();
stack.push("first");
stack.push("second");
console.log(stack.pop()); // 'second' (LIFO)

const queue = new DoubleLinkedList<number>();
queue.push(1);
queue.push(2);
console.log(queue.shift()); // 1 (FIFO)

🔧 Node-Level Control

import {
  DoubleLinkedList,
  getNextNode,
  getPreviousNode,
  getNodeValue,
} from "doublell";

// Traditional node manipulation
const list = new DoubleLinkedList("a", "b", "d");
const nodeB = getNextNode(list.getHead());
if (nodeB) {
  list.insertAfterNode(nodeB, "c"); // O(1) insertion
}

// Enhanced node-based splice - even more powerful!
const list2 = new DoubleLinkedList(1, 2, 5, 6);
const nodeAt5 = getPreviousNode(list2.getTail());
if (nodeAt5) {
  // Replace one item with multiple - all in O(1)!
  list2.splice(nodeAt5, 1, 3, 4); // [1, 2, 3, 4, 6]
}

// Append efficiently using undefined
list2.splice(undefined, 0, 7, 8, 9); // [1, 2, 3, 4, 6, 7, 8, 9]

📚 Complete API Reference

Core Operations

// Creation and basic operations
const list = new DoubleLinkedList<T>(...items);
list.append(item); // Add to end
list.prepend(item); // Add to beginning
list.getLength(); // Get size
list.isEmpty(); // Check if empty
list.clear(); // Remove all items
list.remove(node); // Remove specific node

// Node access
list.getHead(); // First node
list.getTail(); // Last node
list.insertAfterNode(node, item); // Insert after node
list.insertBeforeNode(node, item); // Insert before node

Array-like Methods

// Index-based access
list.get(index)             // Get item by index (supports negative indices)
list.getNodeAt(index)       // Get node by index (supports negative indices)

// Iteration and transformation
list.forEach(callback)      // Execute function for each item
list.map(callback)          // Transform to new list
list.find(predicate)        // Find first matching item
list.indexOf(item)          // Get index of item
list.includes(item)         // Check if item exists
list.toArray()              // Convert to array

// Array modification
list.splice(start, deleteCount, ...items)  // Remove/insert items at index

// Stack/Queue operations
list.push(item)             // Add to end (alias for append)
list.pop()                  // Remove from end
list.shift()                // Remove from beginning
list.unshift(item)          // Add to beginning (alias for prepend)

// Iterator support
[...list]                   // Spread to array
Array.from(list)            // Convert to array
for (const item of list)    // for...of iteration

🎨 Real-World Use Cases

LRU Cache Implementation

// Why DoubleLinkedList is perfect for LRU Cache:
// - O(1) access to both ends (most/least recently used)
// - O(1) removal from anywhere (when you have the node reference)
// - O(1) insertion at head (mark as most recently used)

class LRUCache<K, V> {
  private capacity: number;
  private list = new DoubleLinkedList<{ key: K; value: V }>();
  private map = new Map<K, DoubleLinkedListNode<{ key: K; value: V }>>();

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (node !== undefined) {
      // Move to front (most recently used) - O(1)!
      this.list.remove(node);
      const nodeValue = getNodeValue(node);
      const newNode = this.list.prepend(nodeValue);
      this.map.set(key, newNode);
      return nodeValue.value;
    }
    return undefined;
  }

  set(key: K, value: V): void {
    const existingNode = this.map.get(key);

    if (existingNode !== undefined) {
      // Update existing - move to front
      this.list.remove(existingNode);
      const newNode = this.list.prepend({ key, value });
      this.map.set(key, newNode);
    } else {
      // Check capacity - evict LRU if needed
      if (this.list.getLength() >= this.capacity) {
        const tail = this.list.getTail(); // Least recently used
        if (tail !== undefined) {
          this.list.remove(tail); // O(1) eviction!
          const tailValue = getNodeValue(tail);
          this.map.delete(tailValue.key);
        }
      }

      // Add new item at front (most recently used)
      const newNode = this.list.prepend({ key, value });
      this.map.set(key, newNode);
    }
  }
}

// Perfect O(1) performance for all LRU operations!
const cache = new LRUCache<string, number>(3);
cache.set("a", 1);
cache.set("b", 2);
cache.set("c", 3);
cache.get("a"); // Move 'a' to front
cache.set("d", 4); // Evicts 'b' (LRU) in O(1)

Undo/Redo System

import {
  DoubleLinkedList,
  DoubleLinkedListNode,
  getNextNode,
  getPreviousNode,
  getNodeValue,
} from "doublell";

class UndoRedoManager<T> {
  private history = new DoubleLinkedList<T>();
  private current: DoubleLinkedListNode<T> | undefined;

  execute(state: T): void {
    // When executing new action, discard any "future" states using node-based splice
    const nextNode = this.current ? getNextNode(this.current) : undefined;
    if (this.current !== undefined && nextNode !== undefined) {
      // Remove all states after current position - O(1) with node reference!
      this.history.splice(nextNode, this.history.getLength());
    }

    // Add new state
    this.current =
      this.current !== undefined
        ? this.history.insertAfterNode(this.current, state)
        : this.history.append(state);
  }

  undo(): T | undefined {
    const prevNode = this.current ? getPreviousNode(this.current) : undefined;
    if (this.current !== undefined && prevNode !== undefined) {
      this.current = prevNode;
      return getNodeValue(this.current);
    }
    return undefined;
  }

  redo(): T | undefined {
    const nextNode = this.current ? getNextNode(this.current) : undefined;
    if (this.current !== undefined && nextNode !== undefined) {
      this.current = nextNode;
      return getNodeValue(this.current);
    }
    return undefined;
  }
}

// Comprehensive JSDoc comments provide context for AI suggestions // AI assistants can explain performance characteristics and usage patterns

## 📊 Performance Comparison

| Operation          | doublell    | Array       | Native Set  |
| ------------------ | ----------- | ----------- | ----------- |
| Insert at position | **O(1)** ⚡ | O(n)        | N/A         |
| Delete at position | **O(1)** ⚡ | O(n)        | N/A         |
| Push/Pop           | **O(1)** ⚡ | **O(1)** ⚡ | N/A         |
| Shift/Unshift      | **O(1)** ⚡ | O(n)        | N/A         |
| Find element       | O(n)        | O(n)        | **O(1)** ⚡ |
| Iteration          | O(n)        | O(n)        | O(n)        |

_Use doublell when you need frequent insertions/deletions. Use Array for random access. Use Set for fast lookups._

## 🛠️ Development

```bash
# Install dependencies
yarn install

# Run tests (Node.js)
yarn test

# Build for production (CommonJS + ESM)
yarn build

# Generate documentation
yarn generate:docs

# Lint code
yarn lint

Browser Support

• Modern browsers with ES2015+ support
• Bundle size: Minified and tree-shakeable
• Module formats: ESM and UMD available

Node.js Support

• Node.js 14.14+ (all maintained versions)
• CommonJS and ESM module support
• TypeScript definitions included

📄 License

MIT

Keywords: doubly-linked-list, data-structure, typescript, javascript, algorithm, performance, type-safe, iterator, functional-programming, generic, zero-dependencies, browser, nodejs, universal