Singlie

<h1 align="center"> Singlie </h1> <h4 align="center"> Singly circular and linear linked lists </h4>

Description

TypeScript implementation of singly circular and linear linked list data-structures with comprehensive property-based test coverage

The codebase uses zero production dependencies and it weights ~1 kB minified and gzipped.

Visit the contributing guidelines to learn more on how to translate this document into more languages.

Status

<div style="display: inline-flex; gap: 8px; flex-wrap: wrap;">

<a href="https://github.com/klaudiosinani/singlie/actions/workflows/ci.yml"><img alt="CI" src="https://github.com/klaudiosinani/singlie/actions/workflows/ci.yml/badge.svg"></a> <a href="https://github.com/klaudiosinani/singlie/actions/workflows/cd.yml"><img alt="CD" src="https://github.com/klaudiosinani/singlie/actions/workflows/cd.yml/badge.svg"></a> <a href="https://codecov.io/gh/klaudiosinani/singlie"><img alt="Coverage" src="https://codecov.io/gh/klaudiosinani/singlie/graph/badge.svg?token=2S1ZWC7ALX"></a> <a href="https://github.com/klaudiosinani/singlie/releases"><img alt="GitHub Release" src="https://img.shields.io/github/v/release/klaudiosinani/singlie?label=Lastest%20Version&color=%2332C955"></a> <a href="https://doi.org/10.5281/zenodo.17563627"><img alt="DOI" src="https://img.shields.io/badge/Digital%20Object%20Identifier-10.5281%2Fzenodo.17563627-%2332C955?style=flat"></a>

</div>

Contents

• Description
• Status
• Install
• Usage
• In Depth
• API
• Development
• Related
• Team
• Citations
• License

Install

npm install singlie

Usage

Singlie exposes a fluent API that can be utilized through a simple and minimal syntax, allowing you to combine methods effectively.

Usage examples can be also found at the test directory.

import {Circular, Linear} from 'singlie';

const linear = new Linear<string>();
linear.prepend('A').append('B');
linear.head;
// => Node { value: 'A', next: Node { value: 'B', next: null } }
linear.head.next;
// => Node { value: 'B', next: null }
linear.head.next.next;
// => null
linear.map(x => `[${x}]`).reverse().join(' -> ');
// => [B] -> [A]

const circular = new Circular<string>();
circular.append('B').prepend('A');
circular.head;
// => Node { value: 'A', next: Node { value: 'B', next: [Circular] } }
circular.head.next;
// => Node { value: 'B', next: Node { value: 'A', next: [Circular] } }
circular.head.next.next;
// => Node { value: 'A', next: Node { value: 'B', next: [Circular] } }
circular.map(x => `[${x}]`).reverse().toArray();
// => [ '[B]', '[A]' ]

In Depth

Linear Singly Linked List

Linear singly linked lists can contain multiple nodes, where each node has only a value and a next attribute. The value attribute holds the value stored inside the node, and the next attribute points to the next node in line. The only exception, is that the last node of the list has null stored to its next attribute, which indicates the lack of further nodes down the line, thus the end of the list. The following example demonstrates the operations that can be performed on any linear singly linked list.

import {Linear} from 'singlie';

const linear = new Linear<string>();

// Append a node holding the value `E`
linear.append('E');
linear.head; // => Node { value: 'E', next: null }
linear.last; // => Node { value: 'E', next: null }
linear.get(0); // => E

// Return the node corresponding to the index
linear.node(0); // => Node { value: 'E', next: null }
linear.node(0).value; // => E
linear.node(0).next; // => null

// Append multiple nodes at once
linear.append('F', 'G');
linear.length; // => 3
linear.node(0).next.value; // => F
linear.node(0).next.next.value; // => G
linear.toArray(); // => [ 'E', 'F', 'G' ]

// Prepend multiple nodes at once
linear.prepend('B', 'A');
linear.join(' '); // => A B E F G

// Insert multiple nodes to the given index
linear.insert({value: ['D', 'C', 'X'], index: 2});
linear.join(' '); // => A B X C D E F G

// Remove the node corresponding to the index
linear.remove(2);
linear.join(' '); // => A B C D E F G

// Update the value of the node corresponding to the index
linear.node(linear.length - 1).value = '!';
linear.join(' '); // => A B C D E F !
linear.set({value: 'G', index: linear.length - 1});
linear.join(' '); // => A B C D E F G

// Iterate over the list
const array: string[] = [];
linear.forEach(x => array.push(x));
console.log(array);
// => [ 'A', 'B', 'C', 'D', 'E', 'F', 'G' ]

// Chain multiple methods
linear.reverse().map(x => `[${x}]`).join('->');
// => [G]->[F]->[E]->[D]->[C]->[B]->[A]

