Comprehensive Guide to Data Structures and Algorithmic Efficiency

Introduction to Data Structures and Big O

Data structures are fundamental components of computer science and are essential for success in technical coding interviews. Understanding how these structures operate and their associated efficiencies allows developers to choose the optimal tool for specific programming scenarios. Sajad, who holds both a Bachelor’s and a Master’s degree in Computer Science from Georgia Tech and has software engineering experience at major technology companies like Amazon, explains that different data structures are optimized for different scenarios, much like different vehicles are optimized for different types of travel.

Understanding Big O Notation and Complexities

Before diving into specific data structures, one must understand Big O notation, which is the standard measure for the speed and efficiency of an algorithm or data structure operation. To illustrate the concept of efficiency, Sajad uses the analogy of traveling from New York to California. One could walk (taking a month), bike (taking a couple of weeks), drive (taking a few days), or fly (taking a few hours). While vehicles are measured in miles per hour, data structures are measured using Time Complexity or Big O notation.

$O(1)$ Constant Time represents the fastest an algorithm can operate, analogous to a rocket ship or the speed of light. In $O(1)$ operations, the time required remains identical regardless of the volume of data. An example is retrieving the first item from a grocery list; whether the list contains $5$, $500$, or $5,000$ items, the effort to grab the first entry is instantaneous and constant.

$O(n)$ Linear Time is a relatively fast operation, comparable to a supercar. Here, $n$ represents the amount of data. As the data increases, the time taken grows at the same linear rate. In the worst-case scenario of searching for a specific name in a list, you must check every entry. If there are $10$ names, you perform $10$ checks; if there are $1,000$ names, you perform $1,000$ checks. The increase is predictable and proportional to the input size.

$O(n^2)$ Quadratic Time is considered a slow and generally inefficient complexity, likened to biking from New York to California. This occurs when every item in a dataset must interact with every other item. For instance, in a classroom where every student must shake hands with every other student, $10$ students results in $10 \times 10 = 100$ handshakes. If the class grows to $100$ students, it results in $100 \times 100 = 10,000$ handshakes. If an algorithm performs at $O(n^2)$, there is often a more efficient alternative available.

$O(\log n)$ Logarithmic Time is faster than linear time but slower than constant time, comparable to the speed of sound. This is often seen in binary search strategies, such as looking up a word in a dictionary. Instead of checking every page ($O(n)$), a person typically opens the book to the middle and determines if the target word is before or after that point, effectively cutting the search space in half with every step. As the input increases, the marginal increase in output time becomes increasingly small.

Arrays: Contiguous Data Storage

An array can be visualized as a row of middle school lockers where each locker has a fixed position and a specific number. Arrays store data in a contiguous manner, meaning elements are placed side-by-side in memory. This allows for extremely fast retrieval if the index is known. However, arrays have a fixed size. Adding a new element to a full array is difficult; it requires creating a new, larger array and copying all existing elements into it before adding the new one.

In terms of Big O complexities, accessing an element by its index is an $O(1)$ operation. Inserting a value is $O(1)$ if it is simply replacing an existing item, but it becomes $O(n)$ if the array must be resized and elements copied. Deleting an element is generally $O(n)$ because all subsequent elements must shift down to fill the gap, though deleting the very last element is $O(1)$ as no shifting is required.

Linked Lists: Dynamic Node Connections

A linked list is comparable to a train where each car (node) is connected to the next. To reach a specific car, one cannot jump directly to it but must travel from the front of the train through each car. Each node in a linked list contains a value and a pointer to the next node. This structure is more flexible than an array because elements can be added or removed without shifting the entire structure or worrying about fixed memory sizes.

Accessing an element by index in a linked list is an $O(n)$ operation because the list must be traversed. Insertion and deletion are $O(1)$ operations if the developer already has a reference to the specific node to be changed, as it only involves updating pointers. However, if the node must be searched for first, the operation becomes $O(n)$. Linked lists avoid the resizing issues found in arrays.

Stacks: Last In, First Out (LIFO)

