Python Data Structures and Algorithms: Complete Guide

Examine the array class in the Python standard library, understand how arrays are stored in memory and their random access advantages, and introduce Big O notation to measure performance.

Compare algorithm performance using big-O notation across worst-case scenarios. Analyze time complexity, input size, and growth patterns like O(1), O(N), and O(N^2) to gauge hardware-independent efficiency.

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 the big-O values for array operations, showing constant time retrieval with an index (O(1)) and linear search (O(n)) when the index is unknown.

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.

Implement a bubble sort in Python that sorts mutable sequences in place using tuple unpacking to swap elements. Explore the two-loop structure and a quadratic time complexity.

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.

Explore a more comprehensive test suite for a bubble sort function, running 18 tests with verbose output to verify correctness, edge cases, and test driven development concepts.

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).

Understand stable sorts preserve duplicates' relative order, as bubble sort does with strict comparisons, while equals can flip order, making an unstable sort.

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.

Copy the bubble sort tests and adapt them for selection sort, then run the tests to confirm they pass, validating unit testing for reliable, reusable sort functions.

Insert each unsorted element into the correct position to grow the sorted partition from left to right. Perform in-place shifting; insertion sort is quadratic and stable.

Explore the Python implementation of insertion sort that sorts a mutable sequence by shifting elements and inserting each new element into its correct position within the sorted partition.

Adapt insertion sort tests by reusing test_bubble_sort.py, edit the test_insertion_sort file name and class, then run python -m unittest to confirm tests pass.

Shell sort improves insertion sort by using a decreasing gap interval to reduce shifting. Explore gap sequences, such as Knuth's, and understand its in-place, unstable nature and variable time complexity.

Implement shell sort in Python for mutable sequences, using a gap sequence (half length or Knuth) and an insertion-sort style inner loop. Include diagnostic prints and unit tests.

Explore recursion through factorial, learning how a function calls itself with base cases and the call stack. Compare iterative and recursive implementations in Python.

Explore how recursion works through the factorial function, tracing calls, the call stack, and the base case, while comparing recursion to iteration and noting stack overflow risks.

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.

Explore the merging phase of merge sort in Python data structures and algorithms, detailing bottom-up merging of one element arrays, temporary storage, and stable, divide-and-conquer behavior.

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

Finish the merge function with optimizations: if left is smaller than right, skip merging; otherwise merge with two pointers and a temp array, handling remaining left elements and preserving stability.

Master the pythonic merge step using slices to combine left and right arrays, manage a temporary array, and complete merge sort with a robust loop-based copy.

Explore a diagnostic merge sort that uses the Python logging module to trace recursion with indented logs, showing left and right subarrays and the merge step.

Explore quick sort, an in-place, divide-and-conquer algorithm that partitions around a pivot into left and right sub-arrays that aren't necessarily sorted, and is not stable, with O(n log n) time.

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, a non-comparative algorithm that sorts non-negative discrete values by counting occurrences within a range. It uses two phases: counting and writing back, with in-place or stable variants.

Implement counting sort in Python by passing min and max values, mutating the data in place, using a counting array to tally values, including negatives, for small value ranges.

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.

Implement a stable counting sort for employee records by ID using a key function and a max value, organized with a main function.

Explore stable counting sort: update data with slice assignment, maintain stability by reverse iteration, and use optional key functions for mutable sequences.

Explore the Radix Sort theory, sorting numbers and strings by fixed radix and width, with stable passes from least to most significant using counting sort.

We implement radix sort in Python, use a stable counting sort on each digit with a nested get_digit function, and analyze digit extraction and time and space complexity.

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.

Discover how to sort in Python using the built-in sorted and list.sort, with key, reverse, and attrgetter or itemgetter for complex objects, dictionaries, and locale-aware sorting.

Tackle the sort algorithms challenge by modifying the merge sort to sort integers in descending order, using the provided starting code and test scripts from the resources.

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.

Adapt the radix sort to sort lowercase ascii strings by mapping 97–122 to 0–25, then extend to all 128 ascii codes, using the negative-numbers radix as a base.

