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

[00:00] data structures are super important to

[00:01] know for technical coding interviews and

[00:03] computer science in general and so in

[00:05] this video I'm going to be breaking down

[00:06] some of the most popular data structures

[00:08] out there what they look like and how

[00:10] they operate real world examples so you

[00:12] can actually picture what I'm talking

[00:13] about plus their time complexities but

[00:15] more on that later and if you're new

[00:17] here hi my name is zad I have a

[00:18] bachelor's and Masters in computer

[00:20] science from Georgia Tech I have

[00:21] software engineering experience working

[00:23] at top tech companies like Amazon and

[00:25] every single day I help hundreds of

[00:26] thousands of people break into Tech

[00:28] before we get into any particular

[00:29] particular data structure we do need to

[00:31] understand one big concept called Big O

[00:34] this is our way of measuring speed and

[00:36] efficiency how well data structures are

[00:38] actually operating in different

[00:40] scenarios for example if I'm in New York

[00:42] and I want to go to California I could

[00:44] walk there it might take me a month I

[00:46] could bike there in a couple weeks I

[00:48] could drive there in a few days or I

[00:50] could fly there in just a few hours

[00:53] different vehicles are optimized for

[00:54] different scenarios just like different

[00:55] data structures are also optimized for

[00:57] different scenarios but for vehicles we

[00:59] measured the by Miles hour but for the

[01:01] speed of data structures and how they

[01:03] operate we use time complexity or Big O

[01:06] notation if you're not understanding

[01:08] this let me break down four different

[01:10] types of Big O notation first one we got

[01:12] o of one constant time this is the

[01:14] fastest an algorithm can operate think

[01:17] like rocket ship speed of light o of one

[01:19] means the operation takes the same

[01:21] amount of time no matter how much data

[01:23] there is imagine you have a grocery list

[01:26] and you want to grab just the first item

[01:28] on the list whether that list is five

[01:30] items 500 items 5,000 items the

[01:33] operation is the same exact thing you

[01:35] just need to take the first one

[01:37] instantly there's no extra effort

[01:38] despite how long the list is so it's

[01:40] super fast and super efficient a level

[01:42] above that we have o of n linear time

[01:46] where n in this case represents the

[01:48] amount of data that we have this is

[01:50] still a pretty fast operation so you can

[01:52] imagine not speed of light but like

[01:54] superar and specifically o of n this is

[01:57] when the amount of data increases the

[01:59] time it takes grows at that same rate

[02:01] for example if you have a list of names

[02:03] and you need to find a specific name the

[02:05] worst case is you have to check every

[02:07] single name until you find that name if

[02:09] you have a list of 10 names you might

[02:10] have to do 10 checks if there are a

[02:12] th000 names you might have to do 1,000

[02:14] checks we don't know the position in the

[02:16] list like we did for the O of one

[02:18] scenario and so as the data increases in

[02:21] size it takes longer cuz there's just a

[02:23] longer operation just more to deal with

[02:25] but it's a very predictable increase a

[02:27] level above that we have quadratic time

[02:30] o of n s think of biking from New York

[02:33] to California I mean like very very slow

[02:36] and this happens when every single item

[02:38] in a data set needs to interact with

[02:40] every other item imagine you have a

[02:42] classroom full of students and each

[02:44] student has to shake hands with every

[02:46] other student if there are 10 students

[02:48] that means 10 * 10 100 handshakes if

[02:51] there are 100 students that is 100 * 100

[02:55] 10,000 handshakes the amount of work

[02:57] this operation has to go through grows

[02:59] way too fast the more students that are

[03:02] added into the mix and if you have an

[03:03] algorithm that takes o of n^2 time

[03:06] complexity just know that's a really

[03:07] slow really bad algorithm and chances

[03:10] are there's a better scenario now the

[03:11] fourth scenario I want to talk about is

[03:13] a slight curve ball and that is O of log

