Python Data Structures and Algorithms: Complete Guide

Compare Python arrays with lists, import the array module, and create a homogenous numeric array. Access items by index, check length, and review item size.

Explore popular sort algorithms for arrays, including bubble sort, merge sort, quick sort, counting sort, and insertion sort, while evaluating in-place and stable versus unstable sorts for memory-constrained applications.

Explore bubble sort theory with an in-place, partitioned array example, swapping adjacent elements to sort in ascending order, and understand its quadratic O(n^2) time and recognize its teaching use.

Write and organize unit tests for bubble sort using unittest and pytest, naming tests like test_bubble_sort, and running them from the command line with verbose output.

Bubble sort optimization stops early when no swaps occur, using a swapped flag, while unit tests confirm correctness and note best-case O(n) and worst-case O(n to the power of 2).

Identify the largest element in the unsorted partition and swap it into its correct position, growing the sorted portion from right to left; in-place, O(n^2) and unstable for duplicates.

Implement selection sort in Python by sorting any mutable sequence with selection_sort, identify the largest in the unsorted partition, and swap it into place, achieving O(n^2) time.

Learn how merge sort uses divide and conquer, splitting the array in place into left and right subarrays and merging them with temporary arrays via recursion to produce sorted result.

Implement merge sort in Python using recursion, with a separate merge function to merge sorted partitions and handle start, mid, and end indices.

Implement quick sort in Python with quick_sort calling _quick_sort, use end indices, and perform partitioning with a pivot and i and j to recursively sort left and right subarrays.

Develop and test quick sort routines by running unit tests, diagnose recursion errors from poor pivot choices, and improve robustness by switching to the middle element as pivot.

Learn counting sort with minimum and maximum values and test scripts. Use unittest and assertRaises to enforce ValueError for floats or strings, and demonstrate stable counting sort with empty data.

Explain how to implement a stable counting sort with a temporary array and prefix-sum counts, noting it cannot be in-place, and its role in radix sort.

Modify radix sort to handle negative values by performing a final sign-based sort, introducing a get_sign function and passing a key function to radix_counting_sort.

Adapt a Python merge sort to descending order by renaming the function to merge_sort_descending and updating the merge step to use greater-than-or-equal comparisons, preserving stability and testing results.

Convert the insertion sort to a recursive version and test it with test_insertion_sort. The challenge reinforces recursion concepts and warns of RecursionError on large inputs, advising downsizing to 900 elements.

Explore converting insertion sort from an iterative to a recursive approach, using a recursive function with num_items, base case, and diagnostic prints; learn testing considerations and Python stack limits.

Enhance a stable counting sort by incorporating a minimum value parameter, rebasing indices, and resizing the counting array, achieving memory efficiency in Python.

Explore singly linked lists: nodes with next pointers, a head reference, and dynamic insertion and deletion at the front in constant time, unlike arrays.

Explore duck typing and dynamic typing that let objects share interfaces. See how abstract base classes and protocols formalize interfaces as contracts with structural typing.

Explore implementing a vehicle interface via an abstract base class, defining abstract methods like start, go, steer, and stop, and compare with a protocol in Python.

Show how ABCs increase coupling and how protocols reduce it by creating a geared interface with change_gear, and by composing Drivable and Geared interfaces for a manual car.

Explore implementing a doubly linked list with a DoubleLinkNode, adding head and tail pointers, and enabling forward and backward traversal through next and previous links.

Rename the delete function to pop and adapt it for a doubly linked list, updating head, tail, and previous links, raising IndexError on empty lists.

Implement a complete mutable sequence pop for a linked list by adding an index parameter with default -1, updating the docstring, and handling head, tail, and empty-list cases with tests.

Learn to pop from a specific index in a doubly linked list by locating the node, updating adjacent links, handling head and tail, and recognizing middle removals require traversal.

Override the add method in a subclass of the double linked list to maintain a sorted list by inserting new items into their correct position, keyed by the Employee id.

