TSDS
TypeScript Data Structures that you need!
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.
Table of Contents
Installation
To install and save in your package.jsondependencies, run:
npm install @samavati/tsds
APIs
LinkedList
A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.
Usage
import { LinkedList } from '@samavati/tsds';
// instantiate new linked list without initial set-up
const list = new LinkedList();
// instantiate new linked list with initial values
const list2 = new LinkedList([1, 2, 3, 4, 5]);
The list supports iterator protocols allowing it to be used with the for...of
import { LinkedList } from '@samavati/tsds';
const list = new LinkedList([1, 2, 3]);
for (let item of list) {
console.log(item)
}
// 1
// 2
// 3
LinkedList.Properties
LinkedList.first
Definition
Gets the first node of the LinkedList.
Property Value
LinkedListNode
The first LinkedListNode of the LinkedList.
Example
const list = new LinkedList<number>([1, 2, 3, 4]);
list.first // => LinkListNode(1)
Remarks
If the LinkedList 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.
Property Value
LinkedListNode
The last LinkedListNode of the LinkedList.
Example
const list = new LinkedList<number>([1, 2, 3, 4]);
list.last // => LinkListNode(4)
Remarks
If the LinkedList 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.
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.append
Definition
Adds a new node or value at the end of the LinkedList.
Parameters
value T: The new value to add at the end of the LinkedList.
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.
Example
const list = new LinkedList<number>([1, 2, 3, 4]);
list.length // => 4
list.clear();
list.length // => 0
LinkedList.delete
Definition
Removes the first occurrence of a node or value 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)
Remarks
This method is an O(n) operation.
LinkedList.deleteFirst
Definition
Removes the node at the start of the LinkedList.
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
value T: The value to locate in the LinkedList.
Returns
The first LinkedListNode that contains the specified value, if found; 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
index number: index of the Node starts, from 0
Returns
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
Determines whether a value is in the LinkedList.
Parameters
value T: The value to locate in the LinkedList.
Returns
boolean
true if value is found in the LinkedList; otherwise, false.
Example
const list = new LinkedList<number>([1, 2, 3, 4]);
list.includes(2) // => true
list.includes(10) // => false
Remarks
This method is an O(n) operation.
LinkedList.insertAfter
Definition
Adds a new node or value after an existing node in the LinkedList.
Example
const list = new LinkedList<number>([1, 2, 3, 4]);
const item = list.get(2);
if (item) {
list.insertAfter(item, 'hello');
const world = new LinkedListNode('world');
list.insertAfter(item, world);
}
Remarks
This method is an O(1) operation.
LinkedList.prepend
Definition
Adds a new node or value at the start of the LinkedList.
Parameters
value T: The new value to add at the start of the LinkedList.
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
Returns the entire LinkedList to a compatible one-dimensional Array
Example
const list = new LinkedList<number>([1, 2, 3, 4]);
list.prepend(0)
list.toArray() // => [0, 1, 2, 3, 4]
Remarks
This method is an O(n) operation.
Stack
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();
The stack supports iterator protocols allowing it to be used with the for...of
import { Stack } from '@samavati/tsds';
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
for (const item of stack) {
console.log(item)
}
// 3
// 2
// 1
Stack.Properties
Stack.length
Definition
Gets the number of elements contained in the Stack.
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.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
Determines whether an element is in the Stack.
Parameters
**item T**The object to locate in the Stack.
Returns
boolean
true if item is found in the Stack; otherwise, false.
Example
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.includes(2) // => true
stack.includes(10) // => false
Remarks
This method is an O(n) operation.
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 at 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
value T: 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
Returns the entire Stack to a compatible one-dimensional Array
Example
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.toArray() // => [3, 2, 1]
Remarks
This method is an O(n) operation.
Queue
first-in-first-out (FIFO) data structure
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();
The queue supports iterator protocols allowing it to be used with the for...of
import { Queue } from '@samavati/tsds';
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
for (const item of queue) {
console.log(item)
}
// 1
// 2
// 3
Queue.Properties
Queue.length
Definition
Gets the number of elements contained in the Queue.
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.clear
Definition
Removes all objects from the Queue.
Example
const queue = new Queue<number>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.length // => 3
queue.clear()
queue.length // => 0
Queue.includes
Definition
Determines whether an element is in the Queue.
Parameters
**item T**The object to locate in the Queue.
Returns
boolean
true if item is found in the Queue; otherwise, false.
Example
const queue = new Queue<number>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.includes(2) // => true
queue.includes(10) // => false
Remarks
This method is an O(n) operation.
Queue.dequeue
Definition
Removes and returns the object at the beginning of the Queue
Returns
T
The object at the beginning of the Queue.
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
Inserts an object at the end of the Queue.
Parameters
value T: The object to add to the Queue.
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.peek
Definition
Returns the object at the beginning of the Stack without removing it.
Returns
T
The object at the beginning of the Queue.
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
Returns the entire Queue to a compatible one-dimensional Array
Example
const queue = new Queue<number>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.toArray() // => [3, 2, 1]
Remarks
This method is an O(n) operation.
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
License
This project is licensed under the MIT License - see the LICENSE.md file for details
49 Oct 24, 2022
22 Dec 4, 2022
2 Jan 10, 2022
11 Dec 28, 2022
43 Jan 2, 2023
34 Dec 23, 2022
2 Apr 15, 2022
29 Dec 30, 2022
162 Jan 3, 2023
4k Dec 29, 2022