[03:16] n logarithmic time and this one is

[03:19] faster than o of n but slower than o of

[03:22] one so it's not the speed of light it's

[03:24] like the speed of sound it's still

[03:26] really fast an example for you to

[03:28] understand this is Imagine trying to

[03:30] look up a word in the dictionary

[03:32] typically if you have like a random word

[03:34] what people generally do is they open up

[03:36] the dictionary to the middle somewhere

[03:38] in the middle and from there you decide

[03:40] does the word I'm looking for come

[03:42] before or after the current page I'm on

[03:44] and so depending on that you'll jump

[03:46] forward or backward and you'll repeat

[03:48] that process until you find your desired

[03:50] word each time we're jumping Pages we're

[03:52] cutting the amount of time that we're

[03:54] looking in our search by a half we're

[03:56] not going through every single page in a

[03:59] dictionary that would be o of n but

[04:00] rather we're going half and then half of

[04:02] that half of that and the search space

[04:04] of the operation just gets smaller and

[04:06] smaller and actually if you look at a

[04:07] logarithm graph at a certain point as

[04:09] you keep increasing the input the

[04:11] difference in the output is so small and

[04:13] so marginal and so these are the

[04:14] different time complexities that

[04:16] different data structures can have and

[04:17] now that we understand how things are

[04:19] getting measured let's start off with

[04:20] our first data structure and we're going

[04:22] to be talking about the array think of

[04:24] an array like a row of middle school

[04:25] lockers each Locker has a fixed position

[04:28] and you can quickly go to any one of

[04:29] them just by knowing its number arrays

[04:31] store data in a contiguous manner

[04:33] meaning all elements are placed side by

[04:36] side by side in memory because each

[04:38] element has a specific index retrieving

[04:40] a value is extremely fast and you can go

[04:43] directly to its position without like

[04:44] searching however if the array is

[04:46] already full and you want to add a new

[04:48] element that can be a little tricky cuz

[04:50] you can't just squeeze another item it's

[04:52] a fixed size just like you can't add a

[04:54] new Locker you might have to break down

[04:56] a wall similarly you need to create a

[04:58] new larger array and all existing

[05:01] elements must be copied over and then

[05:03] the new element can be added but there

[05:05] is a structure that's similar to an

[05:06] array that handles this resizing a

[05:08] little bit better if you know which one

[05:10] I'm talking about and why it's better

[05:12] let me know in the comments down below

[05:13] and I might give you a shout out in my

[05:15] next video in terms of time complexities

[05:17] accessing any element by an index is an

[05:19] O of one operation so it's super

[05:21] efficient inserting an element at a

[05:22] position is also o of one if you're

[05:24] simply replacing an existing item but

[05:27] inserting a value beyond the array side

[05:30] requires creating a whole another array

[05:32] which takes o of n time cuz you have to

[05:34] copy over a whole array deleting an

[05:36] element is also o of nend because once

[05:38] an element is removed all subsequent

[05:40] elements must shift down to maintain the

[05:42] array's contiguous structure unless

[05:44] you're deleting at the very end of the

[05:46] array in that case it's an O of one

[05:48] because you're just removing the last

[05:49] element and there's no shifting

[05:51] downwards the next data structure we're

[05:52] going to be talking about is the linked

[05:54] list think of a linked list like a train

[05:56] where each car is connected to the next

[05:59] one if you if you want to reach a

[06:00] specific car you can't just teleport to

[06:02] it you have to start from the front and

[06:04] move through each car until you find the

[06:06] one that you need in link list each

[06:08] element is stored in a separate node and

[06:10] each node contains both a value and a

[06:12] pointer to the next node in the sequence

[06:14] this makes link list more flexible than

[06:16] arrays since you can easily add or

[06:18] remove elements without worrying about

[06:20] shifting everything around however

[06:22] accessing specific elements is slower

[06:25] because you have to Traverse the list

[06:26] from the beginning to find it so in

