TSDS

TypeScript Data Structures that you need!

NPM npm (scoped) npm bundle size (scoped)

Introduction

A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them.

Example:

You may have used Map before, The Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value.

The Map is similar to Object But, The keys in Map are ordered in a simple, straightforward way: A Map object iterates entries, keys, and values in the order of entry insertion.

The Map is builtin in javascript but, There are lots of other useful Data Structures that are not implemented in JavaScript or TypeScript. We attempt to implement them in this library.

Introduction
Installation
APIs
Contributing
Versioning
Authors
License

Installation

To install and save in your package.jsondependencies, run:

npm install @samavati/tsds

BinaryHeap

A Binary Heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the Binary Heap property

BinaryHeap.Properties

BinaryHeap.size

Definition

Gets the number of elements contained in the BinaryHeap<T>.

Property Value

number

Example

const heap = new BinaryHeap<number>();

heap.push(1);
heap.push(2);
heap.push(3);

heap.size // => 3

Remarks

Retrieving the value of this property is an O(1) operation.

BinaryHeap.Methods

BinaryHeap._bubbleDown

Definition

Recursively bubbles down a node if it's in a wrong position

Parameters

startIndexnumber:

BinaryHeap._bubbleUp

Definition

Recursively bubbles up a node if it's in a wrong position

Parameters

startIndexnumber:

BinaryHeap._compareAt

Definition

compares two element at index i and j with provided comparator

Parameters

inumber:

jnumber:

BinaryHeap._compareChildrenOf

Definition

Compares children of a parent

Parameters

parentIndexnumber:

BinaryHeap._getLetChildIndex

Definition

Retrieves the lest child index of the provided parent index

Parameters

indexnumber: The index of the parent.

BinaryHeap._getParentIndex

Definition

Retrieves the parent index of the provided child index

Parameters

indexnumber: The index of the children.

BinaryHeap._getRightChildIndex

Definition

Retrieves the right child index of the provided parent index

Parameters

indexnumber: The index of the parent.

BinaryHeap._hasLeftChild

Definition

Checks if a parent has a left child

Parameters

parentIndexnumber:

BinaryHeap._hasRightChild

Definition

Checks if a parent has a right child

Parameters

parentIndexnumber:

BinaryHeap._shouldSwap

Definition

Checks if parent and child should be swapped

Parameters

parentIndexnumber:

childIndexnumber:

BinaryHeap._swap

Definition

Swaps two nodes in the BinaryHeap

Parameters

inumber:

jnumber:

BinaryHeap.clear

Definition

Clears BinaryHeap<T>.

Example

const heap = new BinaryHeap<number>([10, 15, 20]);

heap.clear();
heap.isEmpty // => true

Remarks

This method is an O(1) operation.

BinaryHeap.isEmpty

Definition

Checks if the BinaryHeap<T> is empty

Example

const heap = new BinaryHeap<number>();

heap.isEmpty // => true

Remarks

This method is an O(1) operation.

BinaryHeap.peek

Definition

Returns the root node in the BinaryHeap

Example

const heap = new BinaryHeap<number>([10, 15, 20]);

heap.peek() // => 20

Remarks

This method is an O(1) operation.

BinaryHeap.pop

Definition

Removes and returns the root node in the BinaryHeap

Example

const heap = new BinaryHeap<number>([10, 15, 20]);

heap.pop() // => 20

Remarks

This method is an O(log n) operation.

BinaryHeap.push

Definition

Inserts a new value into the BinaryHeap

Parameters

valueT: The value that you want to insert into the BinaryHeap

Example

const heap = new BinaryHeap<number>([10, 15, 20]);

heap.push(40)
heap.peek() => // 40

Remarks

This method is an O(log n) operation.

LinkedList

A linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

Usage

import { LinkedList } from '@samavati/tsds';

LinkedList.Properties

LinkedList.first

Definition

Gets the first node of the LinkedList<T>.

Property Value

null | LinkedListNode<T>

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.first // => LinkListNode(1)

Remarks

If the LinkedList<T> is empty, the first and last properties contain null. Retrieving the value of this property is an O(1) operation.

LinkedList.last

Definition

Gets the last node of the LinkedList<T>.

Property Value

null | LinkedListNode<T>

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.last // => LinkListNode(4)

Remarks

If the LinkedList<T> is empty, the first and last properties contain null.

Retrieving the value of this property is an O(1) operation.

LinkedList.length

Definition

Gets the number of nodes actually contained in the LinkedList<T>.

Property Value

number

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.length // => 4

Remarks

Retrieving the value of this property is an O(1) operation.

LinkedList.Methods

LinkedList.[iterator]

Definition

Returns an iterator over the elements contained in this collection. With iterator protocols you are allowed it to be used with the for...of

