# 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:**
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727349802101/b8af92b3-5a9d-43aa-9401-1cb48d59ac32.png align="center")
    
    **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**:

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727350465869/044e5478-5304-42d4-b336-5811d84555c6.png align="center")

### 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:**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727350729695/9a5da669-95d1-4fd1-9d00-a42cbbe9743b.png align="center")

**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:**  

* ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727350985991/3cdb6c32-2d9c-4e0a-9454-dde212e57e1b.png align="center")
    
    ### 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:**
    
* ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727351119120/e53b02c3-901d-493a-88b2-85c6e12e2fe5.png align="center")
    
    ### 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:**
    
* ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727351225210/555ee24c-b5dd-4ad0-a79a-e5d8b488d2fc.png align="center")
    
    ### 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:**
    
* ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727351304199/b6eb88c5-d850-4b6d-884e-256d50dffc44.png align="center")
    

**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:**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727351604027/be397848-c83e-4e88-a8ca-00739533862f.png align="center")

**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:**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1726550330046/33b9127f-52e9-485a-8120-40a4895843d4.png?auto=compress,format&format=webp&auto=compress,format&format=webp align="left")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1726550205028/6c2f9b4c-a9da-4ee3-9640-5528290eaf2d.png?auto=compress,format&format=webp&auto=compress,format&format=webp align="left")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1726550230817/0bd5bf2e-9f65-4072-92ff-d4f47c6d2214.png?auto=compress,format&format=webp&auto=compress,format&format=webp align="left")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1726550305327/dffd3d52-0449-4f64-9703-5649f840676d.png?auto=compress,format&format=webp&auto=compress,format&format=webp align="left")

## **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.