✌️🔗📝 doubly-linked-list

A zero-dependency TypeScript library to work with doubly linked lists and arrays of any types.

Table of Content

• ✌️🔗📝 doubly-linked-list
  • Table of Content
  • Installation
  • Usage
  • Documentation
    • toDLL
    • unshift, insert, push
    • shift, remove, pop
    • sort
    • map
    • reduce
    • findOne, findMany
    • find(Gt/Gte/Lt/Lte)
    • traverse
    • toArray
    • hasNodes, hasPrev, hasNext
    • makeCompareUtils
    • The infamous DoublyLinkedList class

Installation

yarn add @romainfieve/doubly-linked-list

or

npm install @romainfieve/doubly-linked-list

Usage

type Hero = { name: string };

const compareAlpha = (a: Hero, b: Hero) => a.name.localeCompare(b.name);

const insertAlpha = makeInsert(compareAlpha);
const removeAlpha = makeRemove(compareAlpha);
const findOneAlpha = makeFindOne(compareAlpha);

const heroes: Hero[] = [
    { name: 'Han' },
    { name: 'Anakin' },
    { name: 'Leia' },
    { name: 'Luke' },
    { name: 'Padme' },
    { name: 'Lando' },
    { name: 'Chewie' },
];

const list = toDLL(heroes, compareAlpha);

// Schema of "list"
// Anakin <-> Chewie <-> Han <-> Lando <-> Leia <-> Luke <-> Padme

const updatedList = pipe(
    (t) => insertAlpha(t, { name: 'Obiwan' }),
    (t) => insertAlpha(t, [{ name: 'Boba' }, { name: 'Grogu' }]),
    (t) => push(t, { name: 'Vador' }),
    (t) => removeAlpha(t, [{ name: 'Han' }, { name: 'Padme' }]),
    (t) => removeAlpha(t, { name: 'Luke' })
)(list);

// Schema of "updatedList"
// Anakin <-> Boba <-> Chewie <-> Grogu <-> Lando <-> Leia <-> Obiwan <-> Vador

const grogu = findOneAlpha(updatedList, { name: 'Grogu' }); // { data: 'Grogu', next: ..., prev: ...}

Documentation

toDLL

Converts the given array to a doubly linked list (toDLL), depending on a given compare function if provided.

const arr = [10, 32, 13, 2, 89, 5, 50];
const compare = (a: number, b: number) => a - b;

const list = toDLL(arr, compare);
// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const unorderedList = toDLL(arr);
// Schema of "unorderedList"
// 10 <-> 32 <-> 13 <-> 2 <-> 89 <-> 5 <-> 50

unshift, insert, push

Inserts a (or list of) given node(s) to the given doubly linked list (in place) and returns the list.

• with the given compare function (insert)
• at the head (unshift)
• at the tail (push)

:warning: Using another compare function than the one used to create the list with toDLL or using push/unshift will of course f**k up the sorting. A safer approach consists of using makeInsert. It curries an insert closure function with the given compare function.

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const a = insert(list, 11, compare);
// 2 <-> 5 <-> 10 <-> 11 <-> 13 <-> 32 <-> 50 <-> 89
const b = insert(list, [1, 100], compare);
// 1 <-> 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89 <-> 100
const c = push(list, [3, 17]);
// 1 <-> 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89 <-> 100 <-> 3 <-> 17
const d = unshift(list, 7);
// 7 <-> 1 <-> 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89 <-> 100 <-> 3 <-> 17

shift, remove, pop

Removes a (or list of) given node(s) from the given doubly linked list (in place) with the given compare function and returns the list.

• with the given compare function (remove)
• at the head (shift)
• at the tail (pop)

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const a = remove(list, 13, compare);
// 2 <-> 5 <-> 10 <-> 32 <-> 50 <-> 89
const b = remove(list, [2, 89], compare);
// 5 <-> 10 <-> 32 <-> 50
const c = shift(list);
// 10 <-> 32 <-> 50
const d = pop(list);
// 10 <-> 32

sort

Sorts a doubly linked list with the given compare function and returns the new list.

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const reversed = sort(list, (a: number, b: number) => b - a);
// 89 <-> 50 <-> 32 <-> 13 <-> 10 <-> 5 <-> 2
const ordered = sort(reversed, (a: number, b: number) => a - b);
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

map

Maps the given doubly linked list nodes' data to anything.

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const mapper = (node: DLLNode, index: number) => `${node.data}[${index}]`;
const a = map(list, mapper);
// '2[0]' <-> '5[1]' <-> '10[2]' <-> '13[3]' <-> '32[4]' <-> '50[5]' <-> '89[6]'

reduce

Reduces the given doubly linked list to anything.

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const reducer = (acc: number, node: DLLNode, index: number) => acc + node.data + index;
const a = reduce(list, reducer, 0); // 222

findOne, findMany

Finds the first (findOne) or all (findMany) the matching node(s) into the given doubly linked list with the given compare function.