// Clear the list
linear.clear(); // => Linear { head: null, length: 0 }

Circular Singly Linked List

Circular singly linked lists can also contain multiple nodes, where again each node has the same value and next attributes. The only difference compared to linear lists is that the last node always points back to the first node / head of the list, thus the list is said to be circular or circularly linked. The following example demonstrates the operations that can be performed on any circular singly linked list.

import {Circular} from 'singlie';

const circular = new Circular<string>();

// Append a node holding the value `E`
circular.append('E');
circular.head; // => Node { value: 'E', next: [Circular] }
circular.last; // => Node { value: 'E', next: [Circular] }
circular.get(0); // => E

// Return the node corresponding to the index
circular.node(0); // => Node { value: 'E', next: [Circular] }
circular.node(0).value; // => E
circular.node(0).next.value; // => E
circular.node(0).next.next.value; // => E

// Append multiple nodes at once
circular.append('F', 'G');
circular.length; // => 3
circular.node(0).next.value; // => F
circular.node(0).next.next.value; // => G
circular.node(0).next.next.next.value; // => E
circular.toArray(); // => [ 'E', 'F', 'G' ]

// Prepend multiple nodes at once
circular.prepend('B', 'A');
circular.join(' '); // => A B E F G

// Insert multiple nodes to the given index
circular.insert({value: ['D', 'C', 'X'], index: 2});
circular.join(' '); // => A B X C D E F G

// Remove the node corresponding to the index
circular.remove(2);
circular.join(' '); // => A B C D E F G

// Update the value of the node corresponding to the index
circular.node(circular.length - 1).value = '!';
circular.join(' '); // => A B C D E F !
circular.set({value: 'G', index: circular.length - 1});
circular.join(' '); // => A B C D E F G

// Iterate over the list
const array: string[] = [];
circular.forEach(x => array.push(x));
console.log(array);
// => [ 'A', 'B', 'C', 'D', 'E', 'F', 'G' ]

// Chain multiple methods
circular.reverse().map(x => `[${x}]`).join('->');
// => [G]->[F]->[E]->[D]->[C]->[B]->[A]

// Clear the list
circular.clear(); // => Circular { head: null, length: 0 }

API

The following documentation holds for both circular and linear lists. The described list instance is used to depict the same methods that are applicable to both a linear and a circular linked list, without overlooking their above-described differences and unique qualities.

list.append(value[, value])

• Return Type: Linked List

Appends one of more nodes to the list.

value

• Type: any

Can be one or more comma-delimited values. Each value corresponds to a single node.

list.append('A', 'B', 'C', 'D');
// => { value: 'A', next: { value: 'B', next: [List] } }

list.prepend(value[, value])

• Return Type: Linked List

Prepends one of more nodes to the list.

value

• Type: any

Can be one or more comma-delimited values. Each value corresponds to a single node.

list.append('C', 'D');
// => { value: 'C', next: [List] }
list.prepend('B', 'A');
// => { value: 'A', next: { value: 'B', next: { value: 'C', next: [List] } } }

list.head

• Return Type: Node | null

Returns the first node / head on the list.

list.append('A', 'B');
list.head;
// => Node { value: 'A', next: [Node] }

list.last

• Return Type: Node | null

Returns the last node on the list.

list.append('A', 'B');
list.last;
// => Node { value: 'B', next: [Node] }

list.length

• Return Type: Integer

Returns the length of the list.

list.append('A', 'B');
list.length;
// => 2

list.isEmpty()

• Return Type: Boolean

Checks whether the list is empty.

list.append('A', 'B');
list.isEmpty();
// => false

list.insert({value[, value], index})

• Return Type: Linked List

Inserts one or more nodes to the given index.

value

• Type: any

Can be one or more comma-delimited values. Each value corresponds to a single node.

index

• Type: Integer

Can be an integer corresponding to a list index.

list.append('A', 'B', 'E');
list.insert({value: ['C', 'D'], index: 1});
// => { value: 'A', next: { value: 'D', next: { value: 'C', next: { value: 'B', next: [List] } } } }

list.node(index)

• Return Type: Node

Return the node corresponding to the given index.

index

• Type: Integer

Can be an integer corresponding to a list index.

list.append('A', 'B', 'C', 'D');
const node = list.node(0);
// => { value: 'A', next: { value: 'B', next: [List] } }
node.value;
// => A
node.next;
// => { value: 'B', next: [List] }

list.get(index)

• Return Type: any

Return the value of the node corresponding to the given index.

index

• Type: Integer

Can be an integer corresponding to a list index.

list.append('A', 'B');

list.g