cs.js

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.

Todo

• LinkedHashMap - good for LRU (get it? back-to-front URL?) caches, etc

Contents

Click links below to go straight to the code :sparkles: for each structure or algorithm;

Or jump straight to the API documentation.

List Structures

• [x] Singly-linked list - O(1) (access first) O(n) (insert, delete, update, find), O(n) space list
• [x] Doubly-linked list - O(1) (reversal, access first or last) O(n) (insert, delete, update, find), O(n) space, traversable in forward or reverse list
• [x] Self-organizing list O(weird) access-adapting (move to front or advance) list for faster access, good for cache and easy Least-Recently-Used eviction (pop off end)

Tree Structures

• [x] n-ary Tree - any-arity tree structure, good as a basis for other tree structures and algorithms utilizing trees
• [x] Heap - O(1) (find top) O(log n) (insert, delete, update), O(n) (heapify), O(n) space partially ordered stack of things, good for leaderboard
• [x] Priority queue - O(1) (find top) O(log n) (insert, delete, update), O(n) (heapify), O(n) space stack of thing, priority pairs partially ordered by their priorities, good for job scheduling
• [x] Trie - O(k) (insert, delete, update) O(n) trie-ify O(n) space tree of a list of sequences (commonly strings), good for full-text search

Hybrid Tree/List Structures

• [x] Skiplist - O(log n) (insert, delete, update, find (by key), find (by index)), O(n log n) skiplistify, O(n) to O(n log n) space sorted randomized list, with hybrid list/tree express lanes for fast access, very cool and efficient rare O(n) worst case performance for insert, delete, update, find by key and find by index from bad random express-lane stops, good for associative maps and anything really

Seeking Algorithms

• [x] BinarySearch - O(log n) Find an item and its index in a sorted array, good for looking up books by title from an ordered list, or finding the slot to insert a new book
• [x] QuickSelect - O(N) Find the nth-orderd item in an unordered array, good for "who came 1st (or k-th)" questions

Sorting Algorithms

• [x] InsertionSort - O(n**2) (no binary search), O(n log n) (with binary search), O(n) (already sorted)
• [x] SelectionSort - O(n**2) (no binary search), O(n**2) (already sorted) normally slower than insertion because it has to search all of unsorted tail each time, while insertion only has to search until it finds the insertion slot in the sorted head, which is often not the entire length of the sorted head.
• [x] MergeSort - O(n log n) (every case) O(n) space stable sort, divide and conquer, merging
• [x] QuickSort - O(n**2) (worst case of bad pivots) O(n log n) O(1) space non-stable in-place sort, divide and conquer, partitioning on pivot, bad pivots can lead to quadratic performance.

Getting and testing

Get for use:

$ npm i --save cs101

Get to run tests and modify:

1. Fork and repo, clone your copy
2. Change to directory, and install dependencies:

$ cd cs.js
$ npm i 

3. Run tests in Node

$ npm test

4. Run tests in browser:

$ 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

API Documentation

Contents

• List structures
  • Singly-linked list
  • Doubly-linked list
  • Self-organizing list
• Tree structures
  • N-ary Tree
  • Heap
  • Priority queue
  • Trie
• Hybrid list/tree structures
  • Skiplist
• Seeking algorithms
  • Binary search
  • Quick Select
• Sorting algorithms
  • Insertion sort
  • Selection sort
  • Merge sort
  • Quick sort

---

Singly-linked list

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

Doubly-linked list

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

Self-organizing list

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: