Activity 9: Data Structure in Typescript

Arrays

In TypeScript, arrays serve as user-defined data types that store elements of the same type in contiguous memory locations. These arrays hold multiple values of similar data types and have a fixed size upon declaration without the ability to expand dynamically. Additionally, arrays in TypeScript follow index-based storage where the initial element is stored at index 0 (or 'i') with subsequent elements positioned at 'i+1'. This structured approach enables efficient organization and retrieval of data within arrays in TypeScript.

Key Features

Fixed Size: Arrays have a fixed size, meaning the number of elements is determined at the time of creation and cannot be changed.
Contiguous Memory Allocation: Elements are stored in contiguous memory locations, which allows for efficient access and manipulation.
Index-Based Access: Each element in an array can be accessed directly using its index, providing constant-time access (O(1)).
Homogeneous Elements: Arrays store elements of the same data type, ensuring uniformity.
Static and Dynamic Arrays: Static arrays have a fixed size, while dynamic arrays can resize themselves as needed (e.g., ArrayList in Java, std::vector in C++).

Use Cases

Storing Data: Arrays are used to store collections of data, such as lists of numbers, characters, or objects.
Implementing Other Data Structures: Arrays are the foundation for other data structures like stacks, queues, and heaps.
Matrix Representation: Multidimensional arrays are used to represent matrices and perform matrix operations.
Lookup Tables: Arrays are used in lookup tables and hash tables for quick data retrieval.
Buffer Storage: Arrays serve as buffers in applications like image processing and network data transmission.

Time Complexity

Access: Accessing an element by index is O(1).
Search:
- Unsorted Array: Linear search has a time complexity of O(n).
- Sorted Array: Binary search has a time complexity of O(logn).
Insertion:
- At the End: Inserting an element at the end of a dynamic array is O(1)(amortized).
- At the Beginning or Middle: Inserting an element at the beginning or middle requires shifting elements, resulting inO(n).
Deletion:
- From the End: Deleting an element from the end is O(1).
- From the Beginning or Middle: Deleting an element from the beginning or middle requires shifting elements, resulting in O(n).

Example:

Using unshift: Adds one or more elements to the beginning of an array.

TypeScript

let fruits: string[] = ["banana", "orange"];

fruits.unshift("apple");

console.log(fruits); // Output: [[](https://dev.to/masakifukunishi/understanding-arrays-features-pros-cons-and-time-complexity-3egc)"apple", "banana", "orange"]

Tuple

In TypeScript, tuples are a specific type that allows you to express an array with a fixed number of elements where each element may have a different data type. Tuples provide a way to define and work with data structures that have a specific and fixed number of elements in a specific order.

Key Features

Immutable: Once created, the elements of a tuple cannot be changed. This immutability ensures data consistency.
Ordered: Tuples maintain the order of elements, allowing access via indexing.
Heterogeneous: Tuples can store elements of different data types.
Iterable: Tuples can be looped through, making them useful in various iterations.
Hashable: Tuples can be used as keys in dictionaries, provided all their elements are hashable.
Compact and Memory-Efficient: Tuples use less memory compared to lists due to their immutability and fixed size.

User cases

Fixed Collections: Ideal for storing fixed collections of items, such as coordinates (x, y), RGB color values (red, green, blue), or database records.
Dictionary Keys: Useful as keys in dictionaries because of their immutability.
Function Returns: Often used to return multiple values from a function.
Data Integrity: Ensures data integrity by preventing accidental modification of elements.

Time Complexity

Access (Indexing): O(1) - Constant time complexity for accessing elements by index.
Search: O(n) - Linear time complexity for searching elements, where n is the number of elements.
Insert/Delete: Not applicable - Tuples are immutable, so elements cannot be inserted or deleted once the tuple is created.

Example:

# Defining a tuple

my_tuple = ("apple", "banana", "cherry")

# Accessing elements

first_element = my_tuple[0] # Accessing the first element

second_element = my_tuple[1] # Accessing the second element

last_element = my_tuple[-1] # Accessing the last element using negative indexing

print("First element:", first_element)

print("Second element:", second_element)

print("Last element:", last_element)

my_tuple is defined with three elements: "apple", "banana", and "cherry".

Elements are accessed using their index positions. Indexing starts at 0, so my_tuple[0] gives the first element, my_tuple[1] gives the second element, and my_tuple[-1] gives the last element using negative indexing.

ArrayList (Dynamic Arrays)

In TypeScript, dynamic arrays can be created and managed using the built-in Array type. The Array type allows for dynamic resizing and manipulation of arrays by providing various methods and properties. Dynamic arrays in TypeScript provide flexibility in managing collections of elements that can change in size and content over time.