Sort strings with radix sort, including a get_char_value using ord to map characters to ASCII codes, handle varying string lengths, and align with 128-radix tests.

This lecture explains implementing a stable counting sort by sizing the counting array to max minus min and passing both min and max to counting_sort_stable, creating a zero-based range.

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

Explore python lists beyond arrays, including linked and doubly linked lists, and study abstract data types, abstract base classes, and protocols. Learn how lists act as sequences with dunder methods.

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

Implement a singly linked list with ListNode and LinkedList, storing Employee objects, supporting head insertion, head removal, traversal, and constant-time size tracking.

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.

Using the Protocol class, implement a Drivable interface to enable a structural type check with a type checker, reduce coupling, and keep runtime behavior unchanged.

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.

Learn to implement a LinkedList as a Python sequence by adding __len__ and __getitem__, then optimize iteration with __iter__ and discuss indexing, slicing, and negative indices.

Explore doubly linked lists, their head and tail pointers, and two-direction traversal. Learn constant-time insertions and deletions at ends, plus linear-time operations in the middle.

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.

Implement __reversed__ as a generator starting at the tail and yielding reverse order. The built-in reversed uses __reversed__ when available; doubly linked lists enable efficient reverse traversal and end appends.

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.

Implement an append method to add values at the end of a list, updating head, tail, and previous_node and next_node pointers, including empty-list handling, with size increment and O(1) performance.

Insert a node in the middle of a doubly linked list in Python, handling negative indices and head or tail cases, updating next and previous pointers while keeping size accurate.

Optimize the getitem by index method on a doubly linked list by traversing from head or tail, visiting at most half the nodes, maintaining O(n) time.

Implement the index method in the LinkedList class, considering Python 3.5 signature changes for start and stop, and raise ValueError if not found.

Implement and test a linked list index method, handling negative indices and edge cases, using ListNode and LinkedList concepts, and validating results with start, stop, and exception handling.

Enhance the singly linked list by adding a tail pointer to enable efficient end insertion, and update add and delete to support empty and single-node cases before implementing append.

Explore how adding a tail pointer to a singly linked list enables O(1) end operations, with updated add and delete methods and an efficient append, verified by assertions.

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.

Subclass the doubly linked list to create a sorted linked list and implement the add method with a docstring and diagnostic prints, overriding append and insert to raise NotImplementedError.

Explore how Python implements list data structures, from doubly linked list operations to dynamic resizing, memory overhead of pointers, and how abstract base classes and protocols shape interfaces.

Explore Python's magic methods and how they power iteration, containment, and augmented assignments, by implementing __getitem__, __iter__, and mutable sequence interfaces in practical examples.

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.

Create a case-insensitive dictionary in Python by subclassing dict and overriding __setitem__ and __getitem__ for string keys. Implement __getattribute__ with super to avoid recursion, enabling index and dot access.

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.

Learn how to implement a resizable array in Python using a backing array, with __setitem__, __getitem__, and append. It shows a 1.25x resize strategy.

Discover how to initialize and extend a doubly linked list by implementing the MutableSequence interface, using an iterable in __init__, and testing clear and reverse operations.

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.

Explore removing a value and counting occurrences in a doubly linked list using head and tail pointers, with ValueError handling and simplified display for testing.

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.

Implement __setitem__ in the doubly linked list using index notation to assign values, discuss index access costs (O(n)) versus built-in lists, and outline slicing and unit tests.

Explore how Python's slice objects power __getitem__ and __setitem__ with start, stop, and step, use indices to adapt to sequence length, and calculate slice length for safe assignments.

Master slicing in a Python doubly linked list by enhancing __getitem__ with slice_attributes and index handling for start, stop, and step, and validating behavior with deleteme.py.

Learn to delete a slice using the __delitem__ method, handling index and slice inputs, stop pointer adjustments, and efficient traversal in a doubly linked list.

