Computer Science Data Structures and Algorithms in JavaScript ( Node.JS, ES ) in simple, clean, reusable code
Computer Science Data Structured and Algorithms in JavaScript ( Node.JS, ES ) in simple, clean, reusable code.
Contains Heap, Trie, SkipList, QuickSelect, various sorts and more.
cs101 on NPM.
Click links below to go straight to the code :sparkles: for each structure or algorithm;
Or jump straight to the API documentation.
Get for use:
$ npm i --save cs101
Get to run tests and modify:
$ cd cs.js
$ npm i
$ npm test
$ npm run browser-test
Then open that machine's port 8080 in a browser and view the developer console to see test output.
Linting:
$ npm run lint
Push test output to a file:
$ npm run save-test
Test output will be in file testout.txt
Note: there is no cycle checking, and it's possible to create cycles by adding nodes to head that are already present in the list.
Direct import:
import SingList from './src/lib/singlist.js';
Package import:
import * as CS from 'cs101';
const SingList = CS.SingList.Class
Creation:
// empty singlist
const list = new SingList();
// filled singlist
const dataList = new SingList([1,2,3,4,5]);
Getting head:
const list = new SingList(['beginning', 'middle', 'end']);
const thing = list.head.thing;
console.assert(thing === 'beginning');
Inserting at head:
const list = new SingList(['x','y','z']);
list.head = new SingList.Node('w');
[...list]; // 'w', 'x', 'y', 'z'
Iterating:
const list = new SingList([1,2,3,4,5]);
const things = [...list];
console.assert(things.join(',') === '1,2,3,4,5'); // true
Reversing:
const list = new SingList([1,2,3,4,5]);
list.reverse();
const reversedThings = [...list];
console.assert(reversedThings.join(',') === '5,4,3,2,1'); // true
Note: there is no cycle checking, and it's possible to create cycles by adding nodes that are already present in the list.
Direct import:
import LinkedList from './src/lib/linkedlist.js';
Direct import including Node class:
import {Class as LinkedList, Node} from './src/lib/linkedlist.js';
Direct import including Node class alternative style:
import LinkedList from './src/lib/linkedlist.js';
const Node = LinkedList.Node;
Package import:
import * as CS from 'cs101';
const LinkedList = CS.LinkedList.Class
Creation:
// empty linked list
const list = new LinkedList();
// filled linked list
const dataList = new LinkedList([1,2,3,4,5]);
Getting head:
const list = new LinkedList(['beginning', 'middle', 'end']);
const thing = list.head.thing;
console.assert(thing === 'beginning');
Removing head:
const headThing = list.shift();
Inserting at head (item only):
list.unshift('i am a thing');
Inserting at head (using a Node):
const list = new LinkedList(['x','y','z']);
list.head = new LinkedList.Node('w');
[...list]; // 'w', 'x', 'y', 'z'
Getting tail:
const list = new LinkedList(['beginning', 'middle', 'end']);
const thing = list.tail.thing;
console.assert(thing === 'end');
Removing tail:
const tailThing = list.pop();
Inserting at tail (item only):
list.push('i am a thing');
Inserting at tail (using a Node):
const list = new LinkedList(['x','y','z']);
list.tail = new LinkedList.Node('w');
[...list]; // 'w', 'x', 'y', 'z'
Iterating:
const list = new LinkedList([1,2,3,4,5]);
const things = [...list].map(node => node.thing);
console.assert(things.join(',') === '1,2,3,4,5'); // true
Deleting a node:
const list = new LinkedList([1,2,3,4,5]);
const node3 = [...list][2];
list.delete(node3);
const nodes = [...list].map(node => node.thing); // 1, 2, 4, 5
Deleting a node alternate style:
const list = new LinkedList([1,2,3,4,5]);
const node3 = list.head.nextList(0).nextList(0);
list.delete(node3);
const nodes = [...list].map(node => node.thing); // 1, 2, 4, 5
Move a node toward head:
const newTail = new LinkedList.Node('in the back');
list.tail = newTail;
list.advance(newTail);
console.assert([...list][list.length - 2] === newTail);
Reversing:
const list = new LinkedList([1,2,3,4,5]);
list.reverse(); // O(1) operation
const reversedThings = [...list].map(({thing}) => thing);
console.assert(reversedThings.join(',') === '5,4,3,2,1'); // true
Get length:
list.length; // 5
Importing directly:
import SOL from './src/sol.js';
Importing from package:
import * as CS from 'cs101';
const SOL = CS.SOL.Class;
Creating:
const sol = new SOL({
asLinkedList: false, /* underlying store is linked list, false is array */
moveToFront: 0.8, /* MTF reorganize scheme probability */
swap: 0.2, /* swap reorganize scheme probability */
dupesOK: false, /* duplicate keys are not OK, true they are */
});
Setting a key, value pair:
sol.set('taco', {awesome:true});
Testing membership:
sol.has('taco'); // true
Getting a value from a key:
sol.get('taco'); // {index: 0, copy: {key: 'taco', value: {awesome:true}}}
Deleting a key:
sol.delete('taco'); // :'(
sol.get('taco'); // {index: undefined, copy: undefined}
Iterating:
sol.set('taco', {trulyAwesome:[true, true]}); // XD
[...sol]; // [ {key: 'taco', value: {trulyAwesome: [true, true]}} ]
Get length:
sol.length; // 1
Importing directly:
import Tree from './src/lib/tree.js';
// equivalent with Node
import {Tree, Node} from './src/lib/tree.js';
Importing from package:
import * as CS from 'cs101';
const Tree = CS.Tree.Class;
const Node = Tree.Node; // CS.Tree.Node equivalent
Creating:
const tree = new Tree({arity: 5}); // arity: 2 is binary tree
``
Creating Nodes:
```js
const newRoot = new Node({thing: 'i am a node value'});
Getting / setting the root:
tree.setRoot(newRoot);
tree.getRoot(); // Node {thing: 'i am a Node value'}
Adding child nodes:
tree.getRoot().addChild(new Node({thing: 'i am under the first thing'}));
tree.getRoot().addChild(new Node({thing: 'me too. i am also under the first thing'}));
tree.getRoot().addChild(new Node({thing: 'me three. i too am under the first thing'}));
Getting / Deleting child nodes:
const meTooNode = tree.getRoot().children[1];
tree.getRoot().deleteSubtree(meTooNode);
tree.getRoot().degree; // 2
Iterating:
// depth-first
for( const {node, depth} of tree.dfs() ) {
console.log({node, depth});
}
// breath-first
for( const {node, depth} of tree.bfs() ) {
console.log({node, depth});
}
Updating Node value:
import {Empty} from './src/lib/tree.js';
const meThreeNode = tree.getRoot().children[1];
meThreeNode.thing = Empty; // Empty is a special symbol value
Finding the first empty leaf:
const emptyLeaf = tree.firstEmptyLeaf();
console.assert(emptyLeaf === meThreeNode); // true
Importing directly:
import Heap from './src/heap.js';
Importing from package:
import * as CS from 'cs101';
const Heap = CS.Heap.Class;
Creating:
const data = [0,10,8,7,2,1];
const heap = new Heap({
asTree: false, /* underlying implementation as tree, false is list implementation */
max: true, /* max heap, false is min heap */
arity: 2, /* binary, then 3 is ternary, etc. */
compare: undefined /* a custom comparator per JS Array.sort compareFunction interface */
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#parameters
// with comparison directed by the heap property
// so compare(bigger, smaller) is > 0 for max heap
// while compare(smaller, bigger) is > 0 for min heap
// and vice versa
// in essence, it's
// compare(top, bottom) > 0 and compare(bottom, top) < 0
// DEFAULT comparison is simply this applied to Numbers
}, data); // O(n) (uses Floyd's heapify)
Getting size:
heap.size; // 6
Getting top:
heap.peek(); // 10 O(1)
Replacing top:
heap.replace(22); // 10 O(log n)
heap.size; // 6
Removing top:
heap.pop(); // 22 O(log n)
heap.size; // 5
heap.peek(); // 8
Pushing something on:
heap.push(-5);
heap.peek(); // 8
heap.push(9);
heap.peek(); // 9
Importing directly:
import PQ from './src/pq.js';
Importing from package:
import * as CS from 'cs101';
const PQ = CS.PQ.Class;
Creating:
// data should have priority
const data = [
{
priority: 8,
stuff: 'ooo',
moreStuff: {ok: true}
},
{
priority: 2,
hello: 1
},
{
priority: 9,
text: 'yes'
}
];
// default options shown below
const pq = new PQ({
max: true,
compare: function (A, B) {
const {priority:pA = Empty} = A;
const {priority:pB = Empty} = B;
if ( pB == Empty ) {
return 1;
} else if ( pA == Empty ) {
return -1;
}
if ( pA > pB ) {
return this.config.max ? 1 : -1;
} else if ( pA == pB ) {
return 0;
} else {
return !this.config.max ? 1 : -1;
}
}
}, data); // O(n) (uses Floyd's heapify)
Get size:
pq.size; // 3
Get top priority:
pq.top(); // {priority: 9, text: 'yes'}
Remove top priority:
pq.pull(); // {priority: 9, text: 'yes'}
pq.top(); // {priority: 8, stuff: 'ooo', moreStuff: {ok: true}}
pq.size; // 2
Importing directly:
import Trie from './src/trie.js';
Importing from package:
import * as CS from 'cs101';
const Trie = CS.Trie.Class;
Creating (strings only, Map or object):
const data1 = ['abc', 'def'];
const trie1 = new Trie({
asTree: false, /* underlying implementation as tree, false is list implementation */
max: true, /* max heap, false is min heap */
arity: 2, /* binary, then 3 is ternary, etc. */
compare: undefined /* a custom comparator per JS Array.sort compareFunction interface */
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#parameters
// with comparison directed by the heap property
// so compare(bigger, smaller) is > 0 for max heap
// while compare(smaller, bigger) is > 0 for min heap
// and vice versa
// in essence, it's
// compare(top, bottom) > 0 and compare(bottom, top) < 0
// DEFAULT comparison is simply this applied to Numbers
}, data); // O(n) (uses Floyd's heapify)
const data2 = new Map([
['abc', {movie: 'ok'}],
['def', {time: 'yes'}]
]);
const trie2 = new Trie(null, data2);
const data3 = {
abc: {movie: 'ok'},
def: {time: 'yes'},
}
const trie3 = new Trie(null, data3);
Getting size:
trie1.size; // 2
trie2.size; // 2
trie3.size; // 2
Membership:
trie1.has('ab'); // no
trie1.has('abc'); // yes
trie1.has('xyz'); // no
Setting / updating:
trie1.set('xyz', {everybody: 'else'});
trie1.set('zzz', {accounting: true});
trie1.size; // 3
Getting:
trie1.get('zzz'); // {found: true, value: {accounting: true}}
trie1.get('---'); // {found: false, value: undefined}
Deleting:
trie1.delete('def');
trie1.size; // 2
Iterating (keys, values, entries):
[...trie1.keys()]; // 'abc', 'zzz',
[...trie1.values()]; // true, {accounting: true}
[...trie1.entries()]; // ['abc', true], ['zzz', {accounting:true}
Importing directly:
import SkipList from './src/skiplist.js';
Importing from package:
import * as CS from 'cs101';
const SkipList = CS.SkipList.Class;
Creating:
const data = [1,2,3,4,5]; // data can also be empty or undefined is OK
// default options shown below
const skiplist = new SkipList({
max: false, /* increasing order, true gives decreasing order */
p: 1/2, /* probability node lifts to higher levels */
randomized: true, /* if we base lifting on randomizedation */
// false uses a determ inistic lifting scheme
duplicatesOkay: false, /* only insert each thing once, true allows dupes */
compare: undefined, /* custom comparator function */
}, data); // O(n log(1/p) n)
Get size:
skiplist.size; // 3
Set thing:
skiplist.insert(84, '1984'); //
skiplist.set(84, '1984'); // alias of insert
skiplist.size; // 6 (would be 7 if dupesOK: true)
Get thing:
skiplist.get(84); // {has: true, value: '1984', index: 5}
Get thing by index:
skiplist.getSlot(5); // {has: true, thing: 84, value: '1984'}
skiplist.getSlot(0); // {has: true, thing: 1, value: true}
Delete thing:
skiplist.delete(2); // true
skiplist.delete('foo'); // false
skiplist.size; // 5
skiplist.getSlot(5); // {has: false, thing: undefined, value: undefined}
skiplist.getSlot(4); // {has: true, thing: 84, value: '1984'}
Membership:
skiplist.has(84); // true;
skiplist.has('bar'); // false;
Iteration (keys, values, entries):
[...skiplist.keys()]; // 1, 3, 4, 5, 84
[...skiplist.values()]; // true, true, true, true, '1984'
[...skiplist.entries()]; // [1, true], [3, true], [4, true], [5, true], [84, '1984']
Import direct:
import BinarySearch from './src/binarysearch.js';
// equivalent
import {find} from './src/binarysearch.js';
// lower-level alternatives
import {iterativeBinarySearch} from './src/binarysearch.js';
import {recursiveBinarySearch} from './src/binarysearch.js';
Import from package:
import * as CS from 'cs101';
const BinarySearch = CS.BinarySearch.find;
Finding an item:
const list = ['92', 'abc', 'delta', 'twenty1'];
const {has, index} = BinarySearch(list, 'abc'); // {has: true, index: 1}
Finding where to insert an item:
// index gives where to insert before (so insert at 3, moves existing list[3] to list[4])
const {has, index} = BinarySearch(list, 'really'); // {has: false, index: 3}
list.splice(index, 0, 'really');
Using more options:
const list = [{a:1,b:'hi'}, {a:2,b:'9'}, {a:4,b:'12321'}];
const {has, index} = BinarySearch(list, {a:2}, {
compare: ({a:a1}, {a:a2}) => Math.sign(a1-a2),
recursive: true /* false is iterative, the default */
}); // {has: true, index: 1}
Using iterative and recursive directly:
import {iterativeBinarySearch} from './src/binarysearch.js';
import {recursiveBinarySearch} from './src/binarysearch.js';
const list = [1,2,3,4,5,8, 7,4,3,2,1];
// args are -> (data, item, low, high, opts)
iterativeBinarySearch(list, 4, 0, 6, {compare:(a,b) => Math.sign(a-b)}); // {has: true, index: 3}
recursiveBinarySearch(list, 4, 0, 6, {compare:(a,b) => Math.sign(a-b)}); // {has: true, index: 3}
Import direct:
import QuickSelect from './src/selectquick.js';
// equivalent
import {findKth} from './src/selectquick.js';
Import from package:
import * as CS from 'cs101';
const QuickSelect = CS.QuickSelect.findKth;
Finding an the kth item in an unordered list:
const list = ['delta', '92', 'twenty1', 'abc'];
const kth = QuickSelect(list, 1); // 'abc' is the 1st item, O(n)
Using more options:
const list = [{a:1,b:'hi'}, {a:4,b:'12321'}, {a:2,b:'9'}];
const kth = QuickSelect(list, 3, {
pivot: undefined, /* use simple random pivot, */
/* 'mom' uses median of medians but currently requires list be numbers */
compare: ({a:a1}, {a:a2}) => Math.sign(a1-a2),
/* undefined uses DEFAULT_COMPARE, or you can use a custom comparison */
recursive: true, /* false is iterative, the default */
invert: false, /* invert order */
}); // {a:4, b:'12321'} is the 3rd item
Import direct:
import InsertionSort from './src/insertionsort.js';
// equivalent
import {sort} from './src/insertionsort.js';
Import from package:
import * as CS from 'cs101';
const InsertionSort = CS.InsertionSort.sort;
Sorting a list
const list = [5,9,2,4,1,3,0,8];
const sorted = InsertionSort(list); // [0,1,2,3,4,5,8,9]
Using more options:
const list = [{a:4,b:'12321'}, {a:1,b:'hi'}, {a:2,b:'9'}];
const sorted = InsertionSort(list, {
invert: false, /* inverts the order */
compare: ({a:a1}, {a:a2}) => Math.sign(a1-a2),
/* undefined uses DEFAULT_COMPARE, but can be a custom comparison */
inplace: true, /* sort is in place,
/* false is create a new array without changing original */
nobs: false, /* false gives an O(N log N) sort */
/* true will not use binary search (just linear search) to */
/* find insert index in sorted part of list, reduces to O(N**2) */
nosplice: false, /* don't use array splice operations on inplace array instead use swaps */
}); // [{a:1,b:'hi'}, {a:2,b:'9'}, {a:4,b:'12321'}]
Import direct:
import SelectionSort from './src/ssort.js';
// equivalent
import {sort} from './src/ssort.js';
Import from package:
import * as CS from 'cs101';
const SelectionSort = CS.SelectionSort.sort;
Sorting a list
const list = [5,9,2,4,1,3,0,8];
const sorted = SelectionSort(list); // [0,1,2,3,4,5,8,9]
Using more options:
const list = [{a:4,b:'12321'}, {a:1,b:'hi'}, {a:2,b:'9'}];
const sorted = SelectionSort(list, {
invert: false, /* inverts the order */
compare: ({a:a1}, {a:a2}) => Math.sign(a1-a2),
/* undefined uses DEFAULT_COMPARE, but can be a custom comparison */
inplace: true, /* sort is in place,
/* false is create a new array without changing original */
nosplice: false, /* don't use array splice operations on inplace array instead use swaps */
}); // [{a:1,b:'hi'}, {a:2,b:'9'}, {a:4,b:'12321'}]
Import direct:
import MergeSort from './src/mergesort.js';
// equivalent
import {sort} from './src/mergesort.js';
Import from package:
import * as CS from 'cs101';
const MergeSort = CS.MergeSort.sort;
Sorting a list
const list = [5,9,2,4,1,3,0,8];
const sorted = MergeSort(list); // [0,1,2,3,4,5,8,9]
Using more options:
const list = [{a:4,b:'12321'}, {a:1,b:'hi'}, {a:2,b:'9'}];
const sorted = MergeSort(list, {
invert: false, /* inverts the order */
compare: ({a:a1}, {a:a2}) => Math.sign(a1-a2),
/* undefined uses DEFAULT_COMPARE, but can be a custom comparison */
}); // [{a:1,b:'hi'}, {a:2,b:'9'}, {a:4,b:'12321'}]
Import direct:
import QuickSort from './src/quicksort.js';
// equivalent
import {sort} from './src/quicksort.js';
Import from package:
import * as CS from 'cs101';
const QuickSort = CS.QuickSort.sort;
Sorting a list
const list = [5,9,2,4,1,3,0,8];
const sorted = QuickSort(list); // [0,1,2,3,4,5,8,9]
Using more options:
const list = [5,9,2,4,1,3,0,8];
const sorted = QuickSort(list, {
invert: false, /* invert order */
compare: DEFAULT_COMPARE,
pivot: undefined /* standard random pivot. 'mom' uses median of medians algorithm */
/* but throws if list[0] is not a number */
/* 'mom' currently does not work with list items that are not numbers */
}); // [0,1,2,3,4,5,8,9]