@mangos/linked-list
v1.0.2
Published
single-linked-list
Downloads
9
Readme
List
A double linked list library. Fast and small no external dependencies
LICENSE MIT
npm i @mangos/linked-list
- 1.1. Utility functions
from
andvalue
- 1.2.
insertAfter
- 1.3.
insertBefore
- 1.4.
first
- 1.5.
last
- 1.6.
countFrom
- 1.7.
splice
- 1.8.
toArr
- 1.1. Utility functions
1. API
The linked list (List<T>
) is a chain of individual items Item<T>
An Item
type is just a narrowed List
type
The typedecl of an List:
type List<T> = null | { // list can have no items, in that case they have the value null
prev: List<T>; // prev item in the list
next: List<T>; // next item in the list
value: T; // value wrapped by this list element
};
an Element is a a List<T>
but narrowed, null
value excluded
type Item<T> = Exclude<List<T>, null>;
1.1. Utility functions from
and value
Although you can create the list js objects manually there are 2 utility functions to help wrap a value in a list item or to extract a value from a list item:
1.1.1. from
Wrapping a value in a List item:
const item = from({ firstName:'John', lastName: 'Smith' });
// item can be a root of a linked list
1.1.2. value
Exctracting a value from a list item:
const item = from({ firstName: 'John', lastName: 'Smith' });
const actual = value(item);
// -> will return reference to { firstName:'John', lastName: 'Smith' }
1.2. insertAfter
Peformance: O(1)
Add an element item
right after the element pointed to by list
(list
is a superset of item
).
What is returned is the newly added item
integrated into the list
.
decl:
function insertAfter<T>(list: List<T>, item: Item<T>): List<T>;
Example:
let root = from(1); // list with 1 element
insertAfter(root, from(2));
// "2" will be inserted after "1"
insertAfter(root, from(3));
// "3" will be inserted after "1" and before "2"
1.3. insertBefore
Performance: O(1)
Add an element item
right before the element pointed to by list
(list
is a superset of item
).
What is returned is the newly added item
integrated into the list
.
decl:
function insertBefore<T>(list: List<T>, item: Item<T>): List<T>;
Example:
const root = from(1); // list with 1 element, root points to element "1"
const root2 = insertBefore(root, from(2)); // "2" will be before before "1" and become the new root of the list
// NB: root still points to element "1"
// NB: root2 points to element "2"
const elt3 = insertBefore(root, from(3)); // "3" will be inserted before before "1" and after "2"
1.4. first
Find the first element in a linked list by walking back from the element you passed to first
function.
Performance: O(n)
decl:
function first<T>(list: List<T>): List<T>;
Example:
let root = from(3);
const obj3 = root; // remember reference to "3"
root = insertBefore(root, from(2));
root = insertBofere(root, from(1));
const start = first(obj3);
// start will have the same refere"nce to "1" an as root;
first(null);
// will return null;
1.5. last
Performance: O(n)
Find the last element in a linked list by walking forward from the element you passed to last
function.
decl:
function last<T>(list: List<T>): List<T>;
Example:
let root = from(3);
root = insertBefore(root, from(2));
const obj2 = root; // keep reference to "root"
root = insertBofere(root, from(1));
const end = last(obj2);
// end will point to "3"
const end2 = last(root);
// end2 will point to "3"
last(null);
// will return null
1.6. countFrom
Performance: O(n)
Count the number of elements in the linked list starting from the position passed as argument to countFrom
decl:
function countFrom<T>(list: List<T>): number;
Example:
let root = from(3);
root = insertBefore(root, from(2));
const obj2 = root; // keep reference to "root"
root = insertBofere(root, from(1));
countFrom(root); // will count 3 elements
countFrom(obj2); // will count 2 elements
conntFrom(null); // will count 0 elements
1.7. splice
Slice a List
into 2 Lists at the point of Item
reference.
decl:
function splice<T>(item: Item<T> | List<T>): List<T>;
- splits all elements
item
and above to a new list withitem
as the root of the new list. - the ref pointed to by
item.prev
will be last item in the previous list.
Example:
const root1 = from(1);
const itm2 = from(2);
const itm3 = from(3);
const itm4 = from(4);
insertAfter(root1, itm2);
insertAfter(itm2, itm3);
insertAfter(itm3, itm4);
// now we have a sequence "1" , "2", "3", "4", where "1" is the root
const root2 = splice(itm3);
// root2 will be the sequence "3" , "4"
// root1 will be the sequence "1", "2"
1.8. toArr
Convert the List to an javascript Array.
decl:
export function toArr<T>(list: List<T>, take: number = Number.POSITIVE_INFINITY ): T[]
take
is optional second argument, it takes all linked element value's above the list element refeenced by list
.
Example:
const root1 = from(1);
const itm2 = from(2);
const itm3 = from(3);
const itm4 = from(4);
insertAfter(root1, itm2);
insertAfter(itm2, itm3);
insertAfter(itm3, itm4);
// now we have a sequence "1" , "2", "3", "4", where "1" is the root
toArr(root1, 2);
// -> will return array [1,2]
toArr(root1);
// -> will return array [1,2,3,4]
toArr(itm3);
// -> will return array [3,4]