// This compare function will capture the elements that, when compared with the searched one,
// will be in range of x - 5 to x + 5.
const compare = (a: number, b: number) => {
    if (a > b + 5) {
        return 1;
    }
    if (a < b - 5) {
        return -1;
    }
    return 0;
};

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const node = findOne(list, compare, 12)?.data; // 10
const nodes = findMany(list, compare, 12).map(({ data }) => data); // [ 10, 13 ]

find(Gt/Gte/Lt/Lte)

Finds all gt/gte/lt/lte nodes into the given doubly linked list with the given compare function.

• findGt
• findGte
• findLt
• findLte

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const results = findGte(list, compare, 13).map(({ data }) => data);
// [13, 32, 50, 89]

traverse

Traverses a doubly linked list, invoking the callback function on each visited node:

• traverseFrom
• traverseInOrder
• traverseInOrderReverse

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const collect = (collection: number[]) => (node: { data: number }) => {
    collection.push(node.data);
};

const elements = [];

traverseFrom(list.head, 'next', collect(elements));
// elements: [2, 5, 10, 13, 32, 50, 89]
traverseInOrder(list, collect(elements));
// elements: [2, 5, 10, 13, 32, 50, 89]
traverseInOrderReverse(list, collect(elements));
// elements: [89, 50, 32, 13, 10, 5, 2]

toArray

Converts the given doubly linked list to an array sorted as traversed, with an optional mapper:

• toArrayInOrder
• toArrayInOrderReverse
• toArrayMapInOrder
• toArrayMapInOrderReverse

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const a = toArrayInOrder(list);
// [2, 5, 10, 13, 32, 50, 89]
const b = toArrayInOrderReverse(list);
// [89, 50, 32, 13, 10, 5, 2]

const mapper = (node: DLLNode, index: number) => node.data * index;
const c = toArrayMapInOrder(list, mapper);
// [0, 5, 20, 39, 128, 250, 534]

hasNodes, hasPrev, hasNext

Assesses if the list contains nodes hasNodes. Assesses if the given node has a prev node (hasPrev) or a next node (hasNext).

// Schema of "list"
// 2 <-> 5 <-> 10 <-> 13 <-> 32 <-> 50 <-> 89

const isNonEmpty = hasNodes(list); // true

const hasPrevA = hasPrev(list.tail); // true
const hasPrevB = hasPrev(list.head); // false

const hasNextA = hasNext(list.head); // true
const hasNextB = hasNext(list.tail); // false

makeCompareUtils

As the compare function is centric, for both the creation and the traversals of the DLL, a good practice is to create all the necessary utils, along with it. This will be DRY and ensure reusability and consistency.

// compare-alpha.ts
export const compareAlpha = (a: Hero, b: Hero) => a.name.localeCompare(b.name);
export const {
    toDLL: toDLLAlpha,
    insert: insertAlpha,
    remove: removeAlpha,
    sort: sortAlpha,
    findOne: findOneAlpha,
    findMany: findManyAlpha,
    findGt: findGtAlpha,
    findGte: findGteAlpha,
    findLt: findLtAlpha,
    findLte: findLteAlpha,
} = makeCompareUtils(compareAlpha);

// other-file.ts
import {
    toDLLAlpha,
    insertAlpha,
    removeAlpha,
    sortAlpha,
    findOneAlpha,
    findManyAlpha,
    findGtAlpha,
    findGteAlpha,
    findLtAlpha,
    findLteAlpha,
} from './compare-alpha';

const list = toDLLAlpha([{ name: 'Anakin' }]);

const updatedList = pipe(
    (t) => insertAlpha(t, { name: 'Yoda' }),
    (t) => removeAlpha(t, { name: 'Anakin' }),
    (t) => findGteAlpha({ name: 'Yoda' })
)(list); // [{ data: 'Yoda' }]

The infamous DoublyLinkedList class

While diverging from the functional approach, the DoublyLinkedList class offers many advantages, depending on the situation:

Pros:

• Natural chaining
• List state encapsulation
• Compare function encapsulation
• Has all methods listed as functions before

Cons:

• No tree shaking of unused methods, obviously

Let's rewrite the Star Wars example with this approach:

type Hero = { name: string };

const compareAlpha = (a: Hero, b: Hero) => a.name.localeCompare(b.name);

const heroes: Hero[] = [
    { name: 'Han' },
    { name: 'Anakin' },
    { name: 'Leia' },
    { name: 'Luke' },
    { name: 'Padme' },
    { name: 'Lando' },
    { name: 'Chewie' },
];

const list = new DoublyLinkedList(heroes, compareAlpha);
// Schema of list.list
// Anakin <-> Chewie <-> Han <-> Lando <-> Leia <-> Luke <-> Padme

list.insert({ name: 'Yoda' })
    .insert({ name: 'Obiwan' })
    .insert([{ name: 'Boba' }, { name: 'Grogu' }])
    .push({ name: 'Vador' })
    .remove([{ name: 'Han' }, { name: 'Padme' }])
    .remove({ name: 'Luke' });

// Schema of list.list, after update
// Anakin <-> Boba <-> Chewie <-> Grogu <-> Lando <-> Leia <-> Obiwan <-> Yoda <-> Vador