!@thi.ng/dcons

!npm downloads

> [!NOTE]
> This is one of 214 standalone projects, maintained as part
> of the @thi.ng/umbrella monorepo
> and anti-framework.
>
> 🚀 Please help me to work full-time on these projects by sponsoring me on
> GitHub. Thank you! ❤️

- About
- Status
- Installation
- Dependencies
- API
- Head centric
- Tail centric
- Random Access
- Insertion
- Finding
- Structure
- Authors
- License

About

Double-linked lists with comprehensive set of operations (incl. optional self-organizing behaviors).

- ES6 iterator support
- Stack & queue API (front and/or back)
- Random node access (read / write, O(n/2))
- Node insertion (also w/ custom comparator)
- Node finding (O(n))
- Node swaps (O(1))
- Reversing (O(n/2))
- Rotation (left / right) (O(1))
- Shuffling (configurable, support custom PRNG)
- Sorting (Merge sort, w/ custom comparator)
- Slicing (sublist copies)
- Splicing (delete and/or insert)
- release() (emptying, GC friendly)
- concat() / into()
- map() / filter() / reduce()
- compare() / equiv()
- toJSON() transform (-> array)

v2.3.0 adds the self-organizing
list type SOL (an
extension of DCons), which dynamically re-orders items based on certain
accesses and offers these two built-in strategies:

- defMTF() - moves currently accessed element to front of list
- defTranspose() - swaps currently accessed element with its predecessor

Only the following operations will trigger the self-organizing behavior:

- nth()
- setNth()
- setTail()
- find()
- findWith()

Btw. Also see
@thi.ng/cache
for more LRU, MRU implementations based on managed DCons impls...

Status

STABLE - used in production

Search or submit any issues for this package

Installation

``bash
yarn add @thi.ng/dcons
`

ESM import:

`ts
import * as dcons from "@thi.ng/dcons";
`

Browser ESM import:

`html

`

JSDelivr documentation

For Node.js REPL:

`js
const dcons = await import("@thi.ng/dcons");
`

Package sizes (brotli'd, pre-treeshake): ESM: 2.54 KB

Dependencies

- @thi.ng/api
- @thi.ng/checks
- @thi.ng/compare
- @thi.ng/equiv
- @thi.ng/errors
- @thi.ng/random
- @thi.ng/transducers

Note: @thi.ng/api is in _most_ cases a type-only import (not used at runtime)

API

Generated API docs

$3

- cons()
- first()
- drop()
- setHead()

$3

- into()
- push()
- peek()
- pop()
- setTail()

$3

- .length
- nth()
- nthCell()
- setNth()

$3

- insertBefore()
- insertAfter()
- insertBeforeNth()
- insertAfterNth()
- insertSorted()

$3

- find()
- findWith()

$3

- copy()
- concat()
- slice()
- splice()
- swap()
- shuffle()
- sort()
- reverse()
- rotateLeft()
- rotateRight()
- release()

TODO

Authors

- Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

`bibtex
@misc{thing-dcons,
title = "@thi.ng/dcons",
author = "Karsten Schmidt",
note = "https://thi.ng/dcons",
year = 2017
}
``

License

© 2017 - 2026 Karsten Schmidt // Apache License 2.0