Data Structure and Algorithm PDF

Page 1 of 34 DATA STRUCTURE AND ALGORITHM Recap: DATA DATA TYPE DATA STRUCTURE ABSTRACT DATA TYPES...

Page 1 of 34 DATA STRUCTURE AND ALGORITHM Recap: DATA DATA TYPE DATA STRUCTURE ABSTRACT DATA TYPES (ADTs) Definition Data represents A classification of data Organized ways to A conceptual raw facts or that specifies: store and manage model that information that 1.​ What kind of data data so that it can defines the we process or a variable can hold. be accessed and behavior and store. 2.​ What operations modify efficiently. operations of a can be performed data structure, on that data. without Can be: specifying how Categories: Linear Data it's ​ Primitive Data Structure implemented. Types: Directly Arranged in a supported by SEQUENTIAL Focuses on programming manner like array, what languages (e.g., int, queue, stack and operations you float, char). linked list can perform, ​ Non-Primitive not how data is Data Types: Non-Linear Data stored. Derived types that Structure group or organize Not arranged in data (e.g., arrays, linear fashion lists, classes). Like graph and tree Role The raw Classify and define Provide efficient Define rules information that is how data is stored and ways to store and and behavior stored or what operations are manage data. for managing processed. allowed. data, focusing on WHAT to do rather than how it works. Examples Number = 14 Integer (int): Stores ​Array: Stores Stack: Follows Text: “Hello, whole numbers like 10, multiple items of a Last In, First World” -5. the same type in a Out (LIFO) Measurement: contiguous block of order (e.g., 50kg String (str): Stores memory. undo text like "example". ​Linked List: functionality in Stores items where applications). each item points to the next one, like a Queue: Follows chain. a First In, First ​Tree: Represents Out (FIFO) hierarchical order (e.g., relationships, such customer as a family tree. service line).  Page 2 of 34 ​Graph: Represents networks, like social connections or roads. Key Point DATA is the DATA TYPES define A DATA ADTs describe building block how data is stored and STRUCTURE is a the logical for all what you can do with container that behavior of computational it. organizes and data, leaving processes. stores data. implementation details to the programmer. ARRAY VS LINKED-LIST ARRAY LINKED LIST DEFINITION A LINEAR data structure where elements A collection of nodes, where are of the same data type stored in each node contains DATA and a contiguous memory locations, each POINTER (or link) to the next identified by at least one array index or node. key. Source: https://blog.garybricks.com/a-beginners-overview-of-linked-lists-in-python Aspect Array Linked List Memory Allocation Contiguous memory allocation Non-contiguous memory allocation O(1) for accessing elements (direct Access Time O(n) for traversal (no direct indexing) indexing) Insertion/Deletion Costly (requires shifting elements) Efficient (requires pointer adjustment) Fixed size, resizing requires Dynamic Size Dynamic size, no resizing overhead copying elements  Page 3 of 34 Aspect Array Linked List Requires less memory (no extra Requires extra memory for pointers Memory Usage pointers) (next node links) Cache Poorer due to scattered memory Better due to locality of reference Performance locations More complex due to pointer Implementation Simple to implement management ARRAY LINKED-LIST STRENGTHS Fast Access: Direct indexing makes Dynamic Size: Grows or shrinks as it fast for accessing elements. needed, without resizing. Simple Structure: Easy to implement and use. Efficient Insert/Delete: Can add or Cache-Friendly: Stores data remove elements without shifting, contiguously, making it faster for only the address needs to be sequential operations. updated in the required pointers. WEAKNESSE Fixed Size: Cannot dynamically Slow Access: No direct access; S resize; you must know the maximum must traverse the list sequentially. size in advance. Higher Memory Overhead: Insertion/Deletion: Expensive, as Requires additional memory for elements need to be shifted to pointers. maintain order. Cache-Unfriendly: Non-contiguous storage leads to slower performance for large datasets. Use Cases: When to Use What? Scenario Use Array Use Linked List Fixed size, fast access required ✅ ❌ Frequent insertions/deletions in the middle ❌ ✅ Memory efficiency is critical ✅ ❌ Unknown size at runtime ❌ ✅ Need random access to elements ✅ ❌ Sequential processing or traversal ✅ ✅ (but slower than arrays) Real-Life Analogy  Page 4 of 34 ​ Array: Imagine a row of lockers, each with a number. You can directly access locker #5 without opening others. ​ Linked List: Imagine a scavenger hunt where each clue leads to the next clue. To get to the 5th clue, you must follow the chain sequentially. EXAMPLE ARRAY IMPLEMENTATION LINKED-LIST IMPLEMENTATION # Array example # Linked List example in Python class Node: array = [10, 20, 30, 40, 50] def __init__(self, data): print(array) # Output: 30 self.data = data self.next = None # Create nodes node1 = Node(10) node2 = Node(20) node3 = Node(30) # Link nodes node1.next = node2 node2.next = node3 # Traverse the list current = node1 while current: print(current.data) current = current.next OUTPUT  Page 5 of 34 STACK o​ A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last item added/inserted to the stack is the first one to be removed. Think of a stack like a stack of plates: ​ You add plates on top (Push operation). ​ You remove plates from the top (Pop operation). This means the LAST element ADDED is the FIRST one REMOVED, making stacks ideal for scenarios where you need to reverse order or trace back through actions. Basic Operations Source: https://blog.cipherschools.com/post/what-are-the-three-stack-methods Note: Insertion (push) and Deletion (pop) are done only from the TOP of the stack 1.​ Push: Adds an item to the top of the stack. 2.​ Pop: Removes and returns the top item from the stack.  Page 6 of 34 3.​ Peek (or Top): Returns the top item without removing it. 4.​ IsEmpty: Checks if the stack is empty to prevent performing operations on an empty stack.. isEmpty() conventionally returns a boolean value: True if size is 0, else False. 5.​ IsFull (optional in fixed-sized stacks): Checks if the stack has reached its maximum capacity. Source: https://techvidvan.com/tutorials/wp-content/uploads/sites/2/2021/06/Stack-normal-images02.jpg Page 7 of 34  Page 8 of 34 INPUT-PROCESS-OUTPUT (IPO) Model INPUT PROCESS OUTPUT stack (array), top (integer), ALGORITHM Updated stack with the maxSize (integer), value value added on top (any) 1.​If top == maxSize – 1, then: Print “Stack Overflow” Exit 2. Increment top by 1 3. stack[top] = value 4. Print “Value pushed successfully” Simulations: top = -1 maxSize=4 -1 == (4-1) -1 == 3? N top = -1 + 1 = 0 stack = ‘A’ top = 0 maxSize=4 0 == (4-1) 0 == 3? N top = 0 + 1 = 1 stack = ‘B’ top = 1 maxSize=4 1 == (4-1) 1 == 3? N top = 1 + 1 = 2 stack = ‘C’ top = 2 maxSize=4 2 == (4-1) 2 == 3? N top = 2 + 1 = 3  Page 9 of 34 stack = ‘D’ top = 3 maxSize=4 3 == (4-1) 3 == 3? Y Stack Overflow APPROACHES TO HANDLE WHEN ATTEMPTING TO PUSH IN A FULL STACK 1.​ Check Full Prevents errors by ensuring space is available before pushing. OUTPUT  Page 10 of 34 ================= class Stack: def __init__(self, size): self.stack = [None] * size # Initialize stack with a fixed size self.top = -1 # Top index starts at -1, indicating the stack is empty self.size = size # Set the maximum size of the stack def is_full(self): # Check if the top index has reached the maximum size of the stack return self.top == self.size - 1 def push(self, element): # Before adding an element, check if the stack is already full if self.is_full(): print("Stack is full! Cannot push:", element) else: # Increment the top index and add the element at the new top position self.top += 1 self.stack[self.top] = element print(f"Pushed: {element}") # Display the current stack contents print("Current Stack:", self.stack[:self.top + 1]) # Example usage stack = Stack(3) # Create a stack with a size of 3 stack.push(10) # Push 10 onto the stack stack.push(20) # Push 20 onto the stack stack.push(30) # Push 30 onto the stack stack.push(40) # Attempt to push 40 onto the stack, should print a warning 2.​ Exceptio n Useful when you want strict enforcement and error handling.  Page 11 of 34 OUTPUT  Page 12 of 34 ================== class StackOverflowError(Exception): """Custom exception for stack overflow""" pass class Stack: def __init__(self, size): self.stack = [None] * size # Initialize stack with a fixed size self.top = -1 # Top index starts at -1, indicating the stack is empty self.size = size # Set the maximum size of the stack def is_full(self): # Check if the top index has reached the maximum size of the stack return self.top == self.size - 1 def push(self, element): # Check if the stack is full before pushing if self.is_full(): # Raise a custom exception if the stack is full raise StackOverflowError(f"Cannot push: {element}. Stack is full!") else: # Increment the top index and add the element at the new top position self.top += 1 self.stack[self.top] = element print(f"Pushed: {element}") # Display the current stack contents print("Current Stack:", self.stack[:self.top + 1]) # Example usage try: stack = Stack(3) # Create a stack with a size of 3 stack.push(10) # Push 10 onto the stack stack.push(20) # Push 20 onto the stack stack.push(30) # Push 30 onto the stack stack.push(40) # Attempt to push 40 onto the stack, should raise an exception except StackOverflowError as e: print(e) # Handle the exception and print the error message 3.​ Resize Ideal for dynamic applications where stack size isn't fixed.  Page 13 of 34 OUTPUT Page 14 of 34  Page 15 of 34 =============== class Stack: def __init__(self, size): self.stack = [None] * size # Initialize stack with a fixed initial size self.top = -1 # Top index starts at -1, indicating the stack is empty self.size = size # Set the initial size of the stack def is_full(self): # Check if the stack is full return self.top == self.size - 1 def resize_stack(self): # Double the size of the stack self.size *= 2 new_stack = [None] * self.size # Create a new stack with the larger size # Copy elements from the old stack to the new stack for i in range(self.top + 1): new_stack[i] = self.stack[i] self.stack = new_stack # Replace the old stack with the new stack print(f"Stack resized to: {self.size}") def push(self, element): # If the stack is full, resize it if self.is_full(): print(f"Stack is full! Resizing from {self.size} to {self.size * 2}...") self.resize_stack() # Increment the top index and add the element at the new top position self.top += 1 self.stack[self.top] = element print(f"Pushed: {element}") # Display the current stack contents print("Current Stack:", self.stack[:self.top + 1]) # Example usage stack = Stack(3) # Create a stack with an initial size of 3 stack.push(10) # Push 10 onto the stack stack.push(20) # Push 20 onto the stack stack.push(30) # Push 30 onto the stack stack.push(40) # Push 40 onto the stack, triggers resizing stack.push(50) # Push 50 onto the resized stack  Page 16 of 34 INPUT-PROCESS-OUTPUT (IPO) Model INPUT PROCESS OUTPUT stack (array), top (integer) ALGORITHM The value popped from the stack or an error if empty 1. If top == -1, then: Print "Stack Underflow" Exit 2. setValue = stack[top] 3. Decrement top by 1 4. Return value Simulations: top = 3  Page 17 of 34 3 == -1? N setValue = D top = 3 -1 = 2 D ====== top = 2 2 == -1? N setValue = C top = 2 -1 = 1 C ========= top = 1 1 == -1? N setValue = B top = 1 -1 = 0 B ============ top = 0 0 == -1? N setValue = A top = 0 -1 = -1 A =========== top = -1 -1 == -1? Y Stack Underflow  Page 18 of 34 Approaches to Handle Empty Stack Before Pop Operation 1.​ Check before POP operation. Best for educational purposes or simple applications where avoiding an error is sufficient. OUTPUT  Page 19 of 34 ================== class StackWithCheck: def __init__(self): self.stack = [] def is_empty(self): return len(self.stack) == 0 def push(self, element): self.stack.append(element) def pop(self): if self.is_empty(): print("Stack is empty! Cannot perform POP operation.") return None print(f"Stack: {self.stack}") return self.stack.pop() # Example usage stack1 = StackWithCheck() # Attempt to pop from an empty stack print(stack1.pop()) # Stack is empty! Cannot perform pop operation. # Push elements onto the stack stack1.push(10) stack1.push(20) # Pop an element and display the stack content before popping print(stack1.pop()) # Stack before popping: [10, 20], returns 20 print(stack1.pop()) # Stack before popping: , returns 10 # Attempt to pop from an empty stack print(stack1.pop()) # Stack is empty! Cannot perform pop operation.  Page 20 of 34 2.​ Raise an Exception: Recommende d for critical systems where unexpected behavior needs explicit handling. OUTPUT ======================== class StackWithException: def __init__(self): self.stack = []  Page 21 of 34 def is_empty(self): return len(self.stack) == 0 def push(self, element): self.stack.append(element) def pop(self): if self.is_empty(): raise IndexError("POP operation failed: Stack is empty!") print(f"Stack: {self.stack}") return self.stack.pop() # Example usage stack2 = StackWithException() # Handling the exception while attempting to pop from an empty stack try: stack2.pop() # Should raise an exception except IndexError as e: print(e) # Push elements onto the stack stack2.push(10) stack2.push(20) # Pop an element and display the stack content before popping try: print(stack2.pop()) # Stack before popping: [10, 20], returns 20 print(stack2.pop()) # Stack before popping: , returns 10 print(stack2.pop()) # Should raise an exception again except IndexError as e: print(e) 3.​ Return a Default Value: Suitable for cases where a default return value is acceptable, like in optional operations.  Page 22 of 34 OUTPUT  Page 23 of 34 ============ class StackWithDefaultValue: def __init__(self): self.stack = [] def is_empty(self): return len(self.stack) == 0 def push(self, element): self.stack.append(element) def pop(self, default=None): if self.is_empty(): print("Stack is empty! Returning default value.") return default print(f"Stack before popping: {self.stack}") return self.stack.pop() # Example usage stack3 = StackWithDefaultValue() # Pop from an empty stack print(stack3.pop()) # Should return None with a message # Push elements onto the stack stack3.push(10) stack3.push(20) # Pop elements and display stack content before popping print(stack3.pop()) # Stack before popping: [10, 20], returns 20 print(stack3.pop()) # Stack before popping: , returns 10 print(stack3.pop()) # Should return None with a message Peek isEmpty isFull Purpose: Look at Purpose: Check if Purpose: Check if the top (stack) or the data structure is the data structure is front (queue) empty. full (used in element without fixed-size removing it. implementations). Python ✔​Not built-in; Not built-in; ✔​Not built-in; ✔​access the Use ✔​must be element len(stack) == 0 or not implemented manually stack. manually if using a fixed-size (stack[-1] or structure. queue).  Page 24 of 34 C++ Use Use Not available in top() (for stack) empty() method STL because or in STL containers. containers like front() (for std::stack are queue). dynamic. JAVA Use Use Not available for peek() (in stack isEmpty() dynamic or method in collections; queue). Stack or implement Queue manually for fixed-size arrays. Note: ​ peek and isEmpty are readily available in C++ STL and Java collections but need to be manually implemented in Python. ​ isFull needs to be implemented manually in all languages if using fixed-size structures. ​ Different languages provide varying levels of abstraction based on their design philosophy. Representation of Stack A stack can be implemented using: 1.​ Array (Fixed size) 2.​ Linked List (Dynamic size) STACK ARRAY-BASED Source: https://afteracademy.com/blog/stack-and-its-basic-operations/  Page 25 of 34 LIST-BASED Source: https://www.geeksforgeeks.org/stack-using-linked-list-in-c/ Why Array and Linked List? 1.​ LIFO Principle: Both implementations adhere to the Last-In-First-Out (LIFO) principle. 2.​ Basic Operations: Both support the same core stack operations: o​ push: Add an element to the top of the stack. o​ pop: Remove the top element from the stack. o​ peek: View the top element of the stack without removing it. o​ isEmpty: Check if the stack is empty. 3.​ Applications: Both implementations can be used interchangeably for applications such as recursion, parsing, or undo functionality. 4.​ A stack may have a limited space depending on the implementation. We must implement check conditions to see if we are not adding or deleting elements more than it can maximum support. 1.​ The UNDERFLOW condition checks if there exists any item before popping from the stack. An empty one cannot be popped further. ​ If (top == -1) { // underflow condition … } 2.​ The OVERFLOW condition checks if the stack is full (or more memory is available) before pushing any element. This prevents any error if more space cannot be allocated for the next item. If (top == sizeOfStack) { // underflow condition … }  Page 26 of 34 FEATURE Array-Based STACK Linked List-Based STACK Uses a contiguous block of Uses a series of nodes connected via Structure memory. pointers. Requires a fixed or dynamically Allocates memory as needed for each Memory Allocation resized block of memory. node. May have a fixed size or require Size Limitation Size is limited only by system memory. resizing when full. Resizing can be costly (copying No resizing needed; nodes are added Resizing elements to a larger array). dynamically. Minimal, but resizing may waste Each node has pointer overhead, memory. increasing memory usage. Space Efficiency Can waste space if allocated size Uses only as much memory as required is larger than needed. by elements. Faster access to elements due to Slower access because nodes are Performance contiguous memory. scattered in memory. Ease of Simple to implement using an Slightly more complex due to node Implementation array or Python list. creation and pointer management. Can occur when the stack size No overflow unless the system runs out Overflow Condition exceeds the array capacity. of memory. When to Use Array vs. Linked List? Use Array-Based Stack When: 1.​ Fixed or Small Size: The maximum size of the stack is known in advance. o​ Example: Keeping track of parentheses balance in a short string. 2.​ Faster Access: Contiguous memory allows quicker element access. 3.​ Minimal Overhead: You want to save memory by avoiding extra pointers. Use Linked List-Based Stack When: 1.​ Dynamic Size: The stack size is unpredictable or can grow/shrink frequently. o​ Example: Evaluating a long mathematical expression with recursion. 2.​ No Wasted Memory: Only the required memory is allocated for the elements. 3.​ Avoid Resizing Costs: Resizing an array can be computationally expensive. Real-World Example of Usage Array-Based Stack Linked List-Based Stack Used in applications like Used in  Page 27 of 34 Browser History: Stores a Undo/Redo Functionality in Text predefined number of recent pages Editors visited. recursive function calls where the Function Call Stacks: The depth of depth is unpredictable the stack is usually fixed and Depth-First Search in Graphs: Graph predefined (e.g., max call stack traversal depth can vary size in programming). significantly depending on the Expression Evaluation (Postfix/Infix graph structure. Conversion) Syntax Parsing in Compilers: Balanced Parentheses/Bracket Parsing complex syntax trees can Matching involve unpredictable depth and String/Word Palindrome Checking dynamic memory allocation. Directory Navigation (Backtracking through File System Paths): File systems may involve unpredictable depths (e.g., deep directory trees); A linked list allows dynamic resizing and efficient memory allocation. Undo Actions in Command-Line Programs: The number of commands to undo is unpredictable. Code Examples Array-B ased Stack (Python Example )  Page 28 of 34 Output:  Page 29 of 34 ================ class ArrayStack: def __init__(self, capacity): # Initialize a stack with a fixed capacity. self.stack = [None] * capacity # Fixed-size array to hold stack elements self.capacity = capacity # Maximum size of the stack self.top = -1 # Tracks the topmost index (-1 means stack is empty) def push(self, item): # Add an item to the top of the stack. if self.top < self.capacity - 1: # Check if there is space in the stack self.top += 1 # Increment the top index self.stack[self.top] = item # Place the new item at the top position print(f"Pushed: {item}") # Display the value being pushed print(f"Stack after push: {self.stack[:self.top + 1]}") # Display stack content after push else: raise OverflowError("Stack is full") # Raise an exception if the stack is full def pop(self): # Remove and return the topmost item from the stack. if self.top >= 0: # Check if the stack is not empty item = self.stack[self.top] # Retrieve the item at the top self.stack[self.top] = None # Clear the value (optional) self.top -= 1 # Decrement the top index print(f"Popped: {item}") # Display the value being popped print(f"Stack after pop: {self.stack[:self.top + 1]}") # Display stack content after pop return item # Return the removed item else: raise IndexError("Stack is empty") # Raise an exception if the stack is empty def peek(self): # Return the topmost item without removing it. if self.top >= 0: # Check if the stack is not empty return self.stack[self.top] # Return the item at the top else: raise IndexError("Stack is empty") # Raise an exception if the stack is empty  Page 30 of 34 def is_empty(self): # Check if the stack is empty. return self.top == -1 # Return True if top is -1, indicating no items # Example usage stack = ArrayStack(5) # Create a stack with a capacity of 5 stack.push(10) # Push 10 onto the stack stack.push(20) # Push 20 onto the stack print(f"Peek: {stack.peek()}") # Output the topmost item without removing it (Output: 20) stack.pop() # Remove the topmost item (20 is removed) stack.push(30) # Push 30 onto the stack Linked List-Bas ed Stack (Python Example ) Page 31 of 34  Page 32 of 34 Output: ============== class Node: # Node class to represent each element in the stack def __init__(self, value): self.value = value # Value of the node self.next = None # Pointer to the next node in the stack class LinkedListStack: # Linked list-based stack implementation def __init__(self): self.top = None # Points to the top node of the stack def push(self, item): # Push an item onto the stack new_node = Node(item) # Create a new node with the given value new_node.next = self.top # Link the new node to the current top self.top = new_node # Update the top to the new node print(f"Pushed: {item}") # Display the value being pushed print("Stack after push:", self._get_stack_content()) # Display the stack content  Page 33 of 34 def pop(self): # Pop the top item from the stack if not self.is_empty(): # Check if the stack is not empty item = self.top.value # Retrieve the value of the top node self.top = self.top.next # Update the top to the next node print(f"Popped: {item}") # Display the value being popped print("Stack after pop:", self._get_stack_content()) # Display the stack content return item # Return the removed item else: raise IndexError("Stack is empty") # Raise an exception if the stack is empty def peek(self): # Peek at the top item without removing it if not self.is_empty(): # Check if the stack is not empty return self.top.value # Return the value of the top node else: raise IndexError("Stack is empty") # Raise an exception if the stack is empty def is_empty(self): # Check if the stack is empty return self.top is None # Return True if the stack has no elements def _get_stack_content(self): # Helper method to get the stack content as a list for display content = [] current = self.top # Start from the top of the stack while current: # Traverse the stack until the end content.append(current.value) # Add each node's value to the list current = current.next # Move to the next node return content # Return the list of stack content # Example usage stack = LinkedListStack() # Create a new stack stack.push(10) # Push 10 onto the stack stack.push(20) # Push 20 onto the stack print(f"Peek: {stack.peek()}") # Output the topmost item without removing it (Output: 20) stack.pop() # Remove the topmost item (20 is removed) stack.push(30) # Push 30 onto the stack Note: To differentiate between a simple array and a stack implemented using an array, you can look at the structure and operations supported by the data structure. ✔​ If the code includes methods like push, pop, peek, and is_empty; and ✔​ only allows operations at one end of the structure (usually the top) then it is likely implementing a stack using an array. A simple array, on the other hand, does not have such restricted operations and allows direct access to any index.  Page 34 of 34 Key Difference from Simple Array: ​ A simple array allows random access to any element at any index, while a stack implemented with an array restricts operations to one end (the top), following LIFO behavior. ​ In a simple array, there is no concept of "top," and you can directly manipulate any index (e.g., arr, arr, etc.). In contrast, a stack uses the top pointer/index to track where the next operation (push or pop) will occur.