Activity 9: Data Structure in Typescript
TypeScript
- being a superset of JavaScript, offers all of the common data structures available in JavaScript but enhances them with static typing. This ensures that data structures are more robust, safe, and predictable. Let's explore these data structures in TypeScript and how its typing system enhances their use.
1. Arrays
Definition: An array is a collection of elements stored at contiguous memory locations. It can store a fixed-size sequence of elements of the same type.
Key Features:
Indexed access to elements.
Fixed size in some languages (though not in TypeScript/JavaScript).
Elements are stored in contiguous memory locations.
Supports random access using indices.
Use Cases:
- Suitable for scenarios where you need fast access to elements using an index (e.g., working with matrices, storing data in a linear fashion).
Time Complexity:
Access: O(1)
Insert: O(n) (worst case when inserting at the start)
Delete: O(n)
Search: O(n) (for unsorted arrays)
Example Code in TypeScript:
Link of reference: https://www.geeksforgeeks.org/typescript-arrays/?ref=gcse_ind
2. Linked List
Definition: A linked list is a data structure where elements (nodes) are stored in a linear order, but each element points to the next one in the sequence.
Key Features:
Dynamically sized.
Each element (node) contains a value and a reference (or pointer) to the next node.
Sequential access.
Types: Singly Linked List, Doubly Linked List.
Use Cases:
When dynamic memory allocation is needed.
Efficient insertion/deletion at the beginning, middle, or end.
Time Complexity:
Access: O(n)
Insert: O(1) (at head), O(n) (at arbitrary position)
Delete: O(1) (at head), O(n) (at arbitrary position)
Search: O(n)
Example Code in TypeScript:
Link of Reference:https://ricardoborges.dev/data-structures-in-typescript-linked-list
3. Stack
Definition: 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:
Push (insert) and pop (remove) operations.
Operates on a LIFO basis.
Use Cases:
Undo/redo functionality in text editors.
Evaluating expressions in compilers.
Reversing strings.
Time Complexity:
Access: O(n)
Insert (push): O(1)
Delete (pop): O(1)
Search: O(n)
Example Code in TypeScript:
Link for Reference: https://www.geeksforgeeks.org/how-to-create-a-stack-in-typescript-using-an-array/?ref=header_outind
4. Queue
Definition: A queue is a linear data structure that follows the First In First Out (FIFO) principle, where elements are added at the back and removed from the front.
Key Features:
Enqueue (insert) and dequeue (remove) operations.
Operates on a FIFO basis.
Use Cases:
Managing tasks in a scheduling system.
Breadth-first search (BFS) in graphs.
Print job management.
Time Complexity:
Access: O(n)
Insert (enqueue): O(1)
Delete (dequeue): O(1)
Search: O(n)
Example Code in TypeScript:
Link for References: https://dev.to/glebirovich/typescript-data-structures-stack-and-queue-hld
5. Set
Definition: A set is a collection of unique elements, meaning no duplicates are allowed.
Key Features:
Only unique elements.
No order of elements.
Use Cases:
Checking for duplicates in collections.
Operations like union, intersection, and difference between sets.
Time Complexity:
Insert: O(1)
Delete: O(1)
Search: O(1)
Example Code in TypeScript:
Link for References: https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba
6. Map
Definition: A map is a collection of key-value pairs, where each key is unique.
Key Features:
Key-value pairs.
Efficient lookup, insert, and delete operations by key.
Use Cases:
Storing data with unique keys (e.g., dictionaries).
Caching data.
Time Complexity:
Insert: O(1)
Delete: O(1)
Search: O(1)
Example Code in TypeScript:
Link for References: https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba
7. Binary Search Tree (BST)
Definition: A binary search tree is a hierarchical structure where each node has at most two children (left and right), and the left child is smaller than the parent, while the right child is greater.
Key Features:
Dynamic structure.
Elements are stored in a hierarchical order.
Use Cases:
Efficient searching, insertion, and deletion.
Managing sorted data.
Time Complexity:
Access: O(log n) (in a balanced tree), O(n) (in an unbalanced tree)
Insert: O(log n) (balanced), O(n) (unbalanced)
Delete: O(log n) (balanced), O(n) (unbalanced)
Search: O(log n) (balanced), O(n) (unbalanced)
Example Code in TypeScript:
Link for References: https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba
Tuples in TypeScript
Definition
A tuple in TypeScript is a fixed-length array that can contain values of different types. Each element in a tuple has a specific, predefined type, which makes tuples more restrictive than regular arrays. Unlike arrays, where all elements must have the same type, tuples can contain elements of various types, and their length is fixed once defined.
Key Differences from Arrays:
Fixed Length: Once a tuple is declared, its length is fixed and cannot be changed, whereas an array's length can grow or shrink.
Different Types: Tuples can hold values of different types, whereas arrays typically contain elements of the same type.
Static Typing: The type of each element in the tuple is known and enforced by TypeScript, while arrays generally enforce types across all elements.
Use Cases:
- Tuples are often used when you need to group multiple pieces of data with different types, such as returning multiple values from a function, or representing a record with fixed attributes like a name, age, and status.
Example of Defining and Accessing Tuple Elements:
Link for References: https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba
ArrayList (Dynamic Arrays) in TypeScript
Definition
A dynamic array, or ArrayList, in TypeScript is an array whose size can dynamically grow or shrink as needed. TypeScript uses JavaScript's built-in array mechanism, which supports resizing without explicit management, unlike static arrays in some other languages where array sizes must be predetermined.
Key Features:
Flexible Size: Dynamic arrays can grow or shrink as elements are added or removed.
Efficient Memory Management: The resizing of dynamic arrays is handled internally, and the programmer doesn't need to manually reallocate memory.
Same Type Elements: While arrays in TypeScript often contain elements of the same type, TypeScript also allows union types for arrays, if needed.
Managing Dynamic Arrays:
Dynamic arrays can be manipulated using a variety of methods:
.push(): Add an element to the end of the array..pop(): Remove an element from the end of the array..shift(): Remove an element from the beginning of the array..unshift(): Add an element to the beginning of the array..splice(): Add or remove elements from any position within the array.
Resizing in Dynamic Arrays:
In TypeScript/JavaScript, when the capacity of the array is reached and new elements are added, the runtime automatically resizes the array by allocating more memory. This resizing happens behind the scenes, so the developer doesn’t need to explicitly manage memory.
Use Cases:
Dynamic arrays are ideal for cases where the number of elements is not known in advance and may change frequently. They are used in situations like:
Storing user input.
Managing a dynamic list of items (like a to-do list).
Storing results from database queries or computations, where the size of the data set is unpredictable.
Example of Resizing or Manipulating Dynamic Arrays:
Link for References: https://medium.com/@ilimalbayrak/mastering-typescript-exploring-data-structures-and-algorithms-part-i-47d58e6195ba