Key Features

Dynamic Size: Unlike regular arrays, ArrayLists can dynamically resize themselves to accommodate new elements as they are added or removed.
Ordered Collection: ArrayLists maintain the order of elements as they are inserted.
Random Access: Elements can be accessed directly by their index, providing constant-time complexity for retrieval operations (O(1)).
Generic Type: ArrayLists are generic, meaning you can specify the type of elements they will contain.

Use Cases

Dynamic Data Storage: Ideal for scenarios where the number of elements can change frequently, such as in dynamic data structures or when dealing with user inputs.
Random Access: Suitable for applications requiring frequent access to elements by index, like implementing lists, stacks, or queues.
Order Maintenance: Useful when the order of elements needs to be preserved, such as in to-do lists, playlists, or any ordered collection.

Time Complexity

Insertions:
- At the end: Amortized constant time O(1), but O(n) in the worst case when resizing is needed.
- At a specific index: O(n) due to the need to shift elements.
Deletions:
- By index: O(n) because elements need to be shifted to fill the gap.
- By value: O(n) as it involves searching for the element and then shifting.
Search:
- By index: Constant time O(1).
- By value: Linear time O(n) as it involves iterating through the array⁴.

Example:

typescript
// Creating a dynamic array
let dynamicArray: number[] = [1, 2, 3, 4, 5];

// Resizing the array by adding elements
dynamicArray.push(6, 7, 8); // Add elements to the end of the array
console.log(dynamicArray); // Output: [1, 2, 3, 4, 5, 6, 7, 8]

// Manipulating the array by removing elements
dynamicArray.pop(); // Remove the last element
console.log(dynamicArray); // Output: [1, 2, 3, 4, 5, 6, 7]

dynamicArray.shift(); // Remove the first element
console.log(dynamicArray); // Output: [2, 3, 4, 5, 6, 7]

dynamicArray.splice(2, 2); // Remove 2 elements starting from index 2
console.log(dynamicArray); // Output: [2, 3, 6, 7]

// Using array methods for manipulation
let squaredNumbers = dynamicArray.map(num => num * num); // Square each element
console.log(squaredNumbers); // Output: [4, 9, 36, 49]

let sum = dynamicArray.reduce((acc, curr) => acc + curr, 0); // Calculate sum of all elements
console.log(sum); // Output: 20

let indexOfSeven = dynamicArray.indexOf(7); // Find the index of value 7
console.log(indexOfSeven); // Output: 3

let containsFive = dynamicArray.includes(5); // Check if the array contains value 5
console.log(containsFive); // Output: true

Stack

A stack uses LIFO (last-in-first-out) ordering, the most recent item added is the first item to be removed, just like a real stack. Some uses of this data structure are expressions evaluations and conversion (prefix, postfix, and infix), backtracking, and memory management. Push operations and pop operations are the terms used to describe the addition and removal of elements from stacks, respectively.

Key Features

LIFO Principle: Stacks operate on a Last In, First Out (LIFO) basis, meaning the last element added is the first one to be removed.
Single Access Point: All operations (push, pop, peek) occur at one end of the stack, known as the top.
Dynamic Size: Stacks can grow and shrink dynamically, depending on the implementation.
Efficient Operations: Push, pop, and peek operations typically have constant time complexity, making them very efficient.
Limited Access: Only the top element is accessible for modification or removal.

Use Cases

Function Call Management: Used in programming languages to manage function calls and maintain the execution context.
Expression Evaluation: Useful in evaluating arithmetic expressions, postfix expressions, and infix-to-postfix conversions.
Undo/Redo Mechanisms: Implemented in text editors and graphic design software to revert or redo actions.
Backtracking Algorithms: Essential in algorithms like depth-first search (DFS), maze solving, and pathfinding.
Browser History: Used to manage the forward and backward navigation in web browsers.

Time Complexity

Push (Insert): O(1)

- Adding an element to the top of the stack is a constant time operation.
Pop (Delete): O(1)

- Removing the top element is also a constant time operation
Peek (Access Top Element): O(1)

- Accessing the top element without removing it is a constant time operation.

Example:

class Stack<T> {

private items: T[] = [];

// Add an item to the stack

public push(item: T): void {

this.items.push(item);

}

// Remove and return the top item of the stack

public pop(): T | undefined {

return this.items.pop();

}

// Return the top item of the stack without removing it

public peek(): T | undefined {

return this.items[this.items.length - 1];

}

// Check if the stack is empty

public isEmpty(): boolean {

return this.items.length === 0;

}

// Get the size of the stack

public size(): number {

return this.items.length;

}

}

// Example usage:

