Activity 10: Data Structure in Typescript
1. Arrays in TypeScript
Definition:
An array is a linear collection of elements that are stored in contiguous memory locations. It is used to store multiple values in a single variable and can be of any type.
Key Features:
Arrays in TypeScript are dynamic in size, unlike in some other languages where arrays have a fixed size.
Strongly typed: You can define arrays with a specific type or allow them to store multiple types (using union types or
any).Supports typical operations like adding, removing, and accessing elements.
Use Cases:
Storing collections of data where order is important.
Common in scenarios like keeping a list of items, such as product inventories, user profiles, etc.
Time Complexity:
Access: O(1)
Insertion (at the end): O(1)
Insertion (at the beginning): O(n)
Deletion (at the end): O(1)
Deletion (at the beginning): O(n)
Example Code:
typescriptCopy codelet numbers: number[] = [10, 20, 30];
// Add an element
numbers.push(40); // [10, 20, 30, 40]
// Remove the last element
numbers.pop(); // [10, 20, 30]
// Access an element
console.log(numbers[1]); // 20
2. Tuple in TypeScript
Definition:
A tuple is a fixed-length array where each element can have a different type. Tuples are similar to arrays but enforce the type of each element at a specific position.
Key Features:
Fixed in size but can have mixed types for each element.
Great for representing structures where you know the number of elements and their types.
Use Cases:
- Representing structured data like key-value pairs, or records with different types for each field.
Time Complexity:
- Same as arrays.
Example Code:
typescriptCopy codelet person: [string, number] = ["Alice", 25];
// Access tuple elements
console.log(person[0]); // Alice
console.log(person[1]); // 25
// Tuple with optional element
let personWithPhone: [string, number, string?] = ["Alice", 25];
personWithPhone.push("123-456-7890"); // Adds phone number to tuple
3. ArrayList (Dynamic Arrays) in TypeScript
Definition:
An ArrayList or dynamic array in TypeScript is implemented using the built-in array, but the array resizes dynamically as elements are added.
Key Features:
Resizable array that automatically grows as more elements are added.
Can hold elements of any type, but is usually typed to maintain type consistency.
Use Cases:
- When the size of the array is not known at compile time and needs to change dynamically based on user input or operations.
Time Complexity:
Access: O(1)
Insertion (at the end): O(1) (amortized cost)
Deletion (at the end): O(1)
Insertion/Deletion (at beginning or middle): O(n)
Example Code:
typescriptCopy codelet dynamicArray: number[] = [1, 2, 3];
dynamicArray.push(4); // [1, 2, 3, 4]
dynamicArray.splice(1, 1); // Remove element at index 1: [1, 3, 4]
4. Stack in TypeScript
Definition:
A stack is a linear data structure that follows the Last In First Out (LIFO) principle, where the last element added is the first one to be removed.
Key Features:
Follows the LIFO principle.
Main operations:
push(add an element),pop(remove the last element), andpeek(get the last element without removing it).
Use Cases:
Undo mechanisms in text editors.
Function call stacks in programming languages.
Time Complexity:
Push: O(1)
Pop: O(1)
Peek: O(1)
Example Code:
typescriptCopy codeclass Stack<T> {
private items: T[] = [];
push(item: T) {
this.items.push(item);
}
pop(): T | undefined {
return this.items.pop();
}
peek(): T | undefined {
return this.items[this.items.length - 1];
}
}
let stack = new Stack<number>();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 20
console.log(stack.peek()); // 10
5. Queue in TypeScript
Definition:
A queue is a linear data structure that follows the First In First Out (FIFO) principle, where the first element added is the first one to be removed.
Key Features:
Follows the FIFO principle.
Main operations:
enqueue(add an element),dequeue(remove the first element), andfront(get the first element without removing it).
Use Cases:
- Task scheduling, printer queues, and event handling.
Time Complexity:
Enqueue: O(1)
Dequeue: O(1)
Peek: O(1)
Example Code:
typescriptCopy codeclass Queue<T> {
private items: T[] = [];
enqueue(item: T) {
this.items.push(item);
}
dequeue(): T | undefined {
return this.items.shift();
}
front(): T | undefined {
return this.items[0];
}
}
let queue = new Queue<number>();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.dequeue()); // 10
console.log(queue.front()); // 20
6. LinkedList in TypeScript
Definition:
A linked list is a linear data structure where each element (node) contains a value and a reference (or pointer) to the next node in the sequence.
Key Features:
Dynamic size, unlike arrays.
Efficient insertions and deletions, especially in the middle of the list.
Can be singly or doubly linked (singly linked lists have pointers to the next node; doubly linked lists have pointers to both the next and previous nodes).
Use Cases:
Efficient memory usage for dynamic data structures.
Commonly used in implementing queues, stacks, and other abstract data types.
Time Complexity:
Access: O(n)
Insertion: O(1) (at head or tail)
Deletion: O(1) (at head or tail)
Example Code:
typescriptCopy codeclass Node<T> {
data: T;
next: Node<T> | null = null;
constructor(data: T) {
this.data = data;
}
}
class LinkedList<T> {
head: Node<T> | null = null;
insert(data: T) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}
traverse() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
let list = new LinkedList<number>();
list.insert(10);
list.insert(20);
list.traverse(); // Output: 10, 20
7. HashMap (Map) in TypeScript
Definition:
A HashMap (or Map) is a collection of key-value pairs where each key is mapped to a value. Unlike arrays, HashMaps allow for efficient lookups by key.
Key Features:
Fast lookups, insertions, and deletions.
Keys can be of any type, unlike objects where keys are typically strings.
Use Cases:
- Storing pairs of related data like usernames and user IDs, word frequencies, etc.
Time Complexity:
Insertion: O(1) (average case)
Deletion: O(1) (average case)
Lookup: O(1) (average case)
Example Code:
typescriptCopy codelet map = new Map<string, number>();
map.set("Alice", 25);
map.set("Bob", 30);
// Access an element
console.log(map.get("Alice")); // 25
// Remove an element
map.delete("Bob");
8. Set in TypeScript
Definition:
A set is a collection of unique elements. Unlike arrays, sets automatically ensure that no duplicates are stored.
Key Features:
Uniqueness: No duplicate elements are allowed.
Supports basic set operations like union, intersection, and difference.
Use Cases:
Efficiently checking for existence of an element.
Storing collections of unique items like tags, categories, etc.
Time Complexity:
Insertion: O(1)
Deletion: O(1)
Search: O(1)
Example Code:
typescriptCopy codelet set = new Set<number>();
set.add(10);
set.add(20);
set.add(10); // Duplicate will not be added
console.log(set.has(10)); // true
set.delete(20);
9. Tree (Binary Search Tree) in TypeScript
Definition:
A tree is a hierarchical data structure with nodes connected by edges. A Binary Search Tree (BST) is a tree where each node has at most two children, and the left child contains a value less than the parent node, while the right child contains a value greater than the parent node.
Key Features:
Efficient searching, insertion, and deletion operations.
Balanced trees (like AVL or Red