# Activity 9: Data Structure in Typescript

**Research and Study Data Structures in TypeScript:**

1. Definition of Typescript
    
    TypeScript is a syntactic superset of JavaScript which adds **static typing**.
    
    This basically means that TypeScript adds syntax on top of JavaScript, allowing developers to add **types**.
    
2. TypeScript’s strong typing system enhances the use of data structures by adding clarity, safety, and maintainability to the code. Here are key ways in which it improves the use of common data structures including the following:
    
    * Type safety
        
    * Improved readability and documentation
        
    * Compile-time error detection
        
    * Readonly and Immutable Data Structures
        
    * Typescript improves your productivity while helping avoid bugs
        
    * Generics for usability
        
    * Strict null and undefined checking
        
    * Union and intersection types
        
    
    **Research and Study Data Structures in TypeScript:**
    

### Brief overview of TypeScript

TypeScript is a superset of [JavaScript](https://www.javascripttutorial.net/).

TypeScript builds on top of JavaScript. First, you write the TypeScript code. Then, you compile the TypeScript code into plain JavaScript code using a TypeScript compiler.

Once you have the plain JavaScript code, you can deploy it to any environment that JavaScript runs.

TypeScript files use the `.ts` extension rather than the `.js` extension of JavaScript files.

### Key features

* **Static Typing-** TypeScript adds static types to JavaScript, enabling type checking at compile time. This ensures that the variables, function arguments, and return types are explicitly defined, reducing runtime errors.
    
* **Type Interface** - In TypeScript, there are several places where type inference is used to provide type information when there is no explicit type annotation.
    
* **Interfaces** - TypeScript introduces `interfaces` to define the shape of an object. They are contracts that classes or objects must follow, making your code more structured and reusable.
    
* **Generics** - Generics allow you to create reusable components that work with multiple types, adding flexibility while maintaining type safety.
    
* **Enums** - Enums are one of the few features TypeScript has which is not a type-level extension of JavaScript.
    
    Enums allow a developer to define a set of named constants. Using enums can make it easier to document intent, or create a set of distinct cases. TypeScript provides both numeric and string-based enums.
    
* **Type Aliases**
    
    Type aliases allow you to create custom names for types, including complex types. This improves code readability and reusability.
    

### Key characteristics of data structures include:

1. **Organization:** Data structures provide a way to organize and structure data to make it more manageable and accessible.
    
2. **Operations:** Data structures define a set of operations that can be performed on the data, such as searching, sorting, and updating.
    
3. **Efficiency:** Different data structures offer different trade-offs in terms of time and space complexity for various operations. Choosing the right data structure is crucial for optimizing the efficiency of algorithms.
    
4. **Abstraction:** Data structures often provide a level of abstraction that hides the underlying details of how the data is stored and manipulated, making it easier for programmers to work with
    

### Time complexity

* The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Note that the time to run is a function of the length of the input and not the actual execution time of the machine on which the algorithm is running on.
    

### Typescript Code snippets example

# Arrays

Arrays are one of the simplest and most common data structures. They store elements of the same type in contiguous memory locations, allowing constant-time access to elements using their indices.

```plaintext
typescript
class Node<T> {
    constructor(public data: T, public next: Node<T> | null = null) {}
}

class LinkedList<T> {
    constructor(public head: Node<T> | null = null) {}

    // Insert a new node at the end of the list
    append(data: T) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
}
```

### TypeScript Tuples

In JavaScript, arrays consist of values of the same type, but sometimes we need to store a collection of values of different types in a single variable. TypeScript offers tuples for this purpose. Tuples are similar to structures in C programming and can be passed as parameters in function calls.

Tuples can contain one or more types of data (e.g., numbers and strings).

**Syntax**

```plaintext
let tuple_name = [val1, val2, val3, ...val n];  
```

**TypeScript**

```plaintext
let arrTuple: [number, string, number, string] = [501, "welcome", 505, "Mohan"];
console.log(arrTuple);
```

**Output**

```plaintext
[501, 'welcome', 105, 'Mohan']
```

### ArrayList (Dynamic arrays)

Concept of Dynamic Arrays:

1. **Resizing**: When adding elements to a dynamic array, if it becomes full, the array typically doubles its size to accommodate more elements.
    
2. **Amortized Cost**: Adding elements might involve copying the elements to a new, larger array, but this resizing happens infrequently, leading to an average (amortized) time complexity of O(1) for insertion.
    

```plaintext
let dynamicArray = [];
dynamicArray.push(10); // Add element at the end
dynamicArray.push(20);
console.log(dynamicArray); // [10, 20]

dynamicArray.pop(); // Removes the last element
console.log(dynamicArray); // [10]
```

### Stack

A stack is an elementary data structure, that is often described as LIFO (last in first out). An item that was added the last is the first to be retrieved. Usually, stacks have the following methods:

1. push adds an item to the stack
    
2. pop returns the last added item and remove it from the stack
    
3. peek (optional) returns the last added item without removing it from the stack
    

Stack also has some properties:

1. storage represents all stacked items
    
2. capacity (optional) is a number of items a stack can fit
    

**Queues** are very similar to the stacks, but they handle items FIFO (first in first out). Items will be retrieved from the queue in the same order as they were added. Queues have the following methods:

1. `enqueue` adds an item to the queue
    
2. `dequeue` retrieves an item from the queue
    
3. `size` returns the size of the queue
    

### **LinkList**

  
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

There are two main types of linked lists:

1. **Singly linked list**: a list where elements have only a reference to next element
    
2. **Doubly linked list**: a list where elements are linked to both next and previous elements
    

Here is an example that demonstrates adding, removing, and traversing nodes in a **Singly Linked List** using TypeScript.

```plaintext
class SinglyNode {
    value: number;
    next: SinglyNode | null = null;  // Points to the next node

    constructor(value: number) {
        this.value = value;  // Initialize the node value
    }
}

class SinglyLinkedList {
    head: SinglyNode | null = null;  // Points to the first node

    // Add a new node at the end of the list
    add(value: number): void {
        const newNode = new SinglyNode(value);
        if (!this.head) {
            // If list is empty, set the head to the new node
            this.head = newNode;
        } else {
            // Traverse to the end and add the new node
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Remove a node by its value
    remove(value: number): void {
        if (!this.head) return;  // If list is empty, do nothing

        // If the node to remove is the head
        if (this.head.value === value) {
            this.head = this.head.next;
            return;
        }

        // Traverse and find the node to remove
        let current = this.head;
        while (current.next && current.next.value !== value) {
            current = current.next;
        }

        // If the node is found, remove it by bypassing it
        if (current.next) {
            current.next = current.next.next;
        }
    }

    // Traverse and print the values of the list
    traverse(): void {
        let current = this.head;
        while (current) {
            console.log(current.value);
            current = current.next;
        }
    }
}

// Example usage:
const singlyList = new SinglyLinkedList();

// Adding nodes
singlyList.add(10);
singlyList.add(20);
singlyList.add(30);

// Traversing the list (Output: 10 20 30)
console.log('Initial list:');
singlyList.traverse();

// Removing a node
singlyList.remove(20);

// Traversing the list after removal (Output: 10 30)
console.log('After removing 20:');
singlyList.traverse();
```

Here’s an example of adding, removing, and traversing nodes in a **Doubly Linked List**.

```plaintext
class DoublyNode {
    value: number;
    next: DoublyNode | null = null;  // Points to the next node
    prev: DoublyNode | null = null;  // Points to the previous node

    constructor(value: number) {
        this.value = value;
    }
}

class DoublyLinkedList {
    head: DoublyNode | null = null;  // Points to the first node
    tail: DoublyNode | null = null;  // Points to the last node

    // Add a node at the end of the list
    add(value: number): void {
        const newNode = new DoublyNode(value);
        if (!this.head) {
            // If the list is empty, set both head and tail to the new node
            this.head = newNode;
            this.tail = newNode;
        } else {
            // Append the new node to the end
            this.tail!.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
    }

    // Remove a node by its value
    remove(value: number): void {
        if (!this.head) return;  // If the list is empty, do nothing

        // If the node to remove is the head
        if (this.head.value === value) {
            this.head = this.head.next;
            if (this.head) this.head.prev = null;
            else this.tail = null;
            return;
        }

        // Traverse to find the node to remove
        let current = this.head;
        while (current && current.value !== value) {
            current = current.next;
        }

        // If the node is found, remove it by adjusting pointers
        if (current) {
            if (current.next) {
                current.next.prev = current.prev;
            } else {
                this.tail = current.prev;
            }

            if (current.prev) {
                current.prev.next = current.next;
            }
        }
    }

    // Traverse and print the values of the list
    traverse(): void {
        let current = this.head;
        while (current) {
            console.log(current.value);
            current = current.next;
        }
    }
}

// Example usage:
const doublyList = new DoublyLinkedList();

// Adding nodes
doublyList.add(10);
doublyList.add(20);
doublyList.add(30);

// Traversing the list (Output: 10 20 30)
console.log('Initial list:');
doublyList.traverse();

// Removing a node
doublyList.remove(20);

// Traversing the list after removal (Output: 10 30)
console.log('After removing 20:');
doublyList.traverse();
```

### Hashmap (or Object map)

In [**TypeScript**](https://www.geeksforgeeks.org/typescript/), [One can u](https://www.geeksforgeeks.org/typescript/)se the built-in `Map` d[ata](https://www.geeksforgeeks.org/typescript-map/) structure to implement a hashmap. A [`Map`](https://www.geeksforgeeks.org/typescript-map/) can be used to store key-value pairs where keys can be of any type.

```plaintext
// Create a new HashMap using the Map object
const hashMap = new Map<string, number>();

// Inserting values into the HashMap
hashMap.set("apple", 50);   // Key: "apple", Value: 50
hashMap.set("banana", 30);  // Key: "banana", Value: 30
hashMap.set("orange", 20);  // Key: "orange", Value: 20

console.log("Initial HashMap:", hashMap);

// Searching for values by key
console.log("Value for 'apple':", hashMap.get("apple"));  // Output: 50
console.log("Does 'banana' exist?:", hashMap.has("banana"));  // Output: true

// Deleting a value by key
hashMap.delete("banana");

console.log("After deleting 'banana':", hashMap);

// Searching for a deleted key
console.log("Does 'banana' exist after deletion?:", hashMap.has("banana"));  // Output: false
```

### Set

In TypeScript, the `Set` is a new data structure introduced in [ES6](https://262.ecma-international.org/6.0/), [si](https://262.ecma-international.org/6.0/)milar to [`Map`](https://howtodoinjava.com/typescript/maps/) [tha](https://howtodoinjava.com/typescript/maps/)t allows us to store distinct values. It is similar to an array or a *List* but with the distinction that it doesn’t allow duplicate values.

1. Creating set
    
    To create a Set in TypeScript, we can simply use the `Set` constructor:
    
    ```plaintext
    
    const directions = new Set<string>();
    ```
    

For refer[ences:](https://www.geeksforgeeks.org/typescript/)

[ht](https://www.geeksforgeeks.org/typescript/)[tps://medium.com/@ili](https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba)[malb](https://www.geeksforgeeks.org/typescript-map/)[ayrak/mastering-](https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba)[types](https://262.ecma-international.org/6.0/)[cript-explo](https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba)[ring-](https://howtodoinjava.com/typescript/maps/)[data-structures-and-algorithms-part-i-47d58e6195ba](https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba)

[https://www.typescripttutorial.net/](https://www.typescripttutorial.net/)

[https://www.geeksforgeeks.org/time-complexity-and-space-complexity/?ref=leftbar-rightbar](https://www.geeksforgeeks.org/time-complexity-and-space-complexity/?ref=leftbar-rightbar)  
[https://clouddevs.com/typescript/implementing-data-structures/](https://clouddevs.com/typescript/implementing-data-structures/)

[https://dev.to/glebirovich/typescript-data-structures-stack-and-queue-hld](https://dev.to/glebirovich/typescript-data-structures-stack-and-queue-hld)

**Linklist Reference - Chatgpt, Typescript Handbook, MDN Web Docs on Linked Lists,**

[https://dev.to/glebirovich/typescript-data-structures-linked-list-3o8i](https://dev.to/glebirovich/typescript-data-structures-linked-list-3o8i)