Explore the __getattribute__ magic method and how it intercepts attribute access, enabling blocking with NotImplementedError for operations like append, plus safe delegation to the superclass.

Learn how __getattribute__ and __getattr__ differ in Python and how dot notation compares to index lookup on dictionaries. Explore implementing __getattr__ to support case-insensitive keys.

Implement the reverse method to mutate lists in place. Swap pointers in a doubly linked list and track the previous node in a singly linked list to reverse order.

Traverse a doubly linked list from the head and tail to implement count and __contains__ efficiently. Then add an index method and run tests in main_double.py to verify behavior.

Implement __eq__ to compare DoublyLinkedList contents, support comparison with built-in lists, and use zip and all for efficient content-based equality checks.

Explore how slice assignment works in Python, including when the assigned iterable differs in size, with step considerations, and how to implement updates using a doubly linked list.

Explore operator overloading in Python with special methods like __eq__ and __mul__, illustrating how lists and strings behave, the role of __rmul__, and non-commutative vs commutative operations.

Learn how __imul__ and __iadd__ enable in-place mutation and how augmented assignment may fall back to __mul__ or __add__, with size tracking and NotImplemented checks.

Explore how augmented assignment mutates a list inside an immutable tuple and then assigns back. Also fixes a DoublyLinkedList bug when extended by itself and adds unit tests.

Adapt CPython's unit tests for a DoublyLinkedList: switch the test type, import the class, and run verbose unittest across Python 3.9–3.12. Verify list integrity and pickling behavior across versions.

Discover stacks as a last in, first out data structure with push, pop, and peek. See how top-item access powers the call stack and recursion.

Explore how a Python list serves as the stack backing store, implementing push, peek, and pop with safety checks, dynamic resizing, and unit tests.

Discover how the stack and heap memory govern Python objects, reference counts, allocation, and garbage collection, and how local variables boost access speed.

Demonstrate implementing a stack with an array backing that uses indirection to store object addresses in a heap dictionary. Explain how CPython uses IDs as memory addresses to retrieve objects.

Understand how circular queues reuse free space in a backing array by wrapping the back pointer, tracking front and back, computing size, and avoiding unnecessary resizing.

Build a generic circular queue in Python using a list backing store with front and back pointers, doubling the array as needed, and exposing add, remove, peek, and __repr__.

Explore Python's standard library queue module with four classes for different use cases. Learn about blocking, timeouts, join and task_done, and inter-thread communication in Queue, SimpleQueue, LifoQueue, and PriorityQueue.

Discover how hash tables store key/value pairs for fast retrieval. Learn about hashing, hash functions, collisions, load factor, and how python dicts illustrate these concepts.

Build a simple Python hash table using a list as backing storage, with generics for keys and values, a hash function, and a Collision exception; implement put, get, and values.

Tests a simple hash table by adding employees and validating length, collision behavior, and value retrieval, while highlighting unhandled collisions and future collision resolution.

Learn to implement linear probing in a hash table to resolve collisions, replacing direct value storage with TableEntry objects, adding get, put, keys, and dict-like repr.

Learn how a probing hash table handles hash collisions, tests replacement on key conflicts, and observes table state and exceptions like table full through focused unit tests and debugging.

Implement bucket sort in Python using a generic bucket_sort and a simple_hash to place values into buckets, then scatter, sort buckets, and gather results back into the list.

Examine binary trees and binary search trees, with left and right children, complete and full trees, and how insertion order affects shape, enabling log n search, insert, and delete.

Explore iterative insertion and in-order traversal of a binary search tree by implementing methods in the BinaryTree class, using a stack for traversal, and weighing speed against memory.

Demonstrate how recursive_delete removes a node in a binary search tree by traversing from the root to the target, replacing with the right subtree's minimum, and updating links.

Explore red-black trees, self-balancing binary search trees that use rotations and recoloring to stay balanced. See how they relate to 2-3 and 2-3-4 trees and B-trees.