Data Structure in Typescript

Data Structures in TypeScript

In TypeScript, the strong typing system enhances the use of data structures by enforcing types at compile time, preventing common errors and improving code maintainability.

1. Array

• Definition: An ordered collection of elements indexed by numbers.

• Key Features: Arrays in TypeScript can hold multiple data types if specified using union types or generics.

• Use Cases: Storing lists of elements where random access is needed.

• Time Complexity:

  • Access: O(1)

  • Insertion (at the end): O(1), Deletion (from the end): O(1)

  • Insertion/Deletion (middle): O(n)

• Example Code:

    let arr: number[] = [1, 2, 3];
    arr.push(4); // Add element
    arr.splice(1, 1); // Remove element at index 1
    console.log(arr[0]); // Access first element
  

  2. Tuple

  • Definition: A fixed-length array where each element can have a different type.

  • Key Features: Enables stronger type constraints, ensuring the right type is used for each element.

  • Use Cases: When you need a collection with a fixed number of elements of different types.

  • Time Complexity: Same as arrays.

• Example Code:

    let tuple: [string, number] = ['age', 30];
    console.log(tuple[0]); // 'age'
  

3. ArrayList (Dynamic Array)

• Definition: A dynamic array resizes as needed, automatically expanding or contracting.

• Key Features: Uses TypeScript’s generics to define the type of elements.

• Use Cases: When the number of elements is unknown or changes frequently.

• Time Complexity:

  • Amortized insertion (at the end): O(1)

  • Access: O(1)

• Example Code:

    let dynamicArray: number[] = [];
    dynamicArray.push(5);
    dynamicArray.push(10);
  

  4. Stack

  • Definition: A collection that follows the Last In, First Out (LIFO) principle.

  • Key Features: Supports push (add), pop (remove), and peek (access top element).

  • Use Cases: Managing tasks like function calls, undo mechanisms.

  • Time Complexity:

    • Push, Pop: O(1)

    • Access (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];
      }
    }

5. Queue

• Definition: A collection that follows the First In, First Out (FIFO) principle.

• Key Features: Supports enqueue (add) and dequeue (remove).

• Use Cases: Task scheduling, handling asynchronous processes.

• Time Complexity:

  • Enqueue, 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();
      }
    }
  

6. LinkedList

• Definition: A data structure consisting of nodes, each containing data and a reference to the next node.

• Key Features: Supports efficient insertion/deletion but slower access than arrays.

• Use Cases: Dynamic lists where elements are frequently added/removed.

• Time Complexity:

  • Insertion, Deletion: O(1) (if at head/tail)

  • Search: O(n)

• Example Code:

    class Node<T> {
      value: T;
      next: Node<T> | null = null;
      constructor(value: T) {
        this.value = value;
      }
    }
  
    class LinkedList<T> {
      head: Node<T> | null = null;
      append(value: T) {
        let newNode = new Node(value);
        if (!this.head) this.head = newNode;
        else {
          let current = this.head;
          while (current.next) current = current.next;
          current.next = newNode;
        }
      }
    }
  

7. HashMap (Map)

• Definition: A collection of key-value pairs where each key is unique.

• Key Features: Efficient key-based access and insertion.

• Use Cases: Storing and accessing data via keys.

• Time Complexity:

  • Access, Insert, Delete: O(1)

• Example Code:

    let map: Map<string, number> = new Map();
    map.set('age', 30);
    console.log(map.get('age')); // 30
  

  8. Set

  • Definition: A collection of unique values.

  • Key Features: Ensures that all elements are unique.

  • Use Cases: Managing collections where duplicates are not allowed.

  • Time Complexity:

    • Add, Delete, Search: O(1)

• Example Code:

    let set: Set<number> = new Set();
    set.add(1);
    set.add(2);
    console.log(set.has(1)); // true
  

  9. Tree (Binary Search Tree)

  • Definition: A hierarchical data structure where each node has at most two children, used for sorted data.

  • Key Features: Fast lookups, insertion, and deletion in sorted order.

  • Use Cases: Searching, sorting, hierarchical data.

  • Time Complexity:

    • Insert, Search, Delete: O(log n)

  • Example Code:

      class TreeNode<T> {
        value: T;
        left: TreeNode<T> | null = null;
        right: TreeNode<T> | null = null;
        constructor(value: T) {
          this.value = value;
        }
      }
    

    These examples demonstrate how TypeScript’s strong typing system improves error detection and code maintainability by enforcing constraints on data structures.