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:

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

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

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

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

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)

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

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

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)

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);