Finish the __delitem__ implementation by completing _del_slice, handling head and tail, and refactoring with _delete_node for step 1 and stepped deletions. Validate with del_test tests and edge cases.

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.

Implement slice assignment in the __setitem__ method for a doubly linked list. Handle slice steps, empty values, and iterable size checks to maintain correct list structure and prevent errors.

Finish implementing the replace slice method to support slice assignments in a doubly linked list, covering head, tail, and middle insertions with start, stop, and replacement values.

Investigate a strange edge case in a doubly linked list when slicing with start after stop and step one, causing an infinite loop; fix by setting stop equal to start.

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.

Discover how reflected operands let Python call the right-hand __rmul__ when the left-hand __mul__ returns NotImplemented, enabling correct operation.

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 the stack data type, its last in, first out behavior, and the push, pop, and peek operations, with top as the element, backed by a linked list or array.

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

Implement a stack backed by a linked list using a Node class with slots to save memory, and compare dynamic attributes and dict storage while adapting push, pop, and top.

Learn to implement a stack with a linked list, using a top pointer and size for push, pop, peek, and is_empty checks.

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.

Explore queues and deques as abstract data types and understand fifo behavior. Implement a singly linked list queue with front and back pointers, supporting enqueue, dequeue, peek, and __len__.

Implement a first‑in, first‑out queue backed by a singly linked list in Python, with a Node class, front and back pointers, size, and methods for add, remove, peek, and representation.

Explore self type annotation in Python to annotate links between nodes in a doubly linked list, compare Self with traditional Node annotations, and learn when to use typing-extensions.

Develop an array-backed queue in Python using front and back indices. Grow the backing list by doubling when full and reset when empty to reuse storage for improved performance.

Explore generics in Python by using TypeVar and generic containers like lists and queues, enabling type checkers to warn about mismatched object types.

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 testing a circular queue in python by creating a cq_test.py, adding and removing elements, observing wrap-around behavior, and resizing the backing store while using the walrus operator for numbering.

Explore deques as double-ended queues with append and pop on both ends, enabling fifo and lifo use, backed by a choice of array, circular array, or doubly linked list implementations.

Develop a deque backed by a Python list with front and back pointers, resize logic, and standard library aliases, demonstrated through unit-tested append and pop operations.

Explore a deque backed by a circular array, using front and back pointers and modulo wraparound, with size tracking, and core operations like append, pop, and clear.

Explore a deque implemented with a doubly linked list, enabling inserts and removals at both ends, with size tracking and methods like __getitem__, __iter__, __eq__, and __repr__.

Run unit tests on three deque implementations and the standard library, verify basic operations and equality handling through practical test patterns that avoid recursion errors.

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.

Explore how queues enable thread communication in a real-world Python Tkinter app, showing how worker threads pass results to the main thread using a queue rather than shared globals.

Explore the gui widgets used in a demo Python program, focusing on queues, tkinter event handling, and threading. Visualize queue operations with a Scrollbox, QueueFrame, and processor widgets.

Explore the four queues in the Python standard library—Queue, SimpleQueue, PriorityQueue, and multiprocessing.Queue—their concurrency models, thread and process safety, and how to adapt custom queues for compatibility.

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.

Discover how Python uses hashable objects and hash functions to index dictionaries, manage collisions with buckets, and understand hash values, hashes, and digests.

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.

Explore how open addressing resolves hash collisions using linear probing, storing keys with values, and considering load factor and cache effects to keep lookups fast.

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.

Learn how to delete items in a hash table with linear probing by marking entries as deleted to preserve probe sequences, and compare re-hashing for memory reclamation.

Learn how to implement deletion in a linear probing hash table by marking entries with an active flag instead of None, enabling safe reuse and correct lookups.

Test the hash table pop method by running hash_table_pop_tests.py, verify removing existing keys, handling hash collisions with inactive entries, default values, and no size change when popping absent keys.

Learn how the Python weakref module enables weak references to hash table values, allowing garbage collection to reclaim memory when objects go out of scope.

