jeromebloging

Activity 9: Data Structure in Typescript

Jerome Beriso's photo
Jerome Beriso
·

8 min read

Array

Definition:
An array is a data structure that stores a collection of elements, each identified by at least one array index or key. It is one of the most common and fundamental data structures in programming.

Key Features:

  • Elements are stored in contiguous memory locations.

  • Elements can be accessed using their index (starting from 0).

  • Arrays can hold elements of the same data type or be multi-dimensional.

Use Cases:

  • Storing and accessing a collection of elements in a sequential order.

  • Implementing lists, queues, stacks, and matrices.

  • Processing and manipulating data in an ordered manner.

Time Complexity:

  • Insertion (at the end): O(1) - Constant time as it appends elements at the end.

  • Insertion (at the beginning): O(n) - Linear time as it requires shifting existing elements.

  • Deletion (at the end): O(1) - Constant time to remove the last element.

  • Deletion (at the beginning): O(n) - Linear time due to shifting elements.

  • Search (Accessing an element by index): O(1) - Constant time as it directly accesses elements by index.

  • Search (Linear Search): O(n) - Linear time for searching an element throughout the array.

Example Code in TypeScript:

Tuple

Definition:
A tuple in TypeScript is an array-like structure where each element has a specific, fixed type and position. Unlike arrays, tuples have a predefined length and can contain elements of different data types at specific positions.

Key Features:

  • Elements in a tuple have fixed positions and types.

  • Tuples can store elements of different data types.

  • Tuple length is fixed and defined at declaration.

Use Cases:

  • Storing and accessing data with a known, fixed structure.

  • Representing a collection of values where each element has a specific meaning.

  • Returning multiple values from a function.

Time Complexity:

  • Insertion: O(1) - Constant time for inserting elements at predefined positions.

  • Deletion: O(1) - Constant time for deleting elements at specific positions.

  • Search: O(n) - Linear time for searching elements by iterating through the tuple.

Example Code in TypeScript:

ArrayList (Dynamic Arrays)

Definition:
In TypeScript, dynamic arrays can be created using the Array class, which allows for flexible resizing of the array as elements are added or removed. Dynamic arrays automatically handle memory allocation and resizing behind the scenes, making them convenient for managing collections of data that may change in size.

Key Features:

  • Dynamic arrays automatically resize to accommodate new elements.

  • Elements can be added or removed without fixed size constraints.

  • Efficient memory management for resizing operations.

Use Cases:

  • Managing a collection of data where the size is not known in advance.

  • Storing elements that may grow or shrink dynamically.

  • Implementing resizable data structures like lists, stacks, and queues.

Time Complexity:

  • Insertion (End of Array): O(1) - Constant time for adding elements to the end of the array.

  • Insertion (Middle of Array): O(n) - Linear time for inserting elements in the middle, as it may require shifting elements.

  • Deletion (End of Array): O(1) - Constant time for removing elements from the end.

  • Deletion (Middle of Array): O(n) - Linear time for deleting elements in the middle, as it requires shifting elements.

  • Search: O(n) - Linear time for searching elements throughout the array.

Example Code in TypeScript:

Explanation:

  • The push() method adds an element to the end of the array.

  • The pop() method removes the last element from the array.

  • The spread operator (...) can be used to concatenate arrays and resize the dynamic array by adding new elements.

Stack

Definition:
A stack is a linear data structure that follows the Last In First Out (LIFO) principle, where elements are added and removed from the top of the stack. It supports operations like push (adds an element to the top), pop (removes and returns the top element), and peek (returns the top element without removing it).

Key Features:

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

  • Operations: Push (adds an element), Pop (removes the top element), Peek (view the top element).

  • Efficient for managing function calls, undo/redo functionality, and expression evaluation.

Use Cases:

  • Function calls and recursion management in programming.

  • Undo/Redo functionality in text editors and graphic design tools.

  • Expression evaluation in compilers and calculators.

  • Backtracking algorithms in graph traversal.

Time Complexity:

  • Insertion (Push): O(1) - Constant time to add an element to the stack.

  • Deletion (Pop): O(1) - Constant time to remove the top element from the stack.

  • Access (Peek): O(1) - Constant time to view the top element without removing it.

Example Code in TypeScript:

Queue

Definition:
A queue is a linear data structure that follows the First In First Out (FIFO) principle, where elements are added at the rear and removed from the front. It supports operations like enqueue (adds an element to the rear) and dequeue (removes and returns the front element).

