Lesson Notes By Weeks and Term v5 - Grade 12

Lesson Video

This page supports the lesson note with a companion video and a short classroom-ready summary.

For class groups and homework, share this lesson page so learners also get the summary, objectives, and full lesson context.

Performance objectives

• Implement and use Linked Lists.
• Differentiate and implement Stacks and Queues.
• Understand and traverse Binary Trees.
• Read from and write to binary files.
• Compare the efficiency of different data structures.

Lesson summary

This week, we delve into advanced solution development, focusing specifically on complex data structures and file manipulation. Building on previous knowledge of arrays, records, and basic file operations, we will explore linked lists, stacks, queues, and binary trees. Understanding these data structures is crucial for efficiently storing, organizing, and retrieving data, which is fundamental to developing robust and scalable software solutions.

Furthermore, we will explore techniques for managing and processing data within files, including binary files, which are prevalent in various applications ranging from storing census data to managing financial transactions.

Lesson notes

2.1 Linked Lists A linked list is a linear data structure in which elements are not stored in contiguous memory locations. Each element (node) contains data and a pointer (reference) to the next node in the sequence.

Singly Linked List: Each node contains data and a pointer to the next node. The last node's pointer is typically `NULL` or `None`.

Doubly Linked List: Each node contains data, a pointer to the next node, and a pointer to the previous node. This allows for traversal in both directions.

Advantages of Linked Lists: Dynamic size: Linked lists can grow or shrink as needed, unlike arrays which have a fixed size.

Efficient insertion/deletion: Inserting or deleting elements in the middle of a linked list is faster than in an array, as it doesn't require shifting elements.

Disadvantages of Linked Lists: Requires more memory: Each node requires extra memory for the pointer(s).

Random access is not efficient: To access an element in the middle of a linked list, you need to traverse from the beginning.

Example (Python): Singly Linked List ```python class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insert_at_beginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def print_list(self): temp = self.head while (temp): print(temp.data, end=" ") temp = temp.next print() Example Usage linked_list = LinkedList() linked_list.insert_at_beginning(3) linked_list.insert_at_beginning(7) linked_list.insert_at_beginning(1) linked_list.print_list() # Output: 1 7 3 ``` 2.2 Stacks and Queues Stack: A LIFO (Last-In, First-Out) data structure. Think of a stack of plates; the last plate placed on top is the first one you remove.

Operations: `push` (add to the top), `pop` (remove from the top), `peek` (view the top element).

Queue: A FIFO (First-In, First-Out) data structure. Think of a queue at a bank; the first person in line is the first to be served.

Operations: `enqueue` (add to the rear), `dequeue` (remove from the front), `peek` (view the front element).

Example (Python): Stack using a List ```python class Stack: def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() else: return None # Or raise an exception def peek(self): if not self.is_empty(): return self.items[-1] else: return None Example Usage s = Stack() s.push(10) s.push(20) s.push(30) print(s.pop()) # Output: 30 print(s.peek()) # Output: 20 ``` Example (Python): Queue using a List ```python class Queue: def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def enqueue(self, item): self.items.insert(0, item) # Insert at the beginning for FIFO def dequeue(self): if not self.is_empty(): return self.items.pop() else: return None # Or raise an exception def peek(self): if not self.is_empty(): return self.items[-1] #The last item is the one that's been there the longest else: return None Example Usage q = Queue() q.enqueue(10) q.enqueue(20) q.enqueue(30) print(q.dequeue()) # Output: 10 print(q.peek()) # Output: 20 ``` 2.3 Binary Trees A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.

Root: The topmost node in the tree.

Leaf: A node with no children.

Internal Node: A node with at least one child.

Tree Traversal: Visiting all nodes in a tree in a specific order.

Common traversal methods: In-order: Left subtree -> Root -> Right subtree Pre-order: Root -> Left subtree -> Right subtree Post-order: Left subtree -> Right subtree -> Root Example (Python): Binary Tree Traversal ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.data, end=" ") inorder_traversal(root.right) def preorder_traversal(root): if root: print(root.data, end=" ") preorder_traversal(root.left) preorder_traversal(root.right) def postorder_traversal(root): if root: postorder_traversal(root.left) postorder_traversal(root.right) print(root.data, end=" ") Example Usage root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal:") inorder_traversal(root) # Output: 4 2 5 1 3 print("\nPreorder traversal:") preorder_traversal(root) # Output: 1 2 4 5 3 print("\nPostorder traversal:") postorder_traversal(root) # Output: 4 5 2 3 1 ``` 2.4 Binary Files Binary files store data in the same format as it is stored in memory, unlike text files, which store data as characters. Binary files are more efficient for storing large amounts of numerical data or complex objects.

Advantages of Binary Files: Efficiency: Data is stored in a compact format, saving space.

Speed: Reading and writing binary data is faster than converting to/from text.