Activity 9: Data Structure in Typescript

Data Structures in TypeScript

1. Arrays:

An array is a collection of elements stored in contiguous memory locations. In TypeScript, arrays can be homogeneous (all elements of the same type) or heterogeneous (elements of different types).

Key Features:

• Fixed size (for static arrays).

• Dynamic resizing (in JavaScript/TypeScript).

• Supports indexing.

Use Cases:

• Storing lists of items.

• Implementing stacks, queues, or other collections.

Example Code:

let fruits: Array<string>;
fruits = ['Apple', 'Orange', 'Banana']; 

let ids: Array<number>;
ids = [23, 34, 100, 124, 44];

Tuples

A tuple is a special type of array that allows you to store a fixed number of elements with specific types at each index.

Key Features:

• Fixed size and types for each element.

• Can contain different data types.

Use Cases:

• Returning multiple values from a function.

• Storing records or fixed collections of items.

Example Code:

var employee: [number, string] = [1, "Steve"];
var person: [number, string, boolean] = [1, "Steve", true];

var user: [number, string, boolean, number, string];// declare tuple variable
user = [1, "Steve", true, 20, "Admin"];// initialize tuple variable

3. ArrayList (Dynamic Arrays)

A dynamic array automatically resizes itself when elements are added or removed, unlike static arrays that have a fixed size.

Key Features:

• Resizes dynamically when needed.

• Combines the advantages of arrays and linked lists.

Use Cases:

• Storing collections of data that change in size.

• Useful in scenarios where the number of elements is unknown.

Example Code:

Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle, meaning the last element added is the first to be removed.

Key Features:

• Supports operations: push (add), pop (remove), and peek (view the top element).

• No random access.

Use Cases:

• Undo functionality in text editors.

• Parsing expressions (like evaluating math expressions).

Example Code:

class Stack<T> implements IStack<T> {
  private storage: T[] = [];

  constructor(private capacity: number = Infinity) {}

  push(item: T): void {
    if (this.size() === this.capacity) {
      throw Error("Stack has reached max capacity, you cannot add more items");
    }
    this.storage.push(item);
  }

  pop(): T | undefined {
    return this.storage.pop();
  }

  peek(): T | undefined {
    return this.storage[this.size() - 1];
  }

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

const stack = new Stack<string>();
stack.push("A");
stack.push("B");

stack.size(); // Output: 2
stack.peek(); // Output: "B"
stack.size(); // Output: 2
stack.pop();  // Output: "B"
stack.size(); // Output: 1

5. Queue

   A queue is a linear data structure that follows the First In First Out (FIFO) principle, meaning the first element added is the first to be removed.

   Key Features:

   • Supports operations: enqueue (add), dequeue (remove), and peek (view the front element).

   • No random access.

Use Cases:

• Managing tasks in order of arrival (like printer queues).

• Handling asynchronous requests.

Example Code:

    class Queue<T> implements IQueue<T> {
      private storage: T[] = [];

      constructor(private capacity: number = Infinity) {}

      enqueue(item: T): void {
        if (this.size() === this.capacity) {
          throw Error("Queue has reached max capacity, you cannot add more items");
        }
        this.storage.push(item);
      }
      dequeue(): T | undefined {
        return this.storage.shift();
      }
      size(): number {
        return this.storage.length;
      }
    }

    const queue = new Queue<string>();

    queue.enqueue("A");
    queue.enqueue("B");

    queue.size();    // Output: 2
    queue.dequeue(); // Output: "A"
    queue.size();    // Output: 1

6. Linked List

A linked list is a linear data structure consisting of nodes where each node contains a value and a reference to the next node in the sequence.

Key Features:

• Dynamic size.

• Efficient insertions and deletions (especially at the beginning).

Use Cases:

• Implementing stacks and queues.

• Storing data that requires frequent insertions and deletions.

Example Code:

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

      public insertAtEnd(data: T): Node<T> {
        const node = new Node(data);
        if (!this.head) {
          this.head = node;
        } else {
          const getLast = (node: Node<T>): Node<T> => {
            return node.next ? getLast(node.next) : node;
          };

          const lastNode = getLast(this.head);
          node.prev = lastNode;
          lastNode.next = node;
        }
        return node;
      }

      public insertInBegin(data: T): Node<T> {
        const node = new Node(data);
        if (!this.head) {
          this.head = node;
        } else {
          this.head.prev = node;
          node.next = this.head;
          this.head = node;
        }
        return node;
      }

      public deleteNode(node: Node<T>): void {
        if (!node.prev) {
          this.head = node.next;
        } else {
          const prevNode = node.prev;
          prevNode.next = node.next;
        }
      }

      public search(comparator: (data: T) => boolean): Node<T> | null {
        const checkNext = (node: Node<T>): Node<T> | null => {
          if (comparator(node.data)) {
            return node;
          }
          return node.next ? checkNext(node.next) : null;
        };

        return this.head ? checkNext(this.head) : null;
      }

      public traverse(): T[] {
        const array: T[] = [];
        if (!this.head) {
          return array;
        }

        const addToArray = (node: Node<T>): T[] => {
          array.push(node.data);
          return node.next ? addToArray(node.next) : array;
        };
        return addToArray(this.head);
      }

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

    interface Post {
      title: string;
    }
    const linkedList = new LinkedList<Post>();

    linkedList.traverse() // [];

    linkedList.insertAtEnd({ title: "Post A" });
    linkedList.insertAtEnd({ title: "Post B" });
    linkedList.insertInBegin({ title: "Post C" });
    linkedList.insertInBegin({ title: "Post D" });

    linkedList.traverse() // [{ title : "Post D" }, { title : "Post C" }, { title : "Post A" }, { title : "Post B" }];
    linkedList.search(({ title }) => title === "Post A") // Node { data: { title: "Post A" }, prev: Node, next: Node};

7. HashMap (or Object/Map)

A HashMap (or dictionary) is a collection of key-value pairs that allows for fast retrieval of values based on their keys.

Key Features:

• Keys are unique.

• Fast lookups, insertions, and deletions.

Use Cases:

• Storing configurations.

• Counting occurrences of items.

Example Code:

8. set

   A Set is a collection of unique values that can store any type of data. Duplicates are automatically removed.

   Key Features:

   • Unique values.

   • Fast checks for existence.

Use Cases:

• • Storing a collection of unique items.

    • Removing duplicates from an array.

Example Code:

Tree (Binary Search Tree)

A binary search tree (BST) is a tree data structure where each node has at most two children. The left child is less than the parent, and the right child is greater.

Key Features:

• Efficient searching, insertion, and deletion.

• Hierarchical structure.

Use Cases:

• Organizing data for fast retrieval.

• Implementing databases.

Example Code:

References:

https://www.w3schools.com/typescript/typescript_arrays.php

https://medium.com/@konduruharish/binary-search-tree-in-typescript-and-c-25fa5107cc5d

https://www.geeksforgeeks.org/how-do-dynamic-arrays-work/

https://graphite.dev/guides/typescript-sets

https://ricardoborges.dev/data-structures-in-typescript-binary-search-tree

https://www.tutorialsteacher.com/typescript/type-inference