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 manipulate linked lists.
• Explain binary trees and their traversal methods.
• Use different file formats and access methods.
• Compare sequential vs. random file access.
• Implement error handling for file operations.

Lesson summary

This week, we delve deeper into advanced solution development by focusing on complex data structures and file handling. In previous weeks, you've likely worked with arrays and basic file operations. Now, we'll explore more sophisticated data structures like linked lists and binary trees, and learn how to efficiently store and retrieve data using different file formats and access methods. This is crucial for developing real-world applications that can manage large amounts of information, something increasingly important in our data-driven world.

Lesson notes

2.1 Linked Lists: A linked list is a dynamic data structure where elements (nodes) are linked together using pointers. Unlike arrays, linked lists do not have a fixed size, and memory allocation is done dynamically. Each node in a linked list contains data and a pointer (or link) to the next node in the sequence. The last node's pointer typically points to `NULL` or `None`, indicating the end of the list.

Types of Linked Lists: Singly Linked List: Each node points to the next node.

Doubly Linked List: Each node points to both the next and the previous node.

Circular Linked List: The last node points back to the first node.

Operations on Linked Lists: Insertion: Adding a new node to the list (at the beginning, end, or in the middle).

Deletion: Removing a node from the list.

Traversal: Visiting each node in the list, typically to display or process the data.

Searching: Finding a specific node based on its data.

Example (Python): ```python class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node def print_list(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") Example Usage my_list = LinkedList() my_list.append(10) my_list.append(20) my_list.append(30) my_list.print_list() # Output: 10 -> 20 -> 30 -> None ``` Why Linked Lists are Important: Linked lists are useful when the size of the data is not known beforehand, and insertions/deletions are frequent. Think about managing a queue of customers at a Telkom store. New customers arrive (insertion), and customers are served (deletion). 2.2 Binary Trees: A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. The topmost node is called the root.

Types of Binary Trees: Binary Search Tree (BST): A binary tree where the value of each node is greater than all values in its left subtree and less than all values in its right subtree.

Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.

Full Binary Tree: Every node has either 0 or 2 children.

Perfect Binary Tree: All internal nodes have two children, and all leaves are at the same level.

Tree Traversal: In-order: Visit the left subtree, then the root, then the right subtree. (Left -> Root -> Right)

Pre-order: Visit the root, then the left subtree, then the right subtree. (Root -> Left -> Right)

Post-order: Visit the left subtree, then the right subtree, then the root. (Left -> Right -> Root)

Example (Conceptual): Imagine a family tree. The root is the oldest ancestor. The left and right children represent their descendants. In-order traversal might represent the birth order of the family members (simplified). 2.3 File Handling: File handling involves reading from and writing data to files. It's essential for persistent storage of information.

File Formats: Text Files (.txt): Store data as plain text characters, easily readable by humans. Binary Files (.bin, .dat, .jpg): Store data in a binary format, optimized for computers. They are not directly readable by humans.

File Access Methods: Sequential Access: Data is read or written in a sequential order, from the beginning of the file to the end. Suitable for processing logs or reports.

Random Access (Direct Access): Data can be accessed directly at any location in the file using a file pointer or offset. Suitable for database systems where specific records need to be retrieved quickly.