Common Data Structures

Introduction

Understanding data structures is crucial for writing efficient code. In this lesson, we'll implement common data structures in Python: stacks, queues, linked lists, and binary trees.

Stacks and queues

# Stack (LIFO) - use a list
stack = []
stack.append(1)   # push
stack.append(2)
stack.pop()        # 2 (pop)

# Queue (FIFO) - use deque for O(1) operations
from collections import deque
queue = deque()
queue.append(1)     # enqueue
queue.append(2)
queue.popleft()     # 1 (dequeue)

Linked list

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 not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        return " -> ".join(elements)

Assignment