A stack is a simple data structure following the Last In, First Out (LIFO) principle. It is analogous to a stack of chips; the top chip must be consumed before the one beneath it can be accessed. Elements are added and removed only from the top. Stacks are widely used in Depth-First Search (DFS) algorithms.

Inserting an element into a stack is called "pushing," and it is an $O(1)$ operation. Removing an element is called "popping," which is also an $O(1)$ operation since it only affects the top element. However, searching through a stack or accessing an arbitrary element requires going through the structure one by one, making those actions $O(n)$.

Queues: First In, First Out (FIFO)

A queue operates on the First In, First Out (FIFO) principle, similar to a checkout line at a grocery store. The person at the front of the line is served first, and new arrivals must join at the back. Queues are commonly used in Breadth-First Search (BFS) algorithms and in applications like Spotify music playback.

Insertion (at the back) and deletion (from the front) are $O(1)$ operations. Accessing or searching for an arbitrary element within the queue is an $O(n)$ operation, as there is no index-based access.

Heaps and Priority Queues: Hierarchical Structures

A heap, or priority queue, can be imagined as a pyramid of stacked boxes where a specific box (either the smallest or largest) is always at the top (the root). Heaps are balanced binary trees. There are two primary types: a Min Heap, where the parent node is always smaller than its children (smallest at top), and a Max Heap, where the parent is larger than its children (largest at top). If the top element is removed, the heap must readjust (or "bubble") to maintain its properties.

Accessing the root element is an $O(1)$ operation, while accessing an arbitrary element is $O(n)$. Both insertion and removal are $O(\log n)$ operations because the structure must bubble elements up or down to restore the parent-child relationship property. Heaps are more efficient for these tasks than linear structures like arrays or linked lists.

Hash Maps: Key-Value Pair Operations

A hash map (known as a dictionary in Python) is like a mailroom where every employee has a specific mailbox. Instead of searching every box, you use a hash function to determine exactly where a value is stored. For example, if a hash function is based on name length, "John" ($4$ characters) would be in mailbox $4$, and "Sally" ($5$ characters) would be in mailbox $5$.

Hash maps are highly efficient, with average lookups, insertions, and deletions occurring in $O(1)$ time. However, "hash collisions" occur when multiple keys map to the same location (e.g., "Andy" also has $4$ letters and would collide with "John"). Collisions are resolved through methods like linked list chaining or linear probing. In the worst-case scenario where many collisions occur, operations can degrade to $O(n)$.

Binary Search Trees: Ordered Hierarchical Systems

A binary search tree (BST) is a tree structure similar to a family tree but governed by specific rules: the left child of a node must be smaller than the parent, and the right child must be larger. This ordering allows the search space to be halved at every level, similar to a dictionary search.

In a balanced BST, accessing, inserting, and deleting are $O(\log n)$ operations. However, if the tree becomes unbalanced and resembles a linked list, these operations degrade to $O(n)$ because the search space can no longer be effectively halved.

Sets: Unique Collections and the Infinity Gauntlet

A set is an unordered collection of unique elements, much like Thanos’ Infinity Gauntlet. The gauntlet can only hold one of each unique stone; if Thanos tries to add a second stone of the same type, it will not work. In a set, the order of collection does not matter. Sets are typically implemented using a hash table.

Operations such as inserting, deleting, and checking for membership (existence) are generally $O(1)$, though they can reach $O(n)$ in the event of excessive hash collisions. Sets are frequently used in coding interviews to remove duplicates from datasets or to keep track of visited nodes in tree and graph searches.

Questions & Discussion

Audience Question regarding Array Resizing: Sajad mentions that while adding an element to a full array requires creating a new array and copying elements ($O(n)$), there is a specific structure similar to an array that handles resizing more effectively. He asks the audience to identify this structure and explain why it is better in the comments for a potential shout-out in a future video.

Professional Advice and Resources: Sajad encourages students to apply their data structure knowledge to LeetCode problems specifically associated with top tech companies like Amazon and Google. He offers a newsletter that provides links to popular LeetCode problems categorized by company and data structure. Additionally, he directs viewers interested in landing software engineering internships for the Summer of $2025$ to a specific follow-up video.