# 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:

```plaintext
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:

```plaintext
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:

```plaintext
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), and `peek` (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:

```plaintext
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), and `front` (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:

```plaintext
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:

```plaintext
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:

```plaintext
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:

```plaintext
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
    

---