Explore how weak references and their callbacks automate hash table maintenance, deactivating entries and decrementing size when values are garbage collected.

Explain how to resolve hash collisions by chaining with a linked list at each hash table array position, avoiding probing and keeping chains small in practice.

Explore Python's built-in hash function and why immutable tuples are hashable, with strings' randomized hashes and dict mappings.

Explore Python mappings in the standard library, including ChainMap, Counter, OrderedDict, defaultdict, and UserDict, and see how they relate to hash tables, insertion order, and namespaces.

Bucket sort uses hashing to scatter values into buckets, sorts each bucket, then gathers them back, requiring extra memory and relying on the stability and method of sorting within buckets.

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.

Sorts a linked list using insertion sort by moving through an unsorted partition and inserting each element at proper position with node pointers, with optional key function support and tests.

Learn how bucket sort uses state FIPS codes as hashes to group addresses and sort by zip and zip plus 4, using an address data class.

Explore how hashing extends beyond data structures to security with hashlib, using sha3-256 to generate and compare hex digests for file integrity.

This lecture introduces search algorithms for arrays, covering linear search, binary search, and hashing, explains time complexities like O(n) and O(log n), and notes memory locality benefits of Fibonacci search.

Implement linear search in Python with forward, bidirectional, and index-based methods, timed via timeit. Note how built-in index often dominates, while not-found cases raise ValueError across Python versions.

Master the binary search algorithm, a fast O(log n) method for sorted data, and learn to apply it to arrays with iterative and recursive implementations.

Implement an iterative binary search in Python, exploring start, end, and mid indexes, testing values, handling not-found cases, and comparing performance on large data sets.

Learn a recursive binary search in Python, adding start and end parameters, base cases, and halving the search space to locate a target or return None.

Explore trees as hierarchical data structures and abstract data types, covering nodes, root and leaves, depth, height, paths, edges, and the basics of binary search trees and recursion.

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.

Implement a binary search tree in Python by building a TreeNode class and a recursive insert method, while preparing to traverse and find the minimum and maximum values.

Examine min and max methods in a binary tree, comparing recursive and iterative solutions, verify leftmost and rightmost values (15 and 32), and prepare for implementing remaining methods iteratively.

Explore the four main tree traversal methods—level (breadth-first), pre-order, post-order, and in-order—highlighting how each visits nodes, their uses, and practical examples.

Implement in-order traversal of a binary search tree with a recursive generator using yield from to yield left, root, and right values; the video also covers pre-order and post-order traversals.

Encapsulate the TreeNode in a BinaryTree class to provide root-based operations, delegating to the root and handling empty trees for min, max, insert, and in-order traversal.

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.

Visualize binary trees using Graphviz and the Python graphviz package. Create a digraph, render dot files, and color left edges green and right edges red to display the tree structure.

Explore deleting nodes in a binary search tree, covering leaf and single-child cases, then replace two-child nodes with max in left or min in right subtree via copying values.

implement an iterative delete method for a binary tree, covering root handling, nodes with zero or one child, and two-children cases using the right-subtree successor.

Learn to delete a value from a binary search tree using a recursive approach, handling zero to two children and replacing with the minimum in the right subtree; ValueError handling.

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.

Learn to search a binary search tree by iterative in-order traversal to find a key, with keyed trees storing values by ids and get operations.

Explore how self-balancing binary search trees prevent degenerate structures from sorted insertions, using rotations in AVL and red-black trees to maintain fast logarithmic searches.

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.

Explains how to implement insertion into a red-black tree in Python by translating a C algorithm, rebalancing tree, and adapting binary tree code with colours, nil sentinel, and parent pointers.

Implement Python code for inserting into a red-black tree by tracing the insert path to find the parent. Use rotate_dir to perform rotations and set_child to update pointers for rebalance.

Translate the rb_insert1 insertion method from C to Python for a red-black tree, detailing rotations, recoloring, and cases 1–6 to maintain balance.

Delete a node from a red-black tree, covering cases with two, one, or no children, and maintain tree balance through rotations and recolouring in Python.