Activity #9: Data Structure in Typescript

Research and Study Data Structures in TypeScript:

• Data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Explain Each Data Structure in TypeScript: For each data structure, provide the following details:

• Definition: A brief explanation of the data structure.

• Key Features: The important characteristics and behaviors of the data structure.

• Use Cases: Where and why this data structure is typically used.

• Time Complexity: Analyze the performance of each data structure (Big-O notation) for common operations like insert, delete, and search.

• Example Code in TypeScript: Provide a TypeScript code snippet demonstrating how to use each data structure.

Array

Definition:

• Array in TypeScript is an ordered collection of elements of the same type. Arrays are useful for storing multiple values under a single variable and allow for sequential access to the elements.

Key Features:

• Typed Elements: Arrays can only contain elements of a specified type (e.g., number[] for an array of numbers).

• Indexed: Elements are stored with a zero-based index, allowing access by index number.

• Dynamic Size: Arrays can dynamically grow or shrink by adding or removing elements.

• Traversable: Arrays can be easily iterated over using loops, such as for or array methods like forEach().

Use Cases:

• Used in situations requiring sequential data access, such as lists, matrices, etc.

Time Complexity:

• Access: O(1) – Constant time to access any element by index.

• Insertion/Deletion:

  • O(1) when adding/removing from the end (e.g., push(), pop()).

  • O(n) when adding/removing elements at the beginning or middle, as other elements need to be shifted.

Typescript Code:

Tuple

• Definition: A tuple is a fixed-size, ordered collection of elements that can hold multiple data types.

• Fixed Size: The number of elements is defined at creation and cannot change.

• Use Cases: Ideal for returning multiple values from functions or representing structured data like records.

• Time Complexity: Same as arrays.

TypeScript Code:

ArrayList (Dynamic Arrays):

Definition:
An ArrayList is a dynamic array that can automatically resize itself when elements are added or removed.

Key Features:

• Dynamic Resizing: Adjusts size as needed.

• Random Access: Allows direct access to elements via indices.

Use Cases:
Storing collections of data, implementing stacks or queues, and managing lists where size may change frequently.

Time Complexity:

• Access: O(1)

• Insertion: O(1) on average (O(n) in worst case due to resizing)

• Resizing: O(n) when resizing occurs.

TypeScript Code:

Sack

Definition:
A stack is a collection of elements that follows the Last In, First Out (LIFO) principle, where the most recently added element is the first to be removed.

Key Features:

• LIFO Order: The last element added is the first to be removed.

• Dynamic Size: Can grow and shrink as elements are added or removed.

• Operations: Typically supports push, pop, and peek operations.

Use Cases:

• Function call management (call stack).

• Undo mechanisms in applications.

• Syntax parsing (e.g., for compilers).

Time Complexity:

• Insertion (push): O(1)

• Deletion (pop): O(1)

• Peek: O(1)

TypeScript Code:

• 

  Queue:

  Definition:
  A queue is a collection of elements that follows the First In, First Out (FIFO) principle, where the first element added is the first to be removed.

  Key Features:

  • FIFO Order: The first element added is the first to be removed.

  • Dynamic Size: Can grow and shrink as elements are added or removed.

  • Basic Operations: Supports enqueue, dequeue, and peek.

Use Cases:

• Task scheduling (e.g., print jobs).

• Breadth-first search algorithms.

• Managing requests in web servers.

Time Complexity:

• Insertion (enqueue): O(1)

• Deletion (dequeue): O(1)

• Peek: O(1)

TypeScript Code:

• 

  LinkedList:

  Definition:
  A linked list is a linear data structure where elements are stored in nodes, each containing a value and a reference to the next node, allowing for efficient insertions and deletions.

  Key Features:

  • Dynamic Size: Can grow or shrink as needed.

  • Node-Based Structure: Consists of nodes containing data and pointers to other nodes.

  • No Contiguous Memory: Unlike arrays, nodes can be scattered in memory.

Use Cases:

• Implementing stacks and queues.

• Managing dynamic memory for complex data structures.

• Maintaining ordered collections.

Time Complexity:

• Insertion (push): O(1) (at the head)

• Deletion (pop): O(1) (at the head)

• Peek: O(1) (head element)

TypeScript Code:

• 

  HashMap (or Object/Map):

  Definition:
  A HashMap is a data structure that stores key-value pairs, allowing for efficient data retrieval based on keys using a hash function.

  Key Features:

  • Key-Value Storage: Associates unique keys with values.

  • Fast Lookups: Average time complexity for accessing values is O(1).

  • Dynamic Size: Grows as needed when more key-value pairs are added.

Use Cases:

• Caching data for quick access.

• Counting occurrences of items (frequency map).

• Implementing dictionaries or lookup tables.

Time Complexity:

• Insertion (set): O(1) on average

• Deletion (delete): O(1) on average

• Peek (get): O(1) on average

TypeScript Code:

• 

SET

Definition: A Set is a collection of unique values that allows for efficient insertion, deletion, and lookup of items without duplicates.

Key Features:

• Unique Elements: Automatically ensures all values are unique.

• Dynamic Size: Can grow or shrink as items are added or removed.

• Order of Insertion: Maintains the order of elements based on their insertion.

Use Cases:

• Removing duplicates from arrays.

• Checking membership (existence of an element).

• Implementing mathematical set operations (union, intersection).

Time Complexity:

• Insertion (add): O(1) on average

• Deletion (delete): O(1) on average

• Peek (has): O(1) on average

TypeScript Code:

TREE

Definition: A tree is a hierarchical data structure consisting of nodes connected by edges, with a single node called the root. Each node may have zero or more child nodes, forming a branching structure. In a binary search tree, each node has at most two children, with the left child containing values less than the parent and the right child containing values greater than the parent.

Key Features:

• Hierarchical Structure: Data is organized in a parent-child relationship, making it easy to navigate.

• Root Node: The topmost node from which all other nodes descend.

• Binary Property: In a binary tree, each node has at most two children.

• Dynamic Size: Trees can grow and shrink dynamically based on the number of nodes.

Use Cases:

• Representing hierarchical data (e.g., file systems, organization charts).

• Implementing search algorithms (e.g., binary search trees for fast lookups).

• Storing sorted data, enabling efficient range queries and ordered traversals.

Time Complexity:

• Insertion (push): O(h) where h is the height of the tree (O(log n) for balanced trees, O(n) for unbalanced).

• Deletion (pop): O(h) where h is the height of the tree.

• Peek: O(1) for the root node; O(h) for accessing specific nodes.

TypeScript Code:

Deliverables:

Explanation:

• For Set, we covered its properties of uniqueness, and how to add, remove, and check for elements.

• For Binary Search Tree, we discussed the sorted nature of the structure, and how it allows for efficient searching, insertion, and traversal.

• TypeScript Code Snippets:

  • For Set, the code demonstrates creation, addition, removal, and checking for existence.

  • For Binary Search Tree, the code shows insertion, searching, and in-order traversal of nodes.