@thi.ng/dcons NPM

npm downloads

This project is part of the @thi.ng/umbrella monorepo.

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

ES module import:

<script type="module" src="https://cdn.skypack.dev/@thi.ng/dcons"></script>

Skypack documentation

For Node.js REPL:

# with flag only for < v16
node --experimental-repl-await

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

Package sizes (gzipped, pre-treeshake): ESM: 2.14 KB

Dependencies

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

Karsten Schmidt

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

acceleration datastructure heuristic iterator linkedlist list queue self-organization stack typescript

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

@allforabit/csp @allforabit/associative @everything-registry/sub-chunk-914 @thi.ng/adjacency @thi.ng/transducers-stats @thi.ng/ecs @thi.ng/associative @thi.ng/cache @thi.ng/indicators @thi.ng/iterators

7 days ago

10 days ago

13 days ago

22 days ago

25 days ago

1 month ago

1 month ago

1 month ago

1 month ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

2 months ago

3 months ago

3 months ago

3 months ago

3 months ago

3 months ago

3 months ago

3 months ago

3 months ago

3 months ago

4 months ago

4 months ago

5 months ago

5 months ago

5 months ago

5 months ago

5 months ago

5 months ago

6 months ago

6 months ago

6 months ago

8 months ago

7 months ago

7 months ago

7 months ago

7 months ago

6 months ago

6 months ago

6 months ago

6 months ago

6 months ago

6 months ago

5 months ago

10 months ago

9 months ago

9 months ago

9 months ago

8 months ago

8 months ago

8 months ago

8 months ago

9 months ago

9 months ago

8 months ago

9 months ago

8 months ago

8 months ago

11 months ago

12 months ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

1 year ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

2 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

3 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

4 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

5 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

6 years ago

7 years ago

7 years ago

7 years ago

7 years ago