const stack = new Stack<number>();

stack.push(1);

stack.push(2);

stack.push(3);

console.log(stack.peek()); // 3

console.log(stack.size()); // 3

console.log(stack.pop()); // 3

console.log(stack.size()); // 2

console.log(stack.isEmpty()); // false

console.log(stack.pop()); // 2

console.log(stack.pop()); // 1

console.log(stack.isEmpty()); // true

Queue

Queues are data structures that follow the First-In-First-Out (FIFO) principle. In simple terms, the first element added to the queue will be the first one to be removed.

Key Features

FIFO (First In, First Out): The primary characteristic of a queue is that it follows the FIFO principle. The first element added to the queue will be the first one to be removed.
Enqueue Operation: Adding an element to the end of the queue.
Dequeue Operation: Removing an element from the front of the queue.
Peek Operation: Viewing the element at the front of the queue without removing it.
Size: Keeping track of the number of elements in the queue.
IsEmpty: Checking if the queue is empty.

Use Cases

Task Scheduling: Queues are used in operating systems for managing tasks in a time-sharing system.
Print Queue: Managing print jobs in a printer.
Breadth-First Search (BFS): Used in graph traversal algorithms.
Buffer Handling: Used in handling buffers in IO operations, like keyboard input.
Messaging Systems: Used in message queues for asynchronous communication between different parts of a system.

Time Complexity

Enqueue (Insert): O(1)
Dequeue (Delete): O(1)
Peek (Search): O(1)

Example:

Here’s a simple implementation of a queue in TypeScript:

TypeScript

class Queue<T> {

private storage: T[] = [];

private capacity: number;

constructor(capacity: number = Infinity) {

this.capacity = capacity;

}

enqueue(item: T): void {

if (this.size() === this.capacity) {

throw new Error("Queue has reached max capacity, you cannot add more items");

}

this.storage.push(item);

}

dequeue(): T | undefined {

return this.storage.shift();

}

peek(): T | undefined {

return this.storage[0];

}

size(): number {

return this.storage.length;

}

isEmpty(): boolean {

return this.size() === 0;

}

}

// Example usage:

const queue = new Queue<number>(5);

queue.enqueue(1);

queue.enqueue(2);

queue.enqueue(3);

console.log(queue.dequeue()); // Output: 1

console.log(queue.peek()); // Output: 2

console.log(queue.size()); // Output: 2

console.log(queue.isEmpty()); // Output: false

AI-generated code. Review and use carefully.

This code defines a generic Queue class with methods to enqueue, dequeue, peek, check the size, and determine if the queue is empty. The example usage demonstrates how to create a queue, add elements, remove elements, and check its properties.

LinkedList

A linked list is a linear data structure that consists of a series of nodes connected by pointers (in C or C++) or references (in Java, Python and JavaScript). Each node contains data and a pointer/reference to the next node in the list. Unlike arrays, linked lists allow for efficient insertion or removal of elements from any position in the list, as the nodes are not stored contiguously in memory.A linked list is a fundamental data structure in computer science. It mainly allows efficient insertion and deletion operations compared to arrays. Like arrays, it is also used to implement other data structures like stack, queue and deque.

Key Features

Dynamic Size: LinkedLists can grow or shrink in size during program execution, unlike arrays which have a fixed size.
Efficient Insertions/Deletions: Inserting or deleting elements, especially at the beginning or middle of the list, is efficient since it only involves updating pointers.
Sequential Access: LinkedLists allow for efficient sequential access, making them suitable for applications that require frequent traversal.
Memory Utilization: They use memory efficiently by allocating memory as needed, avoiding the need for contiguous memory allocation.
Types: There are different types of LinkedLists, including singly linked lists (one direction traversal), doubly linked lists (both directions traversal), and circular linked lists (last node points to the first node).

Use Cases

Dynamic Data Structures: When the size of the data structure is not known in advance or changes frequently.
Frequent Insertions/Deletions: Applications that require frequent insertions and deletions, such as implementing stacks, queues, and deques.
Sorted Data: Maintaining sorted data where elements need to be inserted in a sorted order.
Graph Adjacency Lists: Representing graphs where each node points to its adjacent nodes.
Memory Management: Implementing memory management algorithms like garbage collection.

Time Complexity

Insertion:
- At the beginning: O(1)
- At the end (singly linked list): O(n) (due to traversal)
- At the end (doubly linked list): O(1)
- At a specific position: O(n) (due to traversal)
Deletion:
- At the beginning: O(1)
- At the end (singly linked list): O(n)(due to traversal)
- At the end (doubly linked list): O(1)
- At a specific position: O(n) (due to traversal)
Search:
- By value: O(n) (linear search)
Access by Index: O(n)

