# Activity 9: Data Structure in Typescript

## 1\. Arrays

### Definition

An array is a collection of elements identified by index or key, allowing for storage of multiple values in a single variable.

### Key Features

* Fixed size (in some languages), but can be dynamic in TypeScript.
    
* Elements can be accessed using an index.
    
* Can store elements of different types (if not strictly typed).
    

### Use Cases

* Storing a collection of items (e.g., list of numbers, strings).
    
* Frequently used in algorithms and data processing tasks.
    

### Time Complexity

* Access: O(1)
    
* Search: O(n)
    
* Insert: O(n) (for inserting at the beginning or middle)
    
* Delete: O(n)
    

### Example Code:

```abap
let numbers: number[] = [1, 2, 3, 4];

// Adding an element
numbers.push(5); // [1, 2, 3, 4, 5]

// Removing an element
numbers.pop(); // [1, 2, 3, 4]

// Accessing an element
let firstNumber = numbers[0]; // 1
```

## 2\. Tuple

### Definition

A tuple is a fixed-size array where each element can be of a different type.

### Key Features

* Allows for heterogeneous data types.
    
* Fixed length.
    

### Use Cases

* Returning multiple values from a function.
    
* Grouping related data of different types.
    

### Example Code

```abap
let person: [string, number] = ['Alice', 30];

// Accessing tuple elements
let name = person[0]; // 'Alice'
let age = person[1]; // 30
```

## 3\. ArrayList (Dynamic Arrays)

### Definition

A dynamic array is an array that can grow or shrink in size automatically as elements are added or removed.

### Key Features

* Resizes automatically.
    
* Provides methods to manipulate the collection.
    

### Use Cases

* Storing collections where the size is unknown or varies.
    

### Example Code

```abap
class DynamicArray<T> {
  private items: T[] = [];
  
  add(item: T) {
    this.items.push(item);
  }

  remove(index: number): T | undefined {
    return this.items.splice(index, 1)[0];
  }

  get(index: number): T | undefined {
    return this.items[index];
  }

  size(): number {
    return this.items.length;
  }
}

// Usage
const arrayList = new DynamicArray<number>();
arrayList.add(1);
arrayList.add(2);
arrayList.remove(0); // removes 1
```

## 4\. Stack

### 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 to be removed.

### Key Features

* Supports push (add), pop (remove), and peek (access top) operations.
    

### Use Cases

* Function call management (call stack).
    
* Undo mechanisms in applications.
    

### Time Complexity

* Push: O(1)
    
* Pop: O(1)
    
* Peek: O(1)
    

### Example Code

```abap
class 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];
  }
}

// Usage
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.pop(); // returns 2
```

## 5\. Queue

### 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 to be removed.

### Key Features

* Supports enqueue (add) and dequeue (remove) operations.
    

### Use Cases

* Managing tasks in order (e.g., printer queue).
    
* Breadth-first search (BFS) in trees and graphs.
    

### Time Complexity

* Enqueue: O(1)
    
* Dequeue: O(1)
    

### Example Code

```abap
class 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];
  }
}

// Usage
const queue = new Queue<number>();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue(); // returns 1
```

## 6\. Linked List

### Definition

A linked list is a linear data structure where elements (nodes) are stored in separate objects, and each node points to the next one.

### Key Features

* Dynamic size.
    
* Efficient insertions and deletions.
    

### Use Cases

* Implementing stacks and queues.
    
* Storing data that frequently changes.
    

### Time Complexity

* Access: O(n)
    
* Insert: O(1) (at the head)
    
* Delete: O(1) (if node is known)
    

### Example Code (Singly Linked List)

```abap
class Node<T> {
  data: T;
  next: Node<T> | null = null;

  constructor(data: T) {
    this.data = data;
  }
}

class LinkedList<T> {
  head: Node<T> | null = null;

  add(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;
    }
  }

  remove(data: T) {
    if (!this.head) return;
    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }
}

// Usage
const linkedList = new LinkedList<number>();
linkedList.add(1);
linkedList.add(2);
linkedList.remove(1);
```

## 7\. HashMap (or Object/Map)

### Definition

A HashMap (or simply a Map) is a key-value pair data structure that allows for fast retrieval of values based on their keys.

### Key Features

* Keys can be of any type.
    
* Fast access time for retrieving values.
    

### Use Cases

* Caching data.
    
* Storing relationships between data.
    

### Time Complexity

* Insert: O(1) (average)
    
* Delete: O(1) (average)
    
* Search: O(1) (average)
    

### Example Code

```abap
const map = new Map<string, number>();

// Inserting values
map.set('Alice', 25);
map.set('Bob', 30);

// Searching for values
let age = map.get('Alice'); // 25

// Deleting a value
map.delete('Bob');
```

## 8\. Set

### Definition

A Set is a collection of unique elements that can be of any type.

### Key Features

* Only unique values are stored.
    
* Fast access for checking existence.
    

### Use Cases

* Storing unique items, like user IDs.
    
* Removing duplicates from an array.
    

### Time Complexity

* Add: O(1) (average)
    
* Delete: O(1) (average)
    
* Check existence: O(1) (average)
    

### Example Code

```abap
const set = new Set<number>();

// Adding elements
set.add(1);
set.add(2);
set.add(1); // No effect, as 1 is already in the set

// Checking for elements
let hasOne = set.has(1); // true

// Removing an element
set.delete(2);
```

## 9\. Tree (Binary Tree / Binary Search Tree)

### Definition

A tree is a hierarchical data structure with nodes connected by edges. A binary tree is a tree where each node has at most two children.

### Key Features

* Hierarchical structure.
    
* Efficient searching and sorting in a binary search tree (BST).
    

### Use Cases

* Storing sorted data.
    
* Implementing priority queues.
    

### Time Complexity

* Search: O(log n) (average for BST)
    
* Insert: O(log n) (average for BST)
    
* Delete: O(log n) (average for BST)
    

### Example Code (Binary Search Tree)

```abap
class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

class BinarySearchTree<T> {
  root: TreeNode<T> | null = null;

  insert(value: T) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    this.insertNode(this.root, newNode);
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < node.value) {
      if (!node.left) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (!node.right) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
```