Key Features:

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

  • Operations: Enqueue (adds an element to the rear), Dequeue (removes and returns the front element).

  • Efficient for managing processes in the order they arrive and processing tasks sequentially.

Use Cases:

  • Task scheduling in operating systems.

  • Print job management in printer queues.

  • Breadth-first search algorithms in graph traversal.

  • Handling requests in web servers and message queues.

Time Complexity:

  • Insertion (Enqueue): O(1) - Constant time to add an element to the rear of the queue.

  • Deletion (Dequeue): O(1) - Constant time to remove and return the front element.

  • Access (Peek): O(1) - Constant time to view the front element without removing it.

Example Code in TypeScript:

LinkedList

Definition:
A linked list is a data structure made up of nodes where each node contains a value and a reference (pointer) to the next node in the sequence. In a singly linked list, each node points to the next node in the list. In a doubly linked list, each node has pointers to both the next and previous nodes.

Key Features:

  • Dynamic structure where nodes are linked via pointers.

  • Efficient insertion and deletion by adjusting pointers.

  • Flexible size and structure due to dynamic linking of nodes.

Use Cases:

  • Storing and managing data items that need frequent insertion and deletion.

  • Implementing stacks, queues, and hash tables.

  • Memory management in operating systems.

Time Complexity:

  • Insertion (at the beginning): O(1) - Constant time to insert at the beginning of a linked list.

  • Insertion (at the end): O(1) - Constant time with tail reference in a linked list.

  • Insertion (in the middle): O(n) - Linear time as it may require traversing to the specific position.

  • Deletion (at the beginning): O(1) - Constant time to remove the first node.

  • Deletion (at the end): O(n) - Linear time if the tail is not maintained.

  • Deletion (in the middle): O(n) - Linear time as it may require traversal to find the node to delete.

  • Search: O(n) - Linear time to search for an element by traversing the list.

Example Code in TypeScript:

HashMap (or Object/Map)

Definition:
A HashMap, also known as an Object or Map in TypeScript, is a data structure that stores key-value pairs. It allows efficient storage, retrieval, and deletion of values based on a unique key. The key is used to index the value, making lookup operations fast and effective.

Key Features:

  • Stores data as key-value pairs for efficient access.

  • Allows unique keys for each value.

  • Provides fast lookup and retrieval based on keys.

Use Cases:

  • Storing data that needs to be accessed and updated frequently.

  • Implementing associative arrays, dictionaries, and caches.

  • Managing data that requires quick access based on unique identifiers.

Time Complexity:

  • Insertion (Set): O(1) - Constant time to insert a key-value pair.

  • Deletion (Delete): O(1) - Constant time to delete a key-value pair.

  • Search (Get): O(1) - Constant time to retrieve a value based on the key.

Example Code in TypeScript using Map:

Set

Definition:
A Set is a data structure in TypeScript that stores unique elements, ensuring that no duplicates are allowed. It provides methods to add new elements, remove existing elements, and check for the presence of elements in a collection.

Key Features:

  • Stores only unique elements, eliminating duplicates automatically.

  • Efficient for maintaining a collection of distinct values.

  • Provides methods for adding, removing, and checking for the existence of elements.

Use Cases:

  • Eliminating duplicate entries in a list of items.

  • Managing unique identifiers or keys in data processing.

  • Implementing tags, categories, or filters in applications where uniqueness is essential.

Time Complexity:

  • Insertion (Add): O(1) - Constant time to add a new element to the set.

  • Deletion (Delete): O(1) - Constant time to remove an element from the set.

  • Search (Has): O(1) - Constant time to check for the existence of an element in the set.

Example Code in TypeScript:

Binary Search Tree (BST)

Definition:
A Binary Search Tree (BST) is a binary tree data structure where each node has at most two children, referred to as the left child and the right child. In a BST, the left child node contains a value less than the parent node, and the right child node contains a value greater than the parent node.

Key Features:

  • Nodes are organized in a hierarchical order for efficient search operations.

  • Maintains the property that the left subtree values are less than the parent node, and the right subtree values are greater.

  • Supports operations like insertion, deletion, and search with a time complexity optimized for logarithmic search.

Use Cases:

  • Implementing efficient searching and retrieval of data in a sorted order.

  • Providing quick access to data in a hierarchical structure.

  • Sorting data elements in a way that allows for faster search operations.

Time Complexity:

  • Insertion: Average O(log n), Worst-case O(n) - Inserting a new value into the BST.

  • Deletion: Average O(log n), Worst-case O(n) - Removing a value from the BST.

  • Search: Average O(log n) - Searching for a value in the BST.

Example Code in TypeScript:

array