4. Data Structures
4.1 Types of Collections
- Linear (e.g., arrays, stacks, queues)
- Hierarchical (e.g., trees)
- Graph (e.g., maps, networks)
4.2 Arrays vs Linked Structures
- Arrays: static size, fast random access
- Linked Lists: dynamic size, easier insertion/deletion
4.3 Linked Lists
class Node:
def __init__(self, data, next=None):self.data = data
self.next = next
- Traverse with loop: while probe is not None: probe = probe.next
4.4 Stacks (LIFO)
- Operations:
push,pop,peek, isEmpty - Used for: recursion, parentheses matching, expression evaluation
- Implementations: List, Array, Linked List
4.5 Queues (FIFO)
- Operations:
enqueue,dequeue,peek, isEmpty - Applications: CPU scheduling, printer jobs
- Implementations: Array (circular), Linked List
4.6 Binary Trees
- Each node has: left, right child
- Binary Search Tree (BST): Left < Root < Right
Traversals:
- In-order: left, root, right (sorted)
- Pre-order: root, left, right
- Post-order: left, right, root
Example:
class TreeNode:
def __init__(self, data):self.data = data
self.left = None
self.right = None
This concludes the structured notes from topics 5 to 8. Let me know if you’d like a condensed revision version, key diagrams, or concept maps based on this content.
H2 Computing Notes: Comprehensive Beginner-Friendly Summary