@silencedis/sorted-linked-list

A dependency-free doubly linked list that maintains comparator-defined order and preserves insertion order among equivalent values.

Why this implementation?

Unlike a conventional linked list, this collection maintains comparator-defined order as elements are inserted.

• Always sorted: every insertion is placed according to a comparator.
• Stable equivalent ordering: values for which the comparator returns 0 retain their insertion order.
• Efficient boundary operations: insertion at either boundary is constant-time. Ascending streams naturally append to the tail, while descending streams prepend to the head.
• Ordered access and traversal: inspect or extract either boundary, or iterate from head to tail.
• No runtime dependencies: the package contains only ESM JavaScript and TypeScript declarations and does not depend on Node.js APIs.

Installation

npm install @silencedis/sorted-linked-list

The package is ESM-only:

import {
    SortedLinkedList,
    type Comparator,
} from '@silencedis/sorted-linked-list';

Quick start

import { SortedLinkedList } from '@silencedis/sorted-linked-list';

const numbers = new SortedLinkedList<number>();

numbers.insert(30);
numbers.insert(10);
numbers.insert(20);
numbers.insert(20);

console.log([...numbers].map(({element}) => element));
// [10, 20, 20, 30]

console.log(numbers.showHead()); // 10
console.log(numbers.showTail()); // 30

The default comparator uses JavaScript's < and > operators. Supply a custom comparator for objects, descending order, or domain-specific ordering.

Custom ordering and stable equivalents

import {
    SortedLinkedList,
    type Comparator,
} from '@silencedis/sorted-linked-list';

interface WorkItem {
    name: string;
    priority: number;
}

const byDescendingPriority: Comparator<WorkItem> = (a, b) => {
    return b.priority - a.priority;
};

const work = new SortedLinkedList(byDescendingPriority);

work.insert({name: 'routine', priority: 1});
work.insert({name: 'first urgent', priority: 10});
work.insert({name: 'second urgent', priority: 10});

console.log([...work].map(({element}) => element.name));
// ['first urgent', 'second urgent', 'routine']

Comparator-equivalent entries preserve their insertion order.

API

new SortedLinkedList<E>(comparator?)

Creates an empty list. A comparator follows the same sign convention as Array.prototype.sort():

type Comparator<E> = (a: E, b: E) => number;

• a negative value places a before b;
• a positive value places a after b;
• 0 makes the values equivalent while preserving their insertion order.

The comparator must define a consistent total ordering and must not return NaN. If it throws, the attempted insertion is not committed.

Properties

| Property | Type | Description | | --- | --- | --- | | size | number | Number of live entries. | | isEmpty | boolean | Whether the list contains no live entries. |

Methods

| Method | Result | Description | | --- | --- | --- | | insert(element) | SortedLinkedListNodeId | Inserts in sorted order and returns a new node ID. | | showHead() | E \| undefined | Reads the head element without removing it. | | showHead({returnEntry: true}) | SortedLinkedListEntry<E> \| undefined | Reads the head entry without removing it. | | showTail() | E \| undefined | Reads the tail element without removing it. | | showTail({returnEntry: true}) | SortedLinkedListEntry<E> \| undefined | Reads the tail entry without removing it. | | extractHead() | E \| undefined | Removes and returns the head element. | | extractHead({returnEntry: true}) | SortedLinkedListEntry<E> \| undefined | Removes and returns the head entry. | | extractTail() | E \| undefined | Removes and returns the tail element. | | extractTail({returnEntry: true}) | SortedLinkedListEntry<E> \| undefined | Removes and returns the tail entry. | | extractById(nodeId) | E \| undefined | Removes and returns the element identified by a live node ID. | | clear() | void | Removes all entries without reusing previous IDs. | | forEach(callback) | void | Visits entries in order; returning false stops traversal. | | [Symbol.iterator]() | Generator<SortedLinkedListEntry<E>> | Iterates from head to tail. |

When {returnEntry: true} is used, or when the list is iterated, an entry has this shape:

interface SortedLinkedListEntry<E> {
    readonly element: E;
    readonly nodeId: number;
}

Node IDs belong to one list instance. They increase monotonically, are not reused after extraction or clear(), and should be treated as opaque handles.

Complexity

Let n be the number of live entries and d the number of links traversed from the selected insertion anchor.

| Operation | Time | Notes | | --- | --- | --- | | Insert into an empty list, head, or tail | O(1) | Excluding comparator cost. | | Insert into the middle | O(d), worst O(n) | Starts near the last live insertion when possible. | | Read head, tail, size, or emptiness | O(1) | Direct metadata access. | | Extract head or tail | O(1) | Updates one boundary and adjacent link. | | Extract by node ID | Expected O(1) | Map lookup followed by constant-time unlinking. | | Full traversal | O(n) | Visits each reachable entry once. |

For middle insertion, the search starts from the most recently inserted live entry when possible. This can reduce d for clustered input, but the worst case remains O(n).

Space usage is O(n). Compared with a minimal linked list, each entry also has an ID and an index entry in the internal Map.

Choosing the right structure

Compared with a sorted array

A sorted array can locate an insertion position with binary search, but inserting or removing there shifts later elements. This linked list instead spends up to O(n) finding a middle position and then links the node in constant time. It is most effective when data often arrives near either boundary or the latest insertion.

Compared with a heap-based priority queue

A binary heap usually provides O(log n) insertion and head extraction, making it a better fit for large, randomly ordered queues that only consume the minimum or maximum. This list is a better fit when you also need full sorted traversal, stable equivalent ordering, or access to both boundaries.

Compared with a conventional linked list

A conventional linked list does not maintain ordering and normally needs a linear search to find an arbitrary value. This implementation maintains order on every insertion. Its optional ID lookup supports extractById() at the cost of additional memory.

Platform support

The published output targets ES2022 and uses no Node.js-specific API. It can run in modern Node.js, Bun, Deno, and browser projects whose runtime or bundler supports standard ESM and ES2022.

Development

npm ci
npm run check

License

MIT © 2026 Yurii Slobodeniuk