Data Structures Explained for Beginners - How I Wish I was Taught

Summary

Highlights

• Big O Notation explained with relatable travel examples! 🚀
• Learn about constant, linear, quadratic, and logarithmic time complexities. 🎓
• Get clarity on arrays and how they compare to lockers in a hallway. 🚪
• Discover the different ways data structures handle resizing and storage! 📚
• Linked Lists vs Arrays - what's more flexible and why. 🚂📖
• Stacks and Queues - two sides of the same coin in data handling. 🥞🔄
• Understand heaps and why they keep recalibrating like a Rubik's cube! 🧩
• Hashmaps demystified - the office mail room analogy explained. 📬
• Binary Search Trees as the most efficient tree structure for searching! 🌲
• Sets and their unique property of maintaining only distinct items! 💎

Key Takeaways

• Understanding Big O Notation: It's like choosing the best vehicle for different travel scenarios! 🚗🚀
• Arrays are like lockers - fast to access, tricky to resize! 🚪🔑
• Linked Lists are train cars, easy to add but slow to access! 🚂🛤️
• Stacks follow last in, first out - think of Pringles! 🥔🥢
• Queues are first in, first out, like lines at a store! 🛒🕒
• Heaps always keep the minimum or maximum 'box' at the top! 📦🏔️
• Hashmaps store key-value pairs like office mailboxes! 📨📬
• Binary Search Trees - organized like a family tree for quick access! 🌳👨‍👩‍👧
• Sets are like Thanos' gauntlet: no duplicates allowed! 💎🧤

Overview

Chapters

