sidll.js

What is it?

A Sparse Indexed Doubly Linked List (SIDLL) is a linked list that is linked in both directions and which has indices (or pointers) distributed throughout the list which enables O(k + log p) worst case time complexity for inserts, deletes and lookups where p is the number of the indices/pointers and k is the maximum distance travelled between the pointer and a given node. Sparse distribution gives the user choice to trade-off between lookup times (faster if the interpointer distance is small) and memory (less if the interpointer distance is large).

What can it be used for?

Given that it is always sorted by key, it can be used to keep track of metrics like the streaming mean, median, head/tail as well as min/max (and their associated values).

Installing

npm i sidll

Methods

• insertNode(key,value)
  key: number, value: any javascript data type

• deleteNode(key)
  key: number

• keyExist(key)
  key: number

• getMinKey()

• getMaxKey()

• getMean()

• getMedian()

• getLength()

• head(length)
  length: int (optional)

• tail(length)
  length: int (optional)

• getValue(key,index)
  key: number, index: int (optional)

• setInterpointerDistance(distance)
  distance: int

• setVerbosity(verbosity)
  verbosity: 0: low, 1: medium, 2: high

• _delete()

Example

import { SIDLL } from 'sidll';

const sidll = await SIDLL();
sidll.setInterpointerDistance(20);
sidll.setVerbosity(0);

console.log("Inserting...");
for (var i=0;i<100;i++) {
	sidll.insertNode(i,0);
}

console.log("Median:",sidll.getMedian());
console.log("Mean:",sidll.getMean());
console.log("Length:",sidll.getLength());
console.log("Head:",sidll.head(20));
console.log("Tail:",sidll.tail(20));

console.log("Deleting...");
for (var i=100;i>=0;i--) {
	sidll.deleteNode(i);
}

console.log("Median:",sidll.getMedian());
console.log("Mean:",sidll.getMean());
console.log("Length:",sidll.getLength());
console.log("Head:",sidll.head(20));
console.log("Tail:",sidll.tail(20));

sidll._delete();

Important: Don't forget to delete once completed to free up memory.

Languages

Also available for Python at PyPI.

Change log

Version 0.0.2: Initial release