Activity #9: Data Structure in Typescript
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
An array is a collection of elements of the same data type stored in contiguous memory locations. In TypeScript, arrays are objects that provide methods for manipulating the stored elements.
Key Features
Arrays store elements of the same data type
Elements are stored in contiguous memory locations
Each element is identified by an index, starting from 0
Arrays have a fixed size that cannot be changed after initialization
TypeScript arrays can be single-dimensional or multi-dimensional
Use Cases
Storing and manipulating collections of related data
Implementing other data structures like stacks and queues
Performing operations that require random access to elements
Time Complexity
Operation Time Complexity
Access O(1)
Search O(n)
Insert O(n)
Delete O(n)
Example Code in TypeScript
// Declaring an array
const myArray: number[] = [1, 2, 3, 4, 5];
// Accessing an element
console.log(myArray[0]); // Output: 1
// Modifying an element
numbers[2] = 10;
console.log(myArray); // Output: [1, 2, 10, 4, 5]
// Iterating over an array
for (const i = 0; i < numbers.length; i++) {
console.log(myArray[i]);
}
// Using array methods
myArray.push(6);
console.log(myArray); // Output: [1, 2, 10, 4, 5, 6
// Acces the first Array
const firstElement = myArray.myArray(num => num > 3);
console.log(firstElement); // Output: [4, 5, 6]
Tuple
Definition
A tuple in TypeScript is a typed array with a fixed number of elements, where each element can have a different type. Tuples enable the storage of heterogeneous data in a structured manner.
Key Features
Fixed Size: Tuples have a predefined length.
Heterogeneous Types: Each element can be of a different type.
Type Safety: TypeScript enforces type checking based on the defined types at each index.
Destructuring: Supports destructuring for easy access to elements.
Use Cases
Function Parameters: Passing multiple values of different types.
Data Structures: Representing records or data points with fixed attributes.
State Management: Commonly used in React for state and updater functions.
Time Complexity
Operation Time Complexity
Access O(1)
Search O(n)
Insert O(n) (if resizing)
Delete O(n) (if resizing)
Example Code in TypeScript
// Defining a tuple type
type Person = [string, number, string];
// Creating a tuple
const person: Person = ["Christine", 22, "christinemaitom23@gmail.com"];
// Accessing tuple elements
console.log(person[0]); // Output: "Christine"
console.log(person[1]); // Output: 22
console.log(person[2]); // Output: "christinemaitom23@gmail.com"
// Destructuring a tuple
const [name, age, email] = person;
console.log(name); // Output: "Christine"
console.log(age); // Output: 22
console.log(email); // Output: "christinemaitom23@gmail.com"
ArrayList (Dynamic Arrays)
Definition
An ArrayList (or dynamic array) in TypeScript is a resizable array that can grow or shrink in size as elements are added or removed. Unlike static arrays, which have a fixed size, ArrayLists allow for flexible storage of elements.
Key Features
Dynamic Sizing: Automatically adjusts size during runtime.
Heterogeneous Elements: Can store elements of different types.
Built-in Methods: Provides methods like push(), pop(), shift(), and unshift() for easy manipulation.
Type Safety: TypeScript enforces type checking, enhancing code reliability.
Use Cases
Storing collections of items where the number of elements can change, such as user inputs or API responses.
Implementing data structures like stacks and queues.
Managing lists in applications requiring frequent updates.
Time Complexity
Operation Time Complexity
Access O(1)
Search O(n)
Insert O(1) amortized (O(n) worst-case due to resizing)
Delete O(n)
Example Code in TypeScript
// Declaring and initializing an ArrayList (dynamic array)
let dynamicArray: string[] = ["1", "2", "3"];
// Adding elements
dynamicArray.push("Date"); // Adds "Date" to the end
dynamicArray.unshift("Number"); // Adds "Apricot" to the beginning
// Removing elements
dynamicArray.pop(); // Removes the last element ("Date")
dynamicArray.shift(); // Removes the first element ("Number")
// Accessing elements
console.log(dynamicArray[0]); // Output: "2"
// Iterating over the array
for (let dynamicArray of dynamicArray) {
console.log(dynamicArray); // Outputs: 3, 4
}
// Merging two arrays
let moredynamicArray = ["Christine", "DynamicArray"];
let allDynamicArray = [...DynamicArray, ...moreDynamicArray]; // Merges arrays
console.log(allDynamicArray); // Output: ["2", "3", "Christine", "DynamicArray"]
Stack
Definition
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle, meaning the last element added is the first one to be removed. It primarily supports two operations: push (to add an element) and pop (to remove the top element).
Key Features
LIFO Order: The most recently added element is the first to be removed.
Dynamic Size: Can grow or shrink as needed, typically implemented using arrays.
Basic Operations: Common methods include push, pop, peek, is Empty, and size.
Type Safety: TypeScript allows for strong typing of elements within the stack.
Use Cases
Function Call Management: Used in managing function calls (call stack).
Expression Evaluation: Helpful in parsing expressions (infix, postfix).
Backtracking Algorithms: Useful in solving problems like maze navigation and puzzles.
Undo Mechanisms: Implementing undo features in applications.
Time Complexity
Operation Time Complexity
Access O(n)
Search O(n)
Insert O(1)
Delete O(1)
Example Code in TypeScript
class Stack<T> {
private items: T[];
constructor() {
this.items = [];
}
// Add an item to the top of the stack
push(item: T): void {
this.items.push(item);
}
// Remove and return the item from the top of the stack
pop(): T | undefined {
return this.items.pop();
}
// Return the item at the top of the stack without removing it
peek(): T | undefined {
return this.items[this.items.length - 1];
}
// Check if the stack is empty
isEmpty(): boolean {
return this.items.length === 0;
}
// Return the number of items in the stack
size(): number {
return this.items.length;
}
// Clear all items from the stack
clear(): void {
this.items = [];
}
// Print all items in the stack for debugging purposes
print(): void {
console.log(this.items);
}
}
// Usage Example:
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log("Stack contents:");
stack.print(); // Output: [1, 2, 3]
console.log("Top element:", stack.peek()); // Output: Top element: 3
console.log("Stack size:", stack.size()); // Output: Stack size: 3
console.log("Popped element:", stack.pop()); // Output: Popped element: 3
console.log("Stack contents after pop:");
stack.print(); // Output: [10, 20]
console.log("Is stack empty?", stack.isEmpty()); // Output: Is stack empty? false
stack.clear();
console.log("Stack contents after clearing:");
stack.print(); // Output: []
console.log("Is stack empty after clearing?", stack.isEmpty()); // Output: Is stack empty after clearing? true
Queue
Definition
A queue is a linear data structure that follows the FIFO (First In, First Out) principle. It is used to maintain a collection of elements, where the first element added is the first one to be removed. The two primary operations are enqueue (adding an element to the rear of the queue) and dequeue (removing an element from the front of the queue).
Key Features
FIFO Order: Elements are removed in the same order they were added.
Dynamic Size: Can grow or shrink as needed, typically implemented using arrays.
Basic Operations: Common methods include enqueue, dequeue, peek, isEmpty, and size.
Type Safety: TypeScript allows for strong typing of elements within the queue.
Use Cases
Task Scheduling: Used to manage tasks and processes in computer systems.
Breadth-First Search (BFS): Queues are crucial in graph traversal algorithms like BFS.
Message Queues: Fundamental components of message-oriented middleware systems.
Print Queues: Used to manage print jobs sent to printers.
Time Complexity
Operation Time Complexity
Access O(n)
Search O(n)
Insert O(1)
Delete O(1)
Example Code in TypeScript
class Queue<T> {
private items: T[];
constructor() {
this.items = [];
}
// Add an item to the end of the queue
enqueue(item: T): void {
this.items.push(item);
}
// Remove and return the item from the front of the queue
dequeue(): T | undefined {
return this.items.shift();
}
// Return the item at the front of the queue without removing it
peek(): T | undefined {
return this.items[0];
}
// Check if the queue is empty
isEmpty(): boolean {
return this.items.length === 0;
}
// Return the number of items in the queue
size(): number {
return this.items.length;
}
// Clear all items from the queue
clear(): void {
this.items = [];
}
}
// Usage Example:
const queue = new Queue<number>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log("Front item:", queue.peek()); // Output: Front item: 1
console.log("Queue size:", queue.size()); // Output: Queue size: 3
console.log("Dequeued item:", queue.dequeue()); // Output: Dequeued item: 1
console.log("Front item after dequeue:", queue.peek()); // Output: Front item after dequeue: 2
console.log("Is queue empty?", queue.isEmpty()); // Output: Is queue empty? false
queue.clear();
console.log("Queue size after clearing:", queue.size()); // Output: Queue size after clearing: 0
Linked List
Definition
A linked list is a linear data structure where each element (node) contains data and a reference (link) to the next node in the list. The first node is called the head, and the last node points to null. Linked lists provide a way to store collections of data elements that can grow or shrink dynamically.
Key Features
Dynamic Size: Linked lists can grow or shrink in size as needed.
Sequential Access: Elements are accessed sequentially starting from the head.
Flexible Memory Allocation: Nodes can be stored anywhere in memory.
Ease of Insertion/Deletion: Inserting or deleting nodes is efficient, especially at the beginning of the list.
Use Cases
Implementing Stacks and Queues: Linked lists are commonly used to implement these data structures.
Undo/Redo Functionality: Linked lists can efficiently store and manage a sequence of actions for undo/redo operations.
Graph Traversal: Linked lists are useful in representing adjacency lists for graph traversal algorithms.
Memory Management: Linked lists can be used for dynamic memory allocation and deallocation.
Time Complexity
Operation Time Complexity
Access O(n)
Search O(n)
Insert O(1) (at the beginning)
Delete O(1) (at the beginning)
Example:
class Node<T> {
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
class LinkedList<T> {
head: Node<T> | null;
constructor() {
this.head = null;
}
// Append a new node at the end
append(data: T): void {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
// Display the list elements
display(): void {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
// Search for a value in the list
search(data: T): Node<T> | null {
let current = this.head;
while (current) {
if (current.data === data) {
return current; // Found
}
current = current.next; // Move to next node
}
return null; // Not found
}
// Remove a node by value
remove(data: T): void {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next; // Remove head node
return;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next; // Bypass the node to remove it
return;
}
current = current.next; // Move to next node
}
}
}
// Usage Example:
const list = new LinkedList<number>();
list.append(1);
list.append(2);
list.append(3);
console.log("Linked List Elements:");
list.display(); // Output will be 1, 2, 3
const searchResult = list.search(2);
console.log("Search for 2:", searchResult ? searchResult.data : "Not found"); // Output: Search for 2: 2
list.remove(2);
console.log("Linked List after removing 2:");
list.display(); // Output will be 1, 3
Singly Linked List
Definition
Asingly linked listis a linear data structure consisting of a sequence of elements called nodes, where each node contains a data field and a reference (or pointer) to the next node in the sequence. Unlike arrays, which store elements in contiguous memory locations, singly linked lists allow for dynamic memory allocation and efficient insertion and deletion operations due to their non-contiguous nature.
Key Features
Dynamic Size: Singly linked lists can grow and shrink in size dynamically, making them suitable for applications where the number of elements is not known beforehand.
Efficient Insertions/Deletions: Inserting or deleting nodes can be done in constant time O(1)O(1) if the position is known, as it only requires updating pointers.
Unidirectional Traversal: Nodes can only be traversed in one direction, from the head to the tail, which simplifies certain operations but limits flexibility compared to doubly linked lists.
Memory Efficiency: Each node is allocated memory dynamically, allowing for more efficient use of memory compared to static data structures like arrays.
Use Cases
Dynamic Data Storage: When the size of data is unpredictable, such as in applications that require frequent updates.
Implementing Stacks and Queues: Singly linked lists are often used to implement other abstract data types due to their efficient insertion and deletion capabilities.
Memory-Constrained Environments: Useful in systems where memory fragmentation is a concern since nodes can be allocated as needed without requiring contiguous blocks.
Time Complexity
The performance of singly linked lists for common operations can be summarized as follows:
Insertion at Head: O(1)O(1)
Insertion at Tail: O(n)O(n) (unless a tail pointer is maintained)
Deletion from Head: O(1)O(1)
Deletion from Tail: O(n)O(n)
Search: O(n)O(n) (requires traversal from the head to find an element)
Example Code in TypeScript
class SinglylinkedListT> {
data: T;
next: Node<T> | null = null;
constructor(data: T) {
this.data = data;
}
}
class LinkedList<T> {
head: Node<T> | null = null;
// Insert at the beginning
insertFirst(data: T): void {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
// Insert at the end
insertLast(data: T): void {
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;
}
// Remove first node
removeFirst(): void {
if (!this.head) return;
this.head = this.head.next;
}
// Search for a node
search(data: T): Node<T> | null {
let current = this.head;
while (current) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null; // Not found
}
// Print list
printList(): void {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
// Usage Example:
const list = new SinglyLinkedList<number>();
list.insertFirst(1);
list.insertLast(2);
list.insertLast(3);
list.printList(); // Output will be 1, 2, 3
Doubly Linked List
Definition
A**doubly linked list (DLL)**is a type of linked list in which each node contains three components: a data field, a pointer to the next node (next pointer), and a pointer to the previous node (previous pointer). This structure allows for bidirectional traversal of the list, enabling operations to be performed in both forward and backward directions.
Key Features
Bidirectional Traversal: Each node has pointers to both its next and previous nodes, allowing traversal in both directions.
Dynamic Size: Like singly linked lists, doubly linked lists can grow and shrink dynamically, making them flexible for varying data sizes.
Efficient Insertions/Deletions: Inserting or deleting nodes can be done efficiently at both ends or in the middle of the list, as pointers can be easily adjusted.
More Memory Usage: Each node requires additional memory for storing the previous pointer, making DLLs less memory efficient than singly linked lists.
Use Cases
Implementation of Complex Data Structures: Doubly linked lists are often used to implement data structures like deques and certain types of trees.
Browser History Management: They can effectively manage back and forward navigation in web browsers by allowing easy traversal in both directions.
Music Player Playlists: In applications where users can navigate back and forth through songs, DLLs facilitate easy manipulation of playlists.
Time Complexity
The performance of doubly linked lists for common operations can be summarized as follows:
Insertion at Head: O(1)O(1)
Insertion at Tail: O(1)O(1)
Insertion at Specific Position: O(n)O(n) (requires traversal)
Deletion from Head: O(1)O(1)
Deletion from Tail: O(1)O(1)
Deletion from Specific Position: O(n)O(n) (requires traversal)
Search: O(n)O(n) (requires traversal)
Example Code in TypeScript
class DoublyNode<T> {
data: T;
next: DoublyNode<T> | null = null;
prev: DoublyNode<T> | null = null;
constructor(data: T) {
this.data = data;
}
}
class DoublyLinkedList<T> {
private head: DoublyNode<T> | null = null;
private tail: DoublyNode<T> | null = null;
// Add a node to the end of the list
append(data: T): void {
const newNode = new DoublyNode(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail!.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
}
// Delete a node from the list by its value
delete(data: T): void {
let current = this.head;
while (current) {
if (current.data === data) {
if (current.prev) {
current.prev.next = current.next;
} else {
this.head = current.next; // Update head if necessary
}
if (current.next) {
current.next.prev = current.prev;
} else {
this.tail = current.prev; // Update tail if necessary
}
return; // Exit after deletion
}
current = current.next;
}
}
// Display the list elements
display(): void {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
// Usage Example:
const dll = new DoublyLinkedList<number>();
dll.append(1);
dll.append(2);
dll.append(3);
dll.display(); // Output will be 1, 2, 3
dll.delete(2);
dll.display(); // Output will be 1, 3
HashMap (or Map)
Definition
AHashMap(orMap) in TypeScript is a built-in data structure that stores key-value pairs. It allows storing and retrieving data efficiently using unique keys. TheMaptype maintains the insertion order of elements and provides methods for adding, accessing, modifying, and removing key-value pairs.
Key Features
Flexible Key Types: Unlike objects where keys are always strings, Map keys can be of any type, including objects and functions.
Efficient Operations: Map provides constant-time complexity O(1)O(1) for most operations like insertion, deletion, and retrieval.
Ordered Iteration: Map maintains the insertion order of elements, allowing for predictable iteration.
Size Tracking: Map keeps track of the number of key-value pairs it contains, accessible via the
sizeproperty.
Use Cases
Storing Dynamic Data: Map is useful when the keys are not known beforehand or when the keys are of non-string types.
Caching and Memoization: Map can be used to cache results of expensive function calls or to implement memoization techniques.
Maintaining Insertion Order: When the order of elements is important, Map is preferred over objects.
Time Complexity
The performance ofMapfor common operations can be summarized as follows:
Insertion: O(1)O(1)
Deletion: O(1)O(1)
Retrieval: O(1)O(1)
Checking Existence: O(1)O(1)
Iteration: O(n)O(n) (where n is the number of elements)
Example Code in TypeScript
// Create a new Map
const ageMap: Map<string, number> = new Map();
// Add key-value pairs
ageMap.set("Allia", 1);
ageMap.set("Nash", 2);
ageMap.set("Christine", 3);
// Get the value associated with a key
const nashAge = ageMap.get("Nash");
console.log("Nash's age:", nashAge); // Output: Nash's age: 2
// Check if a key exists
const hasChristine = ageMap.has("Christine");
console.log("Does Christine exist?", hasChristine); // Output: Does Christine exist? true
// Delete a key-value pair
ageMap.delete("Christine");
// Get the size of the Map
const size = ageMap.size;
console.log("Size of the Map:", size); // Output: Size of the Map: 2
// Iterate over the Map
ageMap.forEach((value, key) => {
console.log(`Key: ${key}, Value: ${value}`);
});
// Output:
// Key: Allia, Value: 1
// Key: Nash, Value: 2
// Clear the Map
ageMap.clear();
console.log("Map after clearing:", ageMap); // Output: Map after clearing: Map(0) {}
Set
Definition
A Set in TypeScript is a built-in data structure that represents a collection of unique elements. Each element can occur only once, and Sets automatically eliminate duplicates. Unlike arrays, Sets do not maintain any specific order of elements, making them particularly useful for storing distinct values.
Key Features
Uniqueness: Sets enforce uniqueness, ensuring that no duplicate values are stored.
No Order: Elements in a Set are not stored in any specific order, and iteration does not guarantee the order of elements.
Efficient Operations: Sets provide efficient methods for adding, removing, and checking the existence of elements, typically with constant-time complexity for these operations.
Dynamic Size: Sets can grow and shrink dynamically as elements are added or removed.
Use Cases
Removing Duplicates: Sets are ideal for filtering out duplicate values from an array or collection.
Membership Testing: When frequent checks for the existence of values are required, Sets provide efficient membership testing.
Mathematical Set Operations: They can be used to perform operations like union, intersection, and difference on collections of items.
Data Integrity: Ensuring that a collection contains only unique items, such as user IDs or product SKUs.
Time Complexity
The performance of Sets for common operations can be summarized as follows:
Insertion: O(1)O(1)
Deletion: O(1)O(1)
Retrieval (Checking existence): O(1)O(1)
Iteration: O(n)O(n) (where n is the number of elements)
Example Code in TypeScript
// Create a new Set
const mySet = new Set<number>();
// Add elements to the Set
mySet.add(1);
mySet.add(2);
mySet.add(3);
mySet.add(1); // This will be ignored since 1 is already in the Set
// Display the size of the Set
console.log("Size of Set:", mySet.size); // Output: Size of Set: 3
// Check if an element exists in the Set
console.log("Contains 2:", mySet.has(2)); // Output: Contains 2: true
console.log("Contains 4:", mySet.has(4)); // Output: Contains 4: false
// Delete an element from the Set
mySet.delete(2);
console.log("After deleting 2, size of Set:", mySet.size); // Output: After deleting 2, size of Set: 2
// Iterate over the Set elements
for (let number of mySet) {
console.log(number); // Output will be 1 and 3 (order may vary)
}
// Clear all elements from the Set
mySet.clear();
console.log("Size after clearing:", mySet.size); // Output: Size after clearing: 0
Tree (Binary Search Tree)
Definition
A**Binary Search Tree (BST)**is a specialized type of binary tree that maintains a sorted order of its elements. Each node in a BST contains a value, a left child, and a right child. The key property of a BST is that for any given node:
All values in the left subtree are less than or equal to the node's value.
All values in the right subtree are greater than the node's value.
This structure allows for efficient searching, insertion, and deletion operations.
Key Features
Ordered Structure: The BST maintains an ordered structure, which facilitates efficient searching and retrieval.
Dynamic Size: Like other tree structures, the size of a BST can grow and shrink dynamically as nodes are added or removed.
Recursive Operations: Many operations (insert, delete, search) can be implemented recursively, leveraging the tree's hierarchical nature.
No Duplicates: Typically, BSTs do not allow duplicate values, ensuring that each element is unique.
Use Cases
Searching and Sorting: BSTs are commonly used for applications requiring frequent search operations on sorted data.
Database Indexing: They can be used in database systems to index records efficiently.
Memory Management: BSTs can help manage memory in systems where dynamic allocation and deallocation of objects occur frequently.
Implementing Sets and Maps: Many programming languages use BSTs under the hood to implement data structures like sets and maps.
Time Complexity
The performance of Binary Search Trees for common operations can be summarized as follows:
Insertion: O(h)O(h) (where h is the height of the tree; ideally O(logn)O(logn) for balanced trees)
Deletion: O(h)O(h)
Search: O(h)O(h)
Traversal (In-order): O(n)O(n) (where n is the number of nodes)
In the worst case (for unbalanced trees), these operations can degrade toO(n)O(n).
Example Code in TypeScript
class TreeNode<T> {
data: T;
left?: TreeNode<T>;
right?: TreeNode<T>;
constructor(data: T) {
this.data = data;
}
}
class BinarySearchTree<T> {
root?: TreeNode<T>;
// Insert a new value into the BST
insert(data: T): void {
const newNode = new TreeNode(data);
if (!this.root) {
this.root = newNode;
return;
}
let current = this.root;
while (true) {
if (data < current.data) {
if (!current.left) {
current.left = newNode;
return;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return;
}
current = current.right;
}
}
}
// Search for a value in the BST
search(data: T): TreeNode<T> | null {
let current = this.root;
while (current) {
if (data === current.data) {
return current; // Found
} else if (data < current.data) {
current = current.left; // Go left
} else {
current = current.right; // Go right
}
}
return null; // Not found
}
// In-order traversal of the BST
inOrderTraversal(node?: TreeNode<T>): void {
if (node) {
this.inOrderTraversal(node.left);
console.log(node.data);
this.inOrderTraversal(node.right);
}
}
}
// Usage Example:
const bst = new BinarySearchTree<number>();
bst.insert(1);
bst.insert(2);
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(6);
bst.insert(7);
console.log("In-order Traversal:");
bst.inOrderTraversal(bst.root); // Output will be sorted order: 4, 2, 5, 1, 6, 3, 7
const searchResult = bst.search(5);
console.log("Search for 5:", searchResult ? searchResult.data : "Not found"); // Output: Search for 5: 5
Deliverables:
Definition
ADeliverables Data Structureis not a standard data structure like arrays, linked lists, or trees. Instead, it refers to a conceptual model used to manage and organize deliverables in various applications, particularly in project management and software development. This structure can be implemented using various underlying data structures (like arrays or objects) to track tasks, milestones, or outputs of a project.
Key Features
Organization: Deliverables are organized in a way that allows easy access and management of tasks and their statuses.
Hierarchical Structure: Deliverables can be structured hierarchically, allowing for parent-child relationships (e.g., projects containing multiple tasks).
Metadata Storage: Each deliverable can store additional information such as deadlines, responsible persons, and completion status.
Dynamic Updates: The structure allows for dynamic updates as tasks are completed or modified.
Use Cases
Project Management: Used to track tasks and milestones in project management tools.
Software Development: Helps manage features or bug fixes in software development workflows.
Event Planning: Can be used to organize deliverables for events, such as logistics and scheduling.
Product Development: Tracks the progress of product features from conception to delivery.
Time Complexity
The performance of a Deliverables Data Structure will depend on its underlying implementation. If implemented using an array or object:
Insertion: O(1)O(1) (if adding at the end) or O(n)O(n) (if maintaining order)
Deletion: O(n)O(n) (to find and remove an item)
Search: O(n)O(n) (if searching through an array) or O(1)O(1) (if using a hash map for direct access)
Example Code in TypeScript
class Deliverable {
id: number;
title: string;
description?: string;
dueDate?: Date;
completed: boolean;
}
class DeliverablesManager {
private deliverables: Deliverable[] = [];
// Add a new deliverable
addDeliverable(deliverable: Deliverable): void {
this.deliverables.push(deliverable);
}
// Mark a deliverable as completed
completeDeliverable(id: number): void {
const deliverable = this.deliverables.find(d => d.id === id);
if (deliverable) {
deliverable.completed = true;
}
}
// Get all deliverables
getAllDeliverables(): Deliverable[] {
return this.deliverables;
}
// Get pending deliverables
getPendingDeliverables(): Deliverable[] {
return this.deliverables.filter(d => !d.completed);
}
// Remove a deliverable by ID
removeDeliverable(id: number): void {
this.deliverables = this.deliverables.filter(d => d.id !== id);
}
}
// Usage Example
const chris = new DeliverablesManager();
chris.addDeliverable({ id: 1, title: "Design Homepage", completed: false });
chris.addDeliverable({ id: 2, title: "Implement API", completed: false });
console.log("All Deliverables:", chris.getAllDeliverables());
chris.completeDeliverable(1);
console.log("Pending Deliverables:", chris.getPendingDeliverables());
chris.removeDeliverable(2);
console.log("All Deliverables after removal:", chris.getAllDeliverables());
References:
Typescript Data Structures: Stack and Queue - DEV Community
https://www.typescriptlang.org/docs/handbook
https://interviewer.live/typescript/understanding-data-structures-in-typescript-2/