• 00:00 - 00:30: Introduction to Data Structures The chapter "Introduction to Data Structures" emphasizes the importance of understanding data structures for both technical coding interviews and general computer science. The instructor, Zad, aims to break down popular data structures, explaining their appearance, operation, real-world examples, and time complexities. Zad introduces himself as a computer science graduate with experience at top tech companies like Amazon, and mentions that he assists many people in entering the tech industry.
• 00:30 - 01:00: Importance of Big O The chapter titled 'Importance of Big O' introduces Big O notation, a concept used to assess the speed and efficiency of data structures in various scenarios. The analogy of traveling from New York to California illustrates how different methods (i.e., walking, biking, driving, flying) vary in time efficiency, similar to how different data structures are optimized for specific situations. This chapter aims to highlight the crucial role of Big O in determining the most suitable data structure for a given scenario.
• 01:00 - 03:00: Types of Big O Notations The chapter titled 'Types of Big O Notations' discusses the importance of measuring the efficiency of data structures using time complexity, specifically Big O notation. It introduces four different types of Big O notations. The first one discussed is O(1), or constant time, which represents the fastest an algorithm can operate. This means the operation takes the same amount of time regardless of the amount of data. An example provided is grabbing the first item from a grocery list, which takes the same time whether the list has five items or five hundred.
• 04:00 - 05:00: Introduction to Arrays This chapter introduces the concept of arrays and describes different levels of time complexity related to operations on arrays, notably O(1) constant time and O(n) linear time. It discusses the efficiency of operations, highlighting that accessing the first element in an array is an O(1) operation, meaning it is performed in constant time irrespective of the length of the array, making it extremely fast and efficient. The chapter further explains O(n) linear time complexity, where the time taken grows proportionally with the increase in the number of data elements, comparing this to a ‘superar’ speed, faster than normal speed but not as fast as constant time operations.
• 05:00 - 07:00: Introduction to Linked Lists The chapter introduces linked lists, explaining the complexity of searching within a list. It highlights the worst-case scenario of searching, where one might need to check every element in the list, making it a linear time complexity, denoted as O(n). As the number of items grows, the time to search them grows linearly. Unlike constant time complexity (O(1)), where you can quickly find an item if you know its position, linear time complexity is more contingent on the size of the list. The chapter also touches on quadratic time, suggesting more complex time scenarios.
• 07:00 - 08:00: Introduction to Stacks The introduction to stacks explains the complexity of operations that require interaction between all items in a data set, comparing it to a scenario where each student in a classroom has to shake hands with every other student. This scenario illustrates how the amount of work increases exponentially with the number of students.
• 08:00 - 09:00: Introduction to Queues In the 'Introduction to Queues' chapter, the concept of algorithm time complexity is discussed, specifically highlighting O(n^2) as a very inefficient algorithm due to its slow execution. The chapter also introduces O(log n) time complexity, describing it as faster than linear time (O(n)) but slower than constant time (O(1)), likening it to the speed of sound compared to the speed of light, emphasizing its efficiency.
• 09:00 - 11:00: Introduction to Heaps The introduction to Heaps draws an analogy to looking up words in a dictionary to explain the concept of efficient search. Instead of going through each page sequentially (O(n) complexity), one can open the dictionary to a middle page, decide if the word would come before or after it, and jump forwards or backwards accordingly. This method effectively cuts down the search time considerably, illustrating a more efficient search process.
• 11:00 - 13:00: Introduction to Hashmaps The transcript introduces the concept of hashmaps by first discussing how data structures are measured in terms of their time complexity. It begins with an explanation of how logarithmic time works, particularly in the context of search space reduction, highlighting that as the input size increases, the difference in output time becomes marginal. The transcript then shifts to the foundational data structure of arrays, analogous to a row of middle school lockers where each locker has a fixed position that can be quickly accessed by its number.
• 13:00 - 15:00: Introduction to Binary Search Trees The chapter introduces Binary Search Trees (BST) in the context of data storage and retrieval, contrasting them with arrays. Arrays store data contiguously, providing fast retrieval since each element has a specific index. However, arrays are fixed in size, making it difficult to add new elements once full. The chapter hints at the limitations of arrays, setting the stage for why binary search trees, which do not have fixed sizes and allow dynamic data management, might be preferred for certain applications.
• 15:00 - 16:30: Introduction to Sets The chapter introduces the concept of sets and their operations, highlighting how elements can be added once they are copied over. It mentions a data structure similar to an array that efficiently handles resizing. The chapter also touches on time complexity for various operations, noting that accessing an element by index is an O(1) operation and inserting an element at a position is also O(1) if it involves replacing an existing item.
• 25:00 - 26:00: Conclusion and Call to Action The chapter delves into the complexities of handling data structures, particularly focusing on arrays and linked lists. It explains the time-consuming nature of operations such as copying or deleting elements in arrays, which can require shifting elements to maintain order. The text draws an analogy between linked lists and train cars to illustrate how each element is connected and dependent, indicating an introduction to a discussion on linked lists as an efficient alternative for certain operations.

Data Structures Explained for Beginners - How I Wish I was Taught Transcription