Example:

class Node:

def init(self, data):

self.data = data

self.next = None

class LinkedList:

def init(self):

self.head = None

def add_node(self, data):

"""Add a node to the end of the linked list."""

new_node = Node(data)

if not self.head:

self.head = new_node

return

last_node = self.head

while last_node.next:

last_node = last_node.next

last_node.next = new_node

def remove_node(self, key):

"""Remove the first node with the specified key."""

current_node = self.head

# If the node to be deleted is the head node

if current_node and current_node.data == key:

self.head = current_node.next

current_node = None

return

# Otherwise, search for the node to be deleted

while current_node and current_node.next:

if current_node.next.data == key:

current_node.next = current_node.next.next

return

current_node = current_node.next

def traverse(self):

"""Traverse the linked list and print the nodes."""

current_node = self.head

while current_node:

print(current_node.data, end=' ')

current_node = current_node.next

print() # for new line

# Example Usage

if name == "__main__":

linked_list = LinkedList()

# Adding nodes

linked_list.add_node(1)

linked_list.add_node(2)

linked_list.add_node(3)

print("Linked List after adding nodes:")

linked_list.traverse() # Output: 1 2 3

# Removing a node

linked_list.remove_node(2)

print("Linked List after removing node with data 2:")

linked_list.traverse() # Output: 1 3

# Removing the head node

linked_list.remove_node(1)

print("Linked List after removing node with data 1:")

linked_list.traverse() # Output: 3

# Trying to remove a non-existing node

linked_list.remove_node(4) # Should do nothing

print("Linked List remains the same after trying to remove non-existing node 4:")

linked_list.traverse() # Output: 3

HashMap (or Object/Map)

A HashMap is a data structure that allows you to store and manage key-value pairs. They are also called Hash Table or Dictionary (in python) data structure. Unlike arrays or lists, where you access elements using an index, HashMaps let you use a "key" to find the corresponding "value."
Key Features

Key-Value Pairs: HashMap stores data in key-value pairs, where each key is unique.
Hashing: Utilizes a hash function to compute an index into an array of buckets or bins, from which the desired value can be found.
Null Values: Allows one null key and multiple null values.
Non-Synchronized: Not thread-safe by default but can be synchronized externally.
Order: Does not maintain any order of the keys or values.

Use Cases

Fast Lookup: Ideal for scenarios requiring quick access to data, such as caching.
Database Indexing: Used in databases to index data for fast retrieval.
Counting Frequencies: Useful for counting occurrences of elements, like word frequency in a document.
Associative Arrays: Acts as a dictionary to map keys to values, similar to associative arrays in other languages.

Time Complexity

Insertion (put): Average case O(1), worst case O(n) if many collisions occur.
Deletion (remove): Average case O(1), worst case O(n).
Search (get): Average case O(1), worst case O(n).

Example:

// Using a plain object as a hash map const hashMap: { [key: string]: string } = {}; // Setting values hashMap["1"] = "One"; hashMap["2"] = "Two"; hashMap["3"] = "Three"; // Getting values console.log(hashMap["2"]); // Output: Two // Checking if a key exists console.log("3" in hashMap); // Output: true // Iterating through keys for (const key in hashMap) { if (hashMap.hasOwnProperty(key)) { console.log(`${key}: ${hashMap[key]}`); } } // Removing an entry delete hashMap["1"]; // Display the hashMap after deletion console.log(hashMap);

Set

In TypeScript, a Set is a collection of unique values that does not allow duplicate elements. A set is implemented with the Set object, which is part of the ECMAScript 2015 (ES6) specification and fully supported in TypeScript.
Key Features

Unordered Collection: Sets are collections of unique elements without any specific order.
No Duplicates: Each element in a set is unique. If you try to add a duplicate, it will be ignored.
Mutable: Elements can be added or removed from a set.
Efficient Membership Testing: Checking if an element is in a set is generally very fast.

Use Cases

Removing Duplicates: Sets are often used to eliminate duplicate values from a list or array.
Membership Testing: Quickly check if an element exists in a collection.
Mathematical Operations: Perform union, intersection, and difference operations on sets.
Graph Algorithms: Used in algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS) to keep track of visited nodes.

Time Complexity

Insert: Average case is O(1), but can degrade to O(n) in the worst case due to hash collisions.
Delete: Average case is O(1), worst case is O(n).
Search: Average case is O(1), worst case is O(n).

These complexities assume a well-implemented hash table under the hood, which is common in many programming languages.

Example:

// Creating a Set to store unique subjects

const subjects = new Set<string>();

// Adding subjects to the Set

