Data Structure in Typescript
In this topic we will understand what Data Structure is in Typescript
Introduction
- Data structures are fundamental building blocks that organize and store data in memory. They play a vital role in algorithms, ensuring data manipulation, retrieval, and storage are performed as efficiently as possible.
Typescript
- TypeScript is a free and open-source high-level programming language developed by Microsoft that adds static typing with optional type annotations to JavaScript. It is designed for the development of large applications and transpiles to JavaScript.
Data Structures to Cover
Arrays
Definition:
- In TypeScript, an array is a data structure that stores several values of the same type in a single variable. For instance, you can have an array of strings, numbers, or even objects. The array type is, in fact, a built-in data type in TypeScript, which makes it easy to declare and manipulate arrays.
Key Features:
An array declaration allocates sequential memory blocks.
Array elements are identified by a unique integer called as the subscript / index of the element.
Like variables, arrays too, should be declared before they are used. Use the var keyword to declare an array.
Use Cases:
A collection of data like product IDs, user names, or a list of options in a form.
Displaying lists of items in a UI, processing data in bulk, or filtering data.
Performing operations such as mapping, sorting, or reducing data into summary information.
Time Complexity:
Accessing an Element by Index
Time Complexity: O(1)
Reason: Arrays provide constant-time access to elements when you know the index. The element is located directly by index.
Inserting an Element at the End (
push())Time Complexity: O(1) (amortized)
Reason: If there’s enough space in the array, the operation is constant time. However, if the array needs to resize (i.e., allocate more memory), this can take longer, but it happens infrequently.
Inserting an Element at the Beginning (
unshift())Time Complexity: O(n)
Reason: All the existing elements have to be shifted by one to accommodate the new element at the beginning.
Inserting an Element in the Middle
Time Complexity: O(n)
Reason: Inserting at any position requires shifting the elements after the insertion point to make space for the new element.
Removing an Element from the End (pop())
Time Complexity: O(1)
Reason: Removing the last element doesn’t require shifting any other elements.
Removing an Element from the Beginning (shift())
Time Complexity: O(n)
Reason: Similar to
unshift(), removing the first element requires shifting all other elements to fill the gap.
Removing an Element from the Middle
Time Complexity: O(n)
Reason: Elements after the removed element must be shifted to close the gap.
Searching for an Element (indexOf(), find(), etc.)
Time Complexity: O(n)
Reason: The array must be searched element by element in the worst case.
Sorting the Array (sort())
Time Complexity: O(n log n)
Reason: Most efficient sorting algorithms (like Timsort, which is used in JavaScript’s
sort()) have a time complexity of O(n log n).
Concatenating Two Arrays (concat())
Time Complexity: O(n)
Reason: All elements from both arrays need to be copied into a new array.
Example Code in TypeScript:
let numbers: number[] = [1, 2, 3, 4, 5];
let names: string[] = ["Chou", "Ling", "Hayabusa"];
console.log(numbers[2]);
console.log(names[2]);
Tuple
Definition:
- A tuple is a type in TypeScript that is used to represent an array in which the type of a fixed number of elements is known, but not for all the elements. It provides a way to represent the ordered set of the element types for certain elements in a TypeScript array.
Key Features:
Unlike regular arrays, tuples have a fixed number of elements, meaning you know exactly how many values the tuple will contain.
Tuples allow you to define different types for each element. Each position in a tuple can have its own type, ensuring strict type safety.
You can access tuple elements using index positions just like arrays. TypeScript ensures that the type is correctly inferred based on the element's position.
Use Cases:
Tuples are ideal when you need an array with a known number of elements where each element can have a different type. For instance, you might want a pair of a string and a number
When a function needs to return multiple values of different types, tuples can be used to structure the return type in a meaningful way
Tuples can also be used in function parameters when you expect arguments with different types
Time Complexity:
Access by index:
Time complexity: O(1)
Explanation: Accessing an element in a tuple by its index is a constant-time operation since tuples (like arrays) allow direct access to elements by their index.
Search (linear):
Time complexity: O(n)
Explanation: Searching for a specific value in a tuple involves checking each element, leading to a linear time complexity based on the size of the tuple.
Insertion at the end (push operation for arrays, but tuples are fixed-length):
Time complexity: O(1)
Explanation: For an array, inserting at the end is O(1). For a tuple, however, this is not applicable because tuples have a fixed length.
Updating by index:
Time complexity: O(1)
Explanation: Like arrays, updating a value in a tuple at a specific index is done in constant time.
Copying a tuple:
Time complexity: O(n)
Explanation: If you need to copy a tuple, it takes linear time in relation to the size of the tuple, as each element needs to be copied.
Length lookup:
Time complexity: O(1)
Explanation: Checking the length of a tuple is constant-time, just like arrays.
Example Code in TypeScript:
let person: [string, number, boolean];
person = ['Brandon', 21, true];
console.log(person[0]);
ArrayList (Dynamic Arrays)
Definition:
- Dynamic arrays, on the other hand, can resize themselves dynamically to accommodate a varying number of elements. TypeScript's built-in array type (Array<T>) is a dynamic array that provides this flexibility.
Key Features:
Arrays can grow and shrink in size automatically. You can add or remove elements without needing to specify the size beforehand.
TypeScript allows you to define the type of elements in the array, providing compile-time checks.
TypeScript supports generics, so you can define arrays with types other than primitive types
Use Cases:
Use arrays to store a list of items whose size can change at runtime, like user input data or items fetched from an API.
Store results of data processing tasks, like filtering or mapping data from an array of objects.
Use arrays to represent adjacency lists in graph data structures, enabling dynamic manipulation of nodes and edges.
Time Complexity:
Access (indexing): O(1) – Direct access to an element by its index is constant time.
Search: O(n) – In the worst case, you may need to look through the entire array to find an element.
Insertion:
At the end: O(1) (amortized) – Adding an element at the end is usually constant time unless the array needs to be resized, in which case it can take longer but is amortized over many insertions.
At the beginning or in the middle: O(n) – Elements may need to be shifted.
Deletion:
From the end: O(1) – Removing the last element is constant time.
From the beginning or in the middle: O(n) – Similar to insertion, elements may need to be shifted.
Example Code in TypeScript:
class ArrayList<T> {
private items: T[];
constructor() {
this.items = [];
}
add(item: T): void {
this.items.push(item);
}
}
const list = new ArrayList<number>();
list.add(1);
list.add(2);
list.add(3);
Stack
Definition:
- Stack is a linear data structure, which means its elements are connected in a sequential order and each element connected to the element in front or behind it. Stack is a LIFO (last-in-first-out) data structure. This means the first popped element is the last added to the stack.
Key Features:
LIFO (Last In, First Out) The last element added to the stack is the first one to be removed.
Dynamic Sizing A stack can grow and shrink dynamically as elements are added or removed.
Implementation You can implement a stack using an array or a linked list.
Use Cases:
Stacks are used to keep track of function calls (call stack). When a function is called, it's pushed onto the stack, and when it returns, it's popped off.
Stacks can evaluate expressions, especially in postfix or prefix notation.
Browsers use stacks to manage the back and forward navigation history.
Time Complexity:
Push (adding an item to the top): O(1)
Pop (removing the item from the top): O(1)
Peek (viewing the item at the top without removing it): O(1)
IsEmpty (checking if the stack is empty): O(1)
Size (getting the number of items in the stack): O(1) (if you maintain a count, otherwise O(n) to count elements)
Example Code in TypeScript:
class Stack<T> {
private items: T[] = [];
push(item: T): void {
this.items.push(item);
}
pop(): T | undefined {
return this.items.pop();
}
}
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
Queue
Definition:
- Queues are data structures that follow the First-In-First-Out (FIFO) principle. In simple terms, the first element added to the queue will be the first one to be removed. This guide will take you through creating a basic queue in TypeScript.
Key Features:
FIFO Order Queues operate on a First-In, First-Out basis, meaning the first element added to the queue will be the first one to be removed.
Peek/Front Access the front element of the queue without removing it, allowing you to see what's next to be processed.
Size Maintain a count of the number of elements in the queue, which is useful for checking if the queue is empty or for managing resources.
Use Cases:
Queues can help manage asynchronous operations, such as handling incoming requests in web servers or managing promises in an event-driven architecture.
Queues can manage data streams, allowing for processing of incoming data in the order it arrives, which is useful in applications like chat systems or live feeds.
In web applications, requests can be queued to prevent overload and ensure that they are processed in a fair manner.
Time Complexity:
1. Array-based Implementation
Enqueue (adding an item):
Time Complexity: O(1) (amortized) when appending an item to the end of the array.
If resizing is necessary (when the array is full), it can take O(n) for that operation, but this is rare, making it O(1) amortized.
Dequeue (removing an item):
- Time Complexity: O(n), because shifting all other elements in the array to fill the gap left by the removed item takes linear time.
Peek (viewing the front item):
- Time Complexity: O(1), as it just accesses the first element.
Size (checking the number of items):
- Time Complexity: O(1), as it maintains a count.
2. Linked List-based Implementation
Enqueue (adding an item):
- Time Complexity: O(1), since it can add the new node at the tail without needing to traverse the list.
Dequeue (removing an item):
- Time Complexity: O(1), as it can remove the head node without needing to traverse the list.
Peek (viewing the front item):
- Time Complexity: O(1), since it accesses the head node directly.
Size (checking the number of items):
- Time Complexity: O(1), if you maintain a count of nodes.
Example Code in TypeScript:
class Queue<T> {
private items: T[] = [];
enqueue(item: T): void {
this.items.push(item);
}
dequeue(): T | undefined {
return this.items.shift();
}
}
const queue = new Queue<number>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue());
LinkedList
Definition:
- A linked list is a data structure that holds objects arranged in a linear order, this order is determined by a pointer in each node.
Key Features:
Each node typically contains two parts: the data (value) and a reference (pointer) to the next node in the sequence.
Linked lists can grow and shrink in size dynamically, as opposed to arrays, which have a fixed size.
Nodes in a linked list do not need to be stored in contiguous memory locations, allowing for more efficient use of memory.
Use Cases:
Linked lists can efficiently manage memory when the size of the data structure is unknown or changes frequently. They allow for dynamic resizing without the need for reallocating the entire structure.
Linked lists can be used to implement both stacks (LIFO) and queues (FIFO). Their dynamic nature makes it easy to add and remove elements without shifting other elements, as would be necessary with arrays.
When processing data streams or real-time data where the volume can change rapidly, linked lists allow for efficient insertions and deletions.
Time Complexity:
Access: O(n)
- To access an element, you may need to traverse the list from the head to the desired node.
Search: O(n)
- Similar to access, you may need to traverse the entire list to find a specific value.
Insertion:
At the beginning: O(1)
At the end: O(n) if you need to traverse the list, but O(1) if you maintain a tail pointer.
At a specific index: O(n) because you must traverse to the desired index.
Deletion:
From the beginning: O(1)
From the end: O(n) if you need to traverse the list, but O(1) if you maintain a tail pointer.
From a specific index: O(n) because you must traverse to the desired index.
Example Code in TypeScript:
class Node<T> {
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
class LinkedList<T> {
head: Node<T> | null;
constructor() {
this.head = null;
}
append(data: T): void {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
print(): void {
let current = this.head;
let result = '';
while (current) {
result += `${current.data} -> `;
current = current.next;
}
console.log(result + 'null');
}
}
const list = new LinkedList<number>();
list.append(10);
list.append(20);
list.append(30);
list.print();
HashMap (or Object/Map)
Definition:
- The Hashmap is the one kind of data structure that stores the key-value pairs of the different data. Like other programming languages, TypeScript also contains a built-in map data structure. In JavaScript, we can't define the key or value type that needs to be stored in the map.
Key Features:
Key-Value Pairs Maps store data in pairs, where each key is unique and maps to a specific value.
Ordered Entries Unlike plain objects, Maps maintain the insertion order of the key-value pairs, allowing for predictable iteration.
Any Data Type as Keys Maps can use objects, functions, or any primitive type as keys, whereas object keys are always converted to strings.
Use Cases:
Counting Occurrences Keep track of how many times elements appear in a collection. For instance, you can count the occurrences of words in a text:
Lookup Tables Quickly access values based on keys, such as mapping user IDs to user objects or settings.
Storing Configuration Settings Use a hashmap to store application configuration settings, allowing for easy retrieval and updates.
Time Complexity:
Insertion: Average case O(1)
Deletion: Average case O(1)
Lookup: Average case O(1)
Example Code in TypeScript:
const myMap = new Map<string, number>();
myMap.set("red", 1);
myMap.set("blue", 2);
myMap.set("green", 3);
const redCount = myMap.get("red");
console.log(`Red count: ${redCount}`);
Set
Definition:
- In TypeScript, a Set is a collection of unique values that does not allow duplicate elements. A set is implemented with the Set object, which is part of the ECMAScript 2015 (ES6) specification and fully supported in TypeScript.
Key Features:
A
Setautomatically ensures that all its elements are unique. If you attempt to add a duplicate value, it will be ignored.Elements in a
Setare ordered, meaning that they maintain the order of insertion.You can create a
Setof any type, such as numbers, strings, objects, or even other sets.
Use Cases:
You can easily remove duplicates from an array.
Sets provide efficient lookups, making it quick to check if an item exists.
You can use a Set to track active items or states (like user sessions).
Time Complexity:
Insertion (
add): O(1) on average.Deletion (
delete): O(1) on average.Lookup (
has): O(1) on average.Iteration: O(n), where n is the number of elements in the set.
Example Code in TypeScript:
class MySet<T> {
private items: { [key: string]: T } = {};
add(item: T): void {
const key = this.getKey(item);
this.items[key] = item;
}
remove(item: T): void {
const key = this.getKey(item);
delete this.items[key];
}
has(item: T): boolean {
const key = this.getKey(item);
return key in this.items;
}
}
const mySet = new MySet<number>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
mySet.remove(2);
console.log(mySet.has(2));
Tree
Definition:
- Trees are hierarchical data structures that consist of nodes connected by edges. They are widely used in computer science for organizing and representing hierarchical relationships between data. In TypeScript, we can implement tree data structures to store and manipulate hierarchical data efficiently.
Key Features:
A tree is made up of nodes, each containing data and references to its child nodes. In TypeScript, you can define a node interface or class to represent this structure.
Trees represent hierarchical relationships, making them suitable for representing structures like file systems, organizational charts, or XML/JSON data.
Every tree has a root node, which serves as the starting point. If a tree has no nodes, it is empty.
Use Cases:
Trees are perfect for representing hierarchical data, such as file systems, organizational structures, or taxonomies.
Used for efficient searching, insertion, and deletion of data. BSTs can help implement sets and maps.
Useful in compilers and interpreters for parsing expressions, where leaf nodes represent operands and internal nodes represent operators.
Time Complexity:
1. Binary Tree
Insertion: O(n) in the worst case (unbalanced tree), O(log n) on average (balanced).
Deletion: O(n) in the worst case, O(log n) on average.
Search: O(n) in the worst case, O(log n) on average.
2. Binary Search Tree (BST)
Insertion: O(n) in the worst case (unbalanced), O(log n) on average (balanced).
Deletion: O(n) in the worst case, O(log n) on average.
Search: O(n) in the worst case, O(log n) on average.
3. Balanced Trees (e.g., AVL, Red-Black Tree)
Insertion: O(log n)
Deletion: O(log n)
Search: O(log n)
4. B-Trees (used in databases)
Insertion: O(log n)
Deletion: O(log n)
Search: O(log n)
5. Heap (Binary Heap)
Insertion: O(log n)
Deletion (extract max/min): O(log n)
Search: O(n)
Example Code in TypeScript:
class TreeNode<T> {
value: T;
children: TreeNode<T>[];
constructor(value: T) {
this.value = value;
this.children = [];
}
addChild(child: TreeNode<T>): void {
this.children.push(child);
}
}
class Tree<T> {
root: TreeNode<T>;
constructor(rootValue: T) {
this.root = new TreeNode(rootValue);
}
preOrder(node: TreeNode<T> = this.root): void {
console.log(node.value);
for (const child of node.children) {
this.preOrder(child);
}
}
}
const tree = new Tree<string>('Root');
const child1 = new TreeNode('Child 1');
const child2 = new TreeNode('Child 2');
tree.root.addChild(child1);
tree.root.addChild(child2);
const grandChild1 = new TreeNode('Grandchild 1');
child1.addChild(grandChild1);
console.log('Pre-order Traversal:');
tree.preOrder();