[06:28] terms of time comple

[06:30] accessing an element by an index is an O

[06:32] of n operation because you actually have

[06:34] to go through the list there's no index

[06:36] inbuilt into the link list inserting an

[06:38] element at a position is an O of one

[06:40] operation if you already have reference

[06:42] to the node that you're trying to insert

[06:44] around but if you actually have to

[06:46] search for it once again you're

[06:48] traversing the list so that's going to

[06:49] be an O of n operation deleting an

[06:51] element similar to inserting is O of one

[06:54] if you have the right reference because

[06:55] all you have to do is just switch around

[06:57] the pointers but if you have to search

[06:59] for that reference it's an O of n

[07:01] operation once again the nice thing is

[07:02] unlike an array deleting from a linked

[07:04] list doesn't require shifting elements

[07:06] around so sometimes it can be a little

[07:08] more efficient in this type of use case

[07:10] plus there's also no resizing issue

[07:11] because it's just nodes and pointers

[07:13] there's no like fixed structures that

[07:14] you have to deal with the next data

[07:16] structure we're going to talk about is

[07:17] the stack this is a simple structure

[07:19] that follows a last in first out

[07:21] principle meaning the last element added

[07:23] is the first one to be removed think of

[07:25] a stack of chips you have to eat the top

[07:28] one first before you can e the next one

[07:30] each element in a stack is stored in an

[07:32] ordered manner but unlike arrays you can

[07:34] only access or modify elements from the

[07:36] top of the stack this makes retrieval

[07:38] and insertion extremely efficient

[07:40] because there's no shifting around for

[07:42] the Big O time complexity for a stack

[07:44] there's no accessing really at a

[07:46] particular index because you only take

[07:48] or remove from the top itself but if you

[07:51] have to access or search through a stack

[07:52] that would be an O of n operation

[07:54] because you have to go through each

[07:56] element one by one by one there's no

[07:58] indexing inserting an element which is

[08:00] called pushing onto the stack is an O of

[08:02] one operation because you simply add the

[08:04] element to the top of the stack without

[08:06] affecting any other structure within the

[08:08] stack deleting an element which is

[08:10] called popping from the stack once again

[08:12] is an O of one operation because you

[08:14] only have to remove from the top of the

[08:16] element there's no dealing with the

[08:17] other elements when you're taking or

[08:19] removing from a stack so it's highly

[08:21] efficient for adding or removing plus

[08:23] it's very widely used in depth for

[08:25] search but more on that later the next

[08:27] data structure we're going to talk about

[08:28] is the Q and unlike a stack that was

[08:30] last and first out this is a first and

[08:33] first out which means the first element

[08:35] added is the first element to be removed

[08:37] think of it when you're standing in line

[08:39] at the store the person at the front

[08:41] gets to the checkout first and then they

[08:42] get dealt with first any new people that

[08:44] want to join the line has to join in in

[08:46] the back and must wait their turn till

[08:48] they come to the front each element in a

[08:50] queue is stored in an ordered manner but

[08:53] unlike an array which is also ordered

[08:55] these elements can be added only in the

[08:57] back and removed in the front for the

[08:59] Big O time complexity of a que just like

[09:02] a stack you can't access element by

[09:04] their index but for some reason if you

[09:06] have to go through the whole queue to

[09:07] find a certain element that would be an

[09:08] O of n operation to access or search if

[09:11] you're not just trying to access the

[09:13] first element there in terms of

[09:14] insertion or deltion those are o of one

[09:17] operations because you add to the back

[09:19] remove from the front and it's just

[09:20] continuous think of a stack but in

[09:22] slight reverse order plus qes are highly

[09:25] used in breath th search and Spotify

[09:26] music the next data structure we're

[09:28] going to talk about is the Heap or

[09:30] priority CU think of a heap like a

[09:32] pyramid of stacked boxes where the

[09:35] smallest Box is always at the very top