• 00:00 - 00:30 data structures are super important to know for technical coding interviews and computer science in general and so in this video I'm going to be breaking down some of the most popular data structures out there what they look like and how they operate real world examples so you can actually picture what I'm talking about plus their time complexities but more on that later and if you're new here hi my name is zad I have a bachelor's and Masters in computer science from Georgia Tech I have software engineering experience working at top tech companies like Amazon and every single day I help hundreds of thousands of people break into Tech before we get into any particular particular data structure we do need to
• 00:30 - 01:00 understand one big concept called Big O this is our way of measuring speed and efficiency how well data structures are actually operating in different scenarios for example if I'm in New York and I want to go to California I could walk there it might take me a month I could bike there in a couple weeks I could drive there in a few days or I could fly there in just a few hours different vehicles are optimized for different scenarios just like different data structures are also optimized for different scenarios but for vehicles we measured the by Miles hour but for the
• 01:00 - 01:30 speed of data structures and how they operate we use time complexity or Big O notation if you're not understanding this let me break down four different types of Big O notation first one we got o of one constant time this is the fastest an algorithm can operate think like rocket ship speed of light o of one means the operation takes the same amount of time no matter how much data there is imagine you have a grocery list and you want to grab just the first item on the list whether that list is five
• 01:30 - 02:00 items 500 items 5,000 items the operation is the same exact thing you just need to take the first one instantly there's no extra effort despite how long the list is so it's super fast and super efficient a level above that we have o of n linear time where n in this case represents the amount of data that we have this is still a pretty fast operation so you can imagine not speed of light but like superar and specifically o of n this is when the amount of data increases the time it takes grows at that same rate
• 02:00 - 02:30 for example if you have a list of names and you need to find a specific name the worst case is you have to check every single name until you find that name if you have a list of 10 names you might have to do 10 checks if there are a th000 names you might have to do 1,000 checks we don't know the position in the list like we did for the O of one scenario and so as the data increases in size it takes longer cuz there's just a longer operation just more to deal with but it's a very predictable increase a level above that we have quadratic time
• 02:30 - 03:00 o of n s think of biking from New York to California I mean like very very slow and this happens when every single item in a data set needs to interact with every other item imagine you have a classroom full of students and each student has to shake hands with every other student if there are 10 students that means 10 * 10 100 handshakes if there are 100 students that is 100 * 100 10,000 handshakes the amount of work this operation has to go through grows way too fast the more students that are
• 03:00 - 03:30 added into the mix and if you have an algorithm that takes o of n^2 time complexity just know that's a really slow really bad algorithm and chances are there's a better scenario now the fourth scenario I want to talk about is a slight curve ball and that is O of log n logarithmic time and this one is faster than o of n but slower than o of one so it's not the speed of light it's like the speed of sound it's still really fast an example for you to understand this is Imagine trying to
• 03:30 - 04:00 look up a word in the dictionary typically if you have like a random word what people generally do is they open up the dictionary to the middle somewhere in the middle and from there you decide does the word I'm looking for come before or after the current page I'm on and so depending on that you'll jump forward or backward and you'll repeat that process until you find your desired word each time we're jumping Pages we're cutting the amount of time that we're looking in our search by a half we're not going through every single page in a dictionary that would be o of n but
• 04:00 - 04:30 rather we're going half and then half of that half of that and the search space of the operation just gets smaller and smaller and actually if you look at a logarithm graph at a certain point as you keep increasing the input the difference in the output is so small and so marginal and so these are the different time complexities that different data structures can have and now that we understand how things are getting measured let's start off with our first data structure and we're going to be talking about the array think of an array like a row of middle school lockers each Locker has a fixed position and you can quickly go to any one of them just by knowing its number arrays
• 04:30 - 05:00 store data in a contiguous manner meaning all elements are placed side by side by side in memory because each element has a specific index retrieving a value is extremely fast and you can go directly to its position without like searching however if the array is already full and you want to add a new element that can be a little tricky cuz you can't just squeeze another item it's a fixed size just like you can't add a new Locker you might have to break down a wall similarly you need to create a new larger array and all existing
• 05:00 - 05:30 elements must be copied over and then the new element can be added but there is a structure that's similar to an array that handles this resizing a little bit better if you know which one I'm talking about and why it's better let me know in the comments down below and I might give you a shout out in my next video in terms of time complexities accessing any element by an index is an O of one operation so it's super efficient inserting an element at a position is also o of one if you're simply replacing an existing item but inserting a value beyond the array side
• 05:30 - 06:00 requires creating a whole another array which takes o of n time cuz you have to copy over a whole array deleting an element is also o of nend because once an element is removed all subsequent elements must shift down to maintain the array's contiguous structure unless you're deleting at the very end of the array in that case it's an O of one because you're just removing the last element and there's no shifting downwards the next data structure we're going to be talking about is the linked list think of a linked list like a train where each car is connected to the next one if you if you want to reach a
• 06:00 - 06:30 specific car you can't just teleport to it you have to start from the front and move through each car until you find the one that you need in link list each element is stored in a separate node and each node contains both a value and a pointer to the next node in the sequence this makes link list more flexible than arrays since you can easily add or remove elements without worrying about shifting everything around however accessing specific elements is slower because you have to Traverse the list from the beginning to find it so in terms of time comple
• 06:30 - 07:00 accessing an element by an index is an O of n operation because you actually have to go through the list there's no index inbuilt into the link list inserting an element at a position is an O of one operation if you already have reference to the node that you're trying to insert around but if you actually have to search for it once again you're traversing the list so that's going to be an O of n operation deleting an element similar to inserting is O of one if you have the right reference because all you have to do is just switch around the pointers but if you have to search for that reference it's an O of n
• 07:00 - 07:30 operation once again the nice thing is unlike an array deleting from a linked list doesn't require shifting elements around so sometimes it can be a little more efficient in this type of use case plus there's also no resizing issue because it's just nodes and pointers there's no like fixed structures that you have to deal with the next data structure we're going to talk about is the stack this is a simple structure that follows a last in first out principle meaning the last element added is the first one to be removed think of a stack of chips you have to eat the top one first before you can e the next one
• 07:30 - 08:00 each element in a stack is stored in an ordered manner but unlike arrays you can only access or modify elements from the top of the stack this makes retrieval and insertion extremely efficient because there's no shifting around for the Big O time complexity for a stack there's no accessing really at a particular index because you only take or remove from the top itself but if you have to access or search through a stack that would be an O of n operation because you have to go through each element one by one by one there's no indexing inserting an element which is
• 08:00 - 08:30 called pushing onto the stack is an O of one operation because you simply add the element to the top of the stack without affecting any other structure within the stack deleting an element which is called popping from the stack once again is an O of one operation because you only have to remove from the top of the element there's no dealing with the other elements when you're taking or removing from a stack so it's highly efficient for adding or removing plus it's very widely used in depth for search but more on that later the next data structure we're going to talk about is the Q and unlike a stack that was
• 08:30 - 09:00 last and first out this is a first and first out which means the first element added is the first element to be removed think of it when you're standing in line at the store the person at the front gets to the checkout first and then they get dealt with first any new people that want to join the line has to join in in the back and must wait their turn till they come to the front each element in a queue is stored in an ordered manner but unlike an array which is also ordered these elements can be added only in the back and removed in the front for the Big O time complexity of a que just like
• 09:00 - 09:30 a stack you can't access element by their index but for some reason if you have to go through the whole queue to find a certain element that would be an O of n operation to access or search if you're not just trying to access the first element there in terms of insertion or deltion those are o of one operations because you add to the back remove from the front and it's just continuous think of a stack but in slight reverse order plus qes are highly used in breath th search and Spotify music the next data structure we're going to talk about is the Heap or
• 09:30 - 10:00 priority CU think of a heap like a pyramid of stacked boxes where the smallest Box is always at the very top you don't randomly grab a box from the middle you always take from the top but specifically for heaps they actually always need a box to be at the top like if any boxes are removed within the pyramid they need to readjust so there's a box still at the top so it can maintain that structure also there are two types of heaps that you need to know first is a Min Heap where every parent is smaller than its children and the top
• 10:00 - 10:30 element is the smallest while in a Max Heap every parent is larger than its children and the top element is the largest for efficiency accessing an element by its index is not a general operation but if needed it would be o of one to access the top element which we call the root and O of n for any arbitrary elements within the Heap inserting an element is a o of login procedure because first it's added into the Heap and then because of the Heap property of the parent child ration ship being bigger or smaller it bubbles up to
• 10:30 - 11:00 its right position similarly removing is also o of login because it removes the elements and then bubbles down to restore the Heap property and since heaps are actually balanced binary trees which more on that later both insertion and deletion operations are extremely efficient compared to linear data structures like arrays or link lists which we talked about the next data structure we're going to talk about is the hashmap and make sure you know this one think of a hashmap like a mail room in an office where every empy employee has a dedicated mailbox instead of
• 11:00 - 11:30 sorting through all the mail one by one by one you just look oh John his mailbox is number four Sally her mailbox is number five you know exactly where to put it and John and Sally know exactly where to access it a hashmap stores data using key value pairs where each key is run through a hash function that determines where the value should be stored an example of a hash function could be the length of a string so John's name for example is four characters long so he's in position four Sally is in position five her name is
• 11:30 - 12:00 five characters long this makes lookups on hash Maps extremely efficient time complexity wise being 0 of one however if too many items hash to the same mailbox which we call a hash Collision for example if a new employee Andy joins well his name is also four letters we can't just put him in position number four because that's where JN is so we need to have a hash Collision resolution which could be a linkless chaining from the hashmap position or it could be linear probing where you find the next available position either way this is
• 12:00 - 12:30 the only real downside to hashmaps otherwise they are super super efficient as a data structure so overall accessing an element by its key in a hashmap is an O of one operation but it could be o of n worst case if everything is put onto that link list and you have to do a lot of searching inserting an element is an O of one operation but worst case scenario that could end up being o ofen deleting an element is also an O of one operation because if you have the right key you can just go to the value but if there is a long length list that you have to deal with to find the actual
• 12:30 - 13:00 element that you're dealing with that could end up being an O of end operation by the way if you use Python you probably call hashmaps dictionaries but they're pretty much the same thing the next data structure we're going to talk about is the binary search tree so it's a tree it looks similar to a family tree but the key difference is each node follows a specific ordering rule the left child has to contain values smaller than the parent and the right child has to contain values greater than the parent this makes searching insertion and deletion extremely efficient in terms of the Big O accessing inserting
• 13:00 - 13:30 and deleting into a binary search tree is an O of login procedure because of the rules of the left parent and right needing to be less than one another while we're dealing with the elements every time we look to access an element insert an element or delete an element you can literally eliminate half the tree as we're going through it so it's like going through the dictionary trying to find that word because you're just splitting up your search Space by half every layer that you're going but worst case if your binary search tree is unbalanced for some reason and it looks something something similar to a link
• 13:30 - 14:00 list each of those operations access insertion and deletion becomes o of n because you might have to go through each element there's no elimination of search space the next data structure we're going to talk about is the set and I want you to think of this like thanos's Infinity Gauntlet it can hold powerful stones but each stone is unique if Thanos tries to add the same Stone twice it simply won't work because the gauntlet can only allow one of each kind also the order in which he collects the stones doesn't matter matter at all as long as like he has all the stones in
• 14:00 - 14:30 whatever order they're all unique it'll be good sets are very useful if you're searching through trees or you're searching through graphs and you want to keep track of if you visited a certain node or not and overall the definition of a set is an unordered collection of unique elements typically implemented using a hash table similarly the efficiency of a hash map with the hash function this makes checking for the existence of an element extremely fast which means 0 of one on average time however similar to all the issues that we had with the hash function and the
• 14:30 - 15:00 hash Maps causing potential collisions that can take it all the way up to O of n unlike a razor link list sets don't store duplicates and they don't maintain a specific order and in fact they're actually used for a lot of coding interview questions such as removing duplicates from a link list removing duplicates from a data set or checking for a certain membership or performing mathematical set operations so make sure you know your sets because it's never going to be the main data structure but it's always going to be something to have in handy just like thanos's Gauntlet in terms of the Big O time complexity in inserting and deleting are
• 15:00 - 15:30 going to be o of one operations because of the whole hash function but if there's so many cash collisions once again it's going to be o ofn worst case just like it was for the hashmap and that's if the case is it's run by hash tables in the background there are various other ways to create sets I just gave you an example of a hash set and if you're interested in leveling up your career applying your data structures knowledge two actual leite code problems that show up in top Tech interviews for companies like Amazon or Google you might want to check out my newsletter down below where I'm going to send you
• 15:30 - 16:00 guys links for popular leak code Problems by each company for different data structures so you guys can practice and really get ahead of the game well that's about all I have in this video I really hope that you guys enjoyed it and if you did make sure to hit the like button subscribe if you haven't already and now if you're interested in landing a software engineering internship for summer of 2025 check out this video right here