Introduction to Implementing Data Structures with Classes

In previous chapters, we explored the basics of Object-Oriented Programming (OOP)—how to create classes, instantiate objects, and use encapsulation. Now, we are going to see where OOP truly shines: implementing data structures.

Instead of just having a messy "naked" list of data, we can wrap that data inside a class. This allows us to control exactly how data is added or removed, ensuring the "rules" of the data structure (like Last-In-First-Out for stacks) are always followed. Don't worry if this seems like a jump in difficulty; we will take it step-by-step, using Nodes and Pointers to build our structures.

1. The "Node" Concept: The Building Block

For many dynamic data structures like Linked Lists and Trees, we need a helper class called a Node. Think of a Node as a "cargo container" that holds two things: the actual data and a reference (pointer) to where the next container is located.

A typical Node class looks like this:

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None # This is our pointer

By linking these Node objects together, we can create complex structures without needing the data to be stored in adjacent memory locations!

2. Implementing Stacks with Classes

A Stack follows the LIFO (Last-In-First-Out) principle. Think of a stack of cafeteria trays; the last one you put on top is the first one someone picks up.

Key Attributes and Methods

  • top: An integer pointer or index tracking the uppermost element.
  • push(item): Adds an item to the top.
  • pop(): Removes and returns the top item.

When implementing a Stack using a Python list inside a class, we use encapsulation to hide the list. The user doesn't need to know how the list works; they just call .push() or .pop(). This is implementation independence.

Quick Tip: Always check if the stack is empty before popping, or you might run into a "Stack Underflow" error!

3. Implementing Queues: Linear and Circular

A Queue follows FIFO (First-In-First-Out). It’s like a line for bubble tea—the first person in line is the first one served.

Linear Queues vs. Circular Queues

In a Linear Queue, as we add and remove items, our front and rear pointers keep moving forward. Eventually, we reach the end of the list and can't add more items, even if there is empty space at the front! This is inefficient.

A Circular Queue solves this by "wrapping around." When the rear pointer reaches the end of the list, it jumps back to index \( 0 \), provided that space is empty.

The Circular Math: We use the modulo operator \( \% \) to calculate the next position:
\( \text{new\_position} = (\text{current\_position} + 1) \% \text{max\_size} \)

4. Implementing Linked Lists

A Linear Linked List is a series of Node objects. Unlike a standard list, it doesn't have fixed indexes. We only know where the Head (the first node) is. To find the 5th item, we have to start at the Head and follow the pointers four times.

Common Operations:

  • Search: Start at head. Use a while loop to move to the next node until the data matches or you hit None. Time complexity: \( O(n) \).
  • Insertion: Create a new Node. Update its next pointer to point to the current node at that position, and update the previous node's pointer to point to the new Node.
  • Deletion: Find the node before the one you want to delete. Change its next pointer to "skip over" the deleted node and point to the one after it.

Common Mistake: Forgetting to handle the "Empty List" case. If the head is None, your code might crash if you try to access head.data!

5. Implementing Binary Trees

A Binary Tree is a structure where each Node has at most two children: left and right. A Binary Search Tree (BST) adds a rule: for every node, smaller values go to the left and larger values go to the right.

The Tree Node Class

class TreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

Traversals (Walking through the Tree)

We use Recursion to visit every node in a tree. There are three main "Depth-First" orders:

  1. Pre-order: Root \( \rightarrow \) Left \( \rightarrow \) Right. (Useful for copying a tree).
  2. In-order: Left \( \rightarrow \) Root \( \rightarrow \) Right. (Key Fact: In a BST, this gives you the data in sorted order!)
  3. Post-order: Left \( \rightarrow \) Right \( \rightarrow \) Root. (Useful for deleting a tree).

Note: For the H2 syllabus, you need to know how to search and insert into a BST, but you are not required to implement the deletion of nodes from a BST.

6. Summary Table: Efficiency and OOP Role

Data Structure Main OOP Benefit Search Efficiency (BST/Sorted)
Stack / Queue Encapsulation prevents illegal access to middle elements. \( O(n) \)
Linked List Dynamic memory allocation using Node objects. \( O(n) \)
Binary Search Tree Recursive methods naturally fit the hierarchical structure. \( O(\log n) \) average case

Quick Review Box

  • Classes act as the "Manager" of the data structure.
  • Encapsulation keeps the internal pointers (like head or top) safe from external interference.
  • Nodes allow us to build structures that grow and shrink easily.
  • Use In-order traversal if you want to print a Binary Search Tree's contents in ascending order.

Did you know? Even though Python's built-in list is very powerful, learning to build these structures with classes is vital for understanding how memory works and is a favorite topic in technical interviews!