Skip to content

Latest commit

 

History

History

dcons

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

@thi.ng/dcons

npm version npm downloads Mastodon Follow

Note

This is one of 199 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

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

yarn add @thi.ng/dcons

ESM import:

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

Browser ESM import:

<script type="module" src="https://esm.run/@thi.ng/dcons"></script>

JSDelivr documentation

For Node.js REPL:

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

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

Dependencies

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

API

Generated API docs

Head centric

  • cons()
  • first()
  • drop()
  • setHead()

Tail centric

  • into()
  • push()
  • peek()
  • pop()
  • setTail()

Random Access

  • .length
  • nth()
  • nthCell()
  • setNth()

Insertion

  • insertBefore()
  • insertAfter()
  • insertBeforeNth()
  • insertAfterNth()
  • insertSorted()

Finding

  • find()
  • findWith()

Structure

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

TODO

Authors

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

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

License

© 2017 - 2024 Karsten Schmidt // Apache License 2.0