[09:38] you don't randomly grab a box from the

[09:40] middle you always take from the top but

[09:42] specifically for heaps they actually

[09:44] always need a box to be at the top like

[09:47] if any boxes are removed within the

[09:49] pyramid they need to readjust so there's

[09:51] a box still at the top so it can

[09:52] maintain that structure also there are

[09:54] two types of heaps that you need to know

[09:56] first is a Min Heap where every parent

[09:58] is smaller than its children and the top

[10:00] element is the smallest while in a Max

[10:03] Heap every parent is larger than its

[10:05] children and the top element is the

[10:07] largest for efficiency accessing an

[10:09] element by its index is not a general

[10:11] operation but if needed it would be o of

[10:14] one to access the top element which we

[10:16] call the root and O of n for any

[10:19] arbitrary elements within the Heap

[10:21] inserting an element is a o of login

[10:23] procedure because first it's added into

[10:25] the Heap and then because of the Heap

[10:27] property of the parent child ration ship

[10:29] being bigger or smaller it bubbles up to

[10:32] its right position similarly removing is

[10:34] also o of login because it removes the

[10:36] elements and then bubbles down to

[10:38] restore the Heap property and since

[10:39] heaps are actually balanced binary trees

[10:42] which more on that later both insertion

[10:44] and deletion operations are extremely

[10:46] efficient compared to linear data

[10:48] structures like arrays or link lists

[10:50] which we talked about the next data

[10:51] structure we're going to talk about is

[10:52] the hashmap and make sure you know this

[10:55] one think of a hashmap like a mail room

[10:57] in an office where every empy employee

[10:59] has a dedicated mailbox instead of

[11:01] sorting through all the mail one by one

[11:03] by one you just look oh John his mailbox

[11:06] is number four Sally her mailbox is

[11:09] number five you know exactly where to

[11:11] put it and John and Sally know exactly

[11:13] where to access it a hashmap stores data

[11:16] using key value pairs where each key is

[11:18] run through a hash function that

[11:20] determines where the value should be

[11:21] stored an example of a hash function

[11:23] could be the length of a string so

[11:25] John's name for example is four

[11:27] characters long so he's in position four

[11:29] Sally is in position five her name is

[11:31] five characters long this makes lookups

[11:33] on hash Maps extremely efficient time

[11:36] complexity wise being 0 of one however

[11:38] if too many items hash to the same

[11:40] mailbox which we call a hash Collision

[11:42] for example if a new employee Andy joins

[11:45] well his name is also four letters we

[11:47] can't just put him in position number

[11:48] four because that's where JN is so we

[11:51] need to have a hash Collision resolution

[11:53] which could be a linkless chaining from

[11:54] the hashmap position or it could be

[11:57] linear probing where you find the next

[11:58] available position either way this is

[12:00] the only real downside to hashmaps

[12:02] otherwise they are super super efficient

[12:04] as a data structure so overall accessing

[12:06] an element by its key in a hashmap is an

[12:08] O of one operation but it could be o of

[12:11] n worst case if everything is put onto

[12:13] that link list and you have to do a lot

[12:14] of searching inserting an element is an

[12:16] O of one operation but worst case

[12:19] scenario that could end up being o ofen

[12:21] deleting an element is also an O of one

[12:23] operation because if you have the right

[12:24] key you can just go to the value but if

[12:26] there is a long length list that you

[12:28] have to deal with to find the actual

[12:30] element that you're dealing with that

[12:31] could end up being an O of end operation

[12:33] by the way if you use Python you

[12:35] probably call hashmaps dictionaries but

[12:36] they're pretty much the same thing the

[12:38] next data structure we're going to talk

[12:39] about is the binary search tree so it's

[12:41] a tree it looks similar to a family tree

[12:44] but the key difference is each node

[12:46] follows a specific ordering rule the

[12:48] left child has to contain values smaller

[12:51] than the parent and the right child has