Example

for (const item of collection) {
    // You have access to the item
}

LinkedList.append

Definition

Adds a new node or value at the end of the LinkedList<T>.

Parameters

valueT: value of the new node.

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.length // => 4
list.append(5)
list.length // => 5
list.last // => LinkListNode(5)

Remarks

This method is an O(1) operation.

LinkedList.clear

Definition

Removes all nodes from the LinkedList<T>.

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.length // => 4
list.clear();
list.length // => 0

LinkedList.delete

Overloads

Variant	Definition
delete(node: LinkedListNode): void	Removes the first occurrence of a node from the `LinkedList<T>`.
delete(value: T): boolean	Removes the first occurrence of the specified value from the `LinkedList<T>`.

delete(node: LinkedListNode): void

Definition

Removes the first occurrence of a node from the LinkedList<T>.

Parameters

nodeLinkedListNode<T>: The LinkedListNode<T> to remove from the LinkedList`. @example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.length // => 4
list.delete(4)
list.length // => 3
list.last // => LinkListNode(3)

@throws {InvalidOperationException} node is not in the current LinkedList<T>.

Remarks

This method is an O(n) operation.

delete(value: T): boolean

Definition

Removes the first occurrence of the specified value from the LinkedList<T>.

Parameters

valueT: The value to remove from the LinkedList<T>.

Returns

boolean

true if the element containing value is successfully removed; otherwise, false. This method also returns false if value was not found in the original LinkedList<T>.

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.length // => 4
list.delete(4)
list.length // => 3
list.last // => LinkListNode(3)

Remarks

This method is an O(n) operation.

LinkedList.deleteFirst

Definition

Removes the node at the start of the LinkedList<T>.

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.length // => 4
list.deleteFirst();
list.length // => 3
list.first // => LinkListNode(2)

Remarks

This method is an O(1) operation.

LinkedList.find

Definition

Finds the first node that contains the specified value.

Parameters

valueT: value of the node we want to find

Returns

null | LinkedListNode<T>

LinkedListNode if there is a value otherwise null

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

const item = list.find(2)

const nullItem = list.find(10) // => null

Remarks

This method is an O(n) operation.

LinkedList.get

Definition

Returns Node at the specified index

Parameters

indexnumber: index of the Node starts from 0

Returns

null | LinkedListNode<T>

LinkedListNode of the specified index, if index is less than length; otherwise, null.

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

const item = list.get(2)

const nullItem = list.get(10) // => null

Remarks

This method is an O(n) operation.

LinkedList.includes

Definition

This implementation iterates over the elements in the collection, checking each element in turn for equality with the specified element.

Parameters

oT:

LinkedList.insertAfter

Overloads

Variant	Definition
insertAfter(node: LinkedListNode, newNode: T): void	Adds a new value after an existing node in the LinkedList.
insertAfter(node: LinkedListNode, newNode: LinkedListNode): void	Adds a new node or after an existing node in the LinkedList.

insertAfter(node: LinkedListNode, newNode: T): void

Definition

Adds a new value after an existing node in the LinkedList.

Parameters

nodeLinkedListNode<T>: The LinkedListNode<T> after which to insert newNode.

newNodeT: The new value to add to the LinkedList<T>.

insertAfter(node: LinkedListNode, newNode: LinkedListNode): void

Definition

Adds a new node or after an existing node in the LinkedList.

Parameters

nodeLinkedListNode<T>: The LinkedListNode<T> after which to insert newNode.

newNodeLinkedListNode<T>: The new LinkedListNode<T> or value to add to the LinkedList<T>.

LinkedList.isEmpty

Definition

This implementation returns length === 0.

LinkedList.isLinkedListNode

Definition

Checks if argument is LinkedListNode or not

Parameters

xany: an argument to check if it is LinkedListNode

Returns

x is LinkedListNode<any>

if argument is LinkedListNode or not

LinkedList.iterator

Definition

LinkedList.prepend

Definition

Appends new Node at the beginning of the LinkedList<T>.

Parameters

valueT: value of the new node

Example

const list = new LinkedList<number>([1, 2, 3, 4]);

list.length // => 4
list.prepend(0)
list.length // => 5
list.first // => LinkListNode(0)

Remarks

This method is an O(1) operation.

LinkedList.toArray

Definition

This implementation returns an array containing all the elements returned by this collection's iterator, in the same order, stored in consecutive elements of the array, starting with index 0. The length of the returned array is equal to the number of elements returned by the iterator, even if the size of this collection changes during iteration, as might happen if the collection permits concurrent modification during iteration. The length property is called only as an optimization hint; the correct result is returned even if the iterator returns a different number of elements.

LinkedListNode

LinkedListNode.Methods

LinkedListNode.isEqual

Parameters

nodeLinkedListNode<any>:

Queue

Represents a first-in, first-out collection of objects.

A queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue.

The operation of adding an element to the rear of the queue is known as enqueue, and the operation of removing an element from the front is known as dequeue.

Usage

import { Queue } from  '@samavati/tsds';

// instantiate new Queue

const queue = new Queue();

Queue.Properties

Queue.length

Definition

Gets the number of elements contained in the Queue<T>.

Property Value

number

Example

const queue = new Queue<number>();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

queue.length // => 3

Remarks

Retrieving the value of this property is an O(1) operation.

Queue.Methods

Queue.[iterator]

Definition

Returns an iterator over the elements contained in this collection. With iterator protocols you are allowed it to be used with the for...of

Example

for (const item of collection) {
    // You have access to the item
}

Queue.clear

Definition

Removes all objects from the Queue<T>.

Example

const queue = new Queue<number>();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

queue.length // => 3
queue.clear()
queue.length // => 0

Queue.dequeue

Definition

Removes and returns the object at the beginning of the Queue<T>.

Returns

T

The object that is removed from the beginning of the Queue<T>.

Example

const queue = new Queue<number>();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

queue.dequeue() // => 3
queue.length // => 2

Remarks

This method is an O(1) operation.

Queue.enqueue

Definition

Adds an object to the end of the Queue<T>.

Parameters

valueT: The object to add to the Queue<T>

Example

const queue = new Queue<number>();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

queue.length // => 3

Remarks

This method is an O(1) operation.

Queue.includes

Definition

This implementation iterates over the elements in the collection, checking each element in turn for equality with the specified element.

Parameters

oT:

Queue.isEmpty

Definition

This implementation returns length === 0.

Queue.iterator

Queue.peek

Definition

Returns the object at the beginning of the Queue<T> without removing it.

Returns

T

The object at the beginning of the Queue<T>.

Example

const queue = new Queue<number>();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

queue.peek() // => 3

Remarks

This method is an O(1) operation.

Queue.toArray

Definition

Stack

Represents a variable size last-in-first-out (LIFO) collection of instances of the same specified type.

A stack is an abstract data type that serves as a collection of elements, with two main principal operations:

Push, which adds an element to the collection, and
Pop, which removes the most recently added element that was not yet removed.

The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out). Additionally, a peek operation may give access to the top without modifying the stack.

Usage

import { Stack } from '@samavati/tsds';
// instantiate new Stack
const stack = new Stack();

Stack.Properties

Stack.length

Definition

Gets the number of elements contained in the Stack<T>.

Property Value

number

Example

const stack = new Stack<number>();

stack.push(1);
stack.push(2);
stack.push(3);

stack.length // => 3

Remarks

Retrieving the value of this property is an O(1) operation.

Stack.Methods

Stack.[iterator]

Definition

Returns an iterator over the elements contained in this collection. With iterator protocols you are allowed it to be used with the for...of

Example

for (const item of collection) {
    // You have access to the item
}

Stack.clear

Definition

Removes all objects from the Stack.

Example

const stack = new Stack<number>();

stack.push(1);
stack.push(2);
stack.push(3);

stack.length // => 3
stack.clear()
stack.length // => 0

Stack.includes

Definition

This implementation iterates over the elements in the collection, checking each element in turn for equality with the specified element.

Parameters

oT:

Stack.isEmpty

Definition

This implementation returns length === 0.

Stack.iterator

Stack.peek

Definition

Returns the object at the top of the Stack without removing it.

Returns

T

The object at the top of the Stack.

Example

const stack = new Stack<number>();

stack.push(1);
stack.push(2);
stack.push(3);

stack.peek() // => 3

Remarks

This method is an O(1) operation.

Stack.pop

Definition

Removes and returns the object at the top of the Stack.

Returns

T

The object removed from the top of the Stack.

Example

const stack = new Stack<number>();

stack.push(1);
stack.push(2);
stack.push(3);

stack.pop() // => 3
stack.length // => 2

Remarks

This method is an O(1) operation.

Stack.push

Definition

Inserts an object at the top of the Stack.

Parameters

valueT: The object to push onto the Stack

Example

const stack = new Stack<number>();

stack.push(1);
stack.push(2);
stack.push(3);

stack.length // => 3

Remarks

This method is an O(1) operation.

Stack.toArray

Definition

Built With

tsdx - Zero-config CLI for TypeScript package development

Contributing

Please do not hesitate to contact me and contribute on this project.

Versioning

We use SemVer for versioning. For the versions available, see the tags on this repository.

Authors

Ehsan Samavati

License

This project is licensed under the MIT License - see the LICENSE.md file for details