subjects.add('Mathematics');

subjects.add('Physics');

subjects.add('Chemistry');

subjects.add('Biology'); // This will be added as it's not a duplicate

// Checking if a subject is in the Set

console.log(subjects.has('Physics')); // Outputs: true //

Deleting a subject from the Set subjects.delete('Biology');

// Checking the size of the Set console.log(subjects.size); // Outputs the number of elements in the Set // Iterating over the Set of subjects for (let subject of subjects) { console.log(subject); }

// or using forEach subjects.forEach((subject) => { console.log(subject); });

Tree

A Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node. This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.
Key Features

Nodes: Each node contains a key (value) and pointers to its left and right children.
Binary Property: Each node has at most two children.
Search Property: For any node, all keys in its left subtree are less than the node’s key, and all keys in its right subtree are greater.

Use Cases

Searching: Efficiently find elements.
Sorting: In-order traversal of a BST gives elements in sorted order.
Dynamic Set Operations: Insert, delete, and find minimum/maximum operations.

Time Complexity

Insert: Average case (O(\log n)), Worst case (O(n))
Delete: Average case (O(\log n)), Worst case (O(n))
Search: Average case (O(\log n)), Worst case (O(n))

Example:

Here’s a simple implementation of a BST in TypeScript:

TypeScript

class TreeNode {

key: number;

left: TreeNode | null;

right: TreeNode | null;

constructor(key: number) {

this.key = key;

this.left = null;

this.right = null;

}

class BinarySearchTree {

root: TreeNode | null;

constructor() {

this.root = null;

}

insert(key: number): void {

const newNode = new TreeNode(key);

if (this.root === null) {

this.root = newNode;

} else {

this.insertNode(this.root, newNode);

}

private insertNode(node: TreeNode, newNode: TreeNode): void {

if (newNode.key < node.key) {

if (node.left === null) {

node.left = newNode;

} else {

this.insertNode(node.left, newNode);

}

} else {

if (node.right === null) {

node.right = newNode;

} else {

this.insertNode(node.right, newNode);

}

search(key: number): TreeNode | null {

return this.searchNode(this.root, key);

}

private searchNode(node: TreeNode | null, key: number): TreeNode | null {

if (node === null) {

return null;

}

if (key < node.key) {

return this.searchNode(node.left, key);

} else if (key > node.key) {

return this.searchNode(node.right, key);

} else {

return node;

}

// Example usage:

const bst = new BinarySearchTree();

bst.insert(10);

bst.insert(5);

bst.insert(15);

console.log(bst.search(10)); // TreeNode { key: 10, left: TreeNode, right: TreeNode }

console.log(bst.search(7)); // null

Deliverables

Deliverables are specific outputs, products, or results that must be achieved and provided to fulfill the requirements of a project. They are the tangible or intangible items produced as a result of project activities.

Key Features

Specific: Clearly defined and unambiguous.
Measurable: Quantifiable to assess progress and completion.
Time-bound: Associated with deadlines.
Client-oriented: Aligned with stakeholder requirements.
Quality-focused: Must meet predefined quality standards.

Use Cases

Project Management: To track progress and ensure project goals are met.
Software Development: To deliver features, updates, or complete software products.
Construction: To provide completed structures or components.
Marketing: To produce campaign materials or reports.

Time Complexity

Insert: O(1) - Adding a new deliverable to a list.
Delete: O(n) - Removing a deliverable, where n is the number of deliverables.
Search: O(n) - Finding a specific deliverable in a list.

Example Code in TypeScript

Here’s a TypeScript code snippet demonstrating how to manage deliverables:

TypeScript

class Deliverable {

constructor(public id: number, public name: string, public status: string) {}

}

class Project {

private deliverables: Deliverable[] = [];

addDeliverable(deliverable: Deliverable): void {

this.deliverables.push(deliverable);

}

removeDeliverable(id: number): void {

this.deliverables = this.deliverables.filter(d => d.id !== id);

}

findDeliverable(id: number): Deliverable | undefined {

return this.deliverables.find(d => d.id === id);

}

listDeliverables(): Deliverable[] {

return this.deliverables;

}

// Example usage

const project = new Project();

project.addDeliverable(new Deliverable(1, "Initial Design", "Completed"));

project.addDeliverable(new Deliverable(2, "Prototype", "In Progress"));

console.log(project.listDeliverables());

console.log(project.findDeliverable(1));

project.removeDeliverable(1);

console.log(project.listDeliverables());

AI-generated code. Review and use carefully.

This code defines a Deliverable class and a Project class to manage a list of deliverables, demonstrating basic operations like adding, removing, and finding deliverables.