[12:53] to contain values greater than the

[12:55] parent this makes searching insertion

[12:57] and deletion extremely efficient in

[12:58] terms of the Big O accessing inserting

[13:01] and deleting into a binary search tree

[13:03] is an O of login procedure because of

[13:05] the rules of the left parent and right

[13:07] needing to be less than one another

[13:09] while we're dealing with the elements

[13:10] every time we look to access an element

[13:12] insert an element or delete an element

[13:14] you can literally eliminate half the

[13:16] tree as we're going through it so it's

[13:18] like going through the dictionary trying

[13:19] to find that word because you're just

[13:21] splitting up your search Space by half

[13:23] every layer that you're going but worst

[13:25] case if your binary search tree is

[13:26] unbalanced for some reason and it looks

[13:28] something something similar to a link

[13:30] list each of those operations access

[13:32] insertion and deletion becomes o of n

[13:34] because you might have to go through

[13:36] each element there's no elimination of

[13:37] search space the next data structure

[13:39] we're going to talk about is the set and

[13:41] I want you to think of this like

[13:43] thanos's Infinity Gauntlet it can hold

[13:46] powerful stones but each stone is unique

[13:49] if Thanos tries to add the same Stone

[13:51] twice it simply won't work because the

[13:53] gauntlet can only allow one of each kind

[13:56] also the order in which he collects the

[13:58] stones doesn't matter matter at all as

[13:59] long as like he has all the stones in

[14:01] whatever order they're all unique it'll

[14:03] be good sets are very useful if you're

[14:05] searching through trees or you're

[14:07] searching through graphs and you want to

[14:08] keep track of if you visited a certain

[14:10] node or not and overall the definition

[14:12] of a set is an unordered collection of

[14:14] unique elements typically implemented

[14:16] using a hash table similarly the

[14:18] efficiency of a hash map with the hash

[14:20] function this makes checking for the

[14:21] existence of an element extremely fast

[14:24] which means 0 of one on average time

[14:26] however similar to all the issues that

[14:28] we had with the hash function and the

[14:30] hash Maps causing potential collisions

[14:32] that can take it all the way up to O of

[14:34] n unlike a razor link list sets don't

[14:36] store duplicates and they don't maintain

[14:37] a specific order and in fact they're

[14:39] actually used for a lot of coding

[14:40] interview questions such as removing

[14:42] duplicates from a link list removing

[14:43] duplicates from a data set or checking

[14:45] for a certain membership or performing

[14:47] mathematical set operations so make sure

[14:49] you know your sets because it's never

[14:51] going to be the main data structure but

[14:53] it's always going to be something to

[14:54] have in handy just like thanos's

[14:56] Gauntlet in terms of the Big O time

[14:58] complexity in inserting and deleting are

[15:00] going to be o of one operations because

[15:02] of the whole hash function but if

[15:04] there's so many cash collisions once

[15:06] again it's going to be o ofn worst case

[15:08] just like it was for the hashmap and

[15:10] that's if the case is it's run by hash

[15:12] tables in the background there are

[15:14] various other ways to create sets I just

[15:17] gave you an example of a hash set and if

[15:19] you're interested in leveling up your

[15:20] career applying your data structures

[15:22] knowledge two actual leite code problems

[15:24] that show up in top Tech interviews for

[15:26] companies like Amazon or Google you

[15:28] might want to check out my newsletter

[15:29] down below where I'm going to send you

[15:31] guys links for popular leak code

[15:33] Problems by each company for different

[15:35] data structures so you guys can practice

[15:37] and really get ahead of the game well

[15:38] that's about all I have in this video I

[15:39] really hope that you guys enjoyed it and

[15:41] if you did make sure to hit the like

[15:42] button subscribe if you haven't already

[15:44] and now if you're interested in landing

[15:45] a software engineering internship for

[15:47] summer of 2025 check out this video

[15:49] right here