these are all structures i *thought* i was familiar with, but you have blown my mind!! when i implemented data structures for college assignments i just used the object oriented approach, never thought about how the memory was laid out. it took this video to realize how much that approach leans on the allocator. i dont think i will ever code the same, i mean that sincerely, thank you!
none of this is necessarily new info to me, but you have such a great and straightforward presentation style that i cant help but enjoy watching anyway. keep it up!
You should absolutely have more subs. Your graph/tree explanation just gave me an approach to solve a project of mine. I'm a hobby C++ learner and so this is absolutely amazing.
Absolutely top tier video. If I may add just one thing, it is how to deal with managing the linked list nodes in the "linked lists array". Specifically, how to find an empty slot to place a node after you've added and removed a bunch. Searching through the array is slow so you don't want to do that. The solution is to always have a special linked list stored there, a *free list*, which keeps track of the empty slots. At the start it covers the entire array, every index pointing to the next index. When you add a new linked list node, you remove the first node of the free list and store the node at that index. When you remove a linked list node, you add its index to the free list. This gives O(1) insertion and removal at the cost of an extra field: the start of the free list.
Great comment, I was very tempted to at least mention the free list implementation but it felt like it was getting into too much detail - I'm going to make a video both on linked lists and freelists at some point so will save it for then 🙂
Just discovered your channel yesterday, and this introduction, this has to be the most intuitive formation of the concept of data structures I have heard. Usually it's all just, "it will help you code better" and "it helps solve problems", with no context on why and how. I already knew a lot of the concepts, but still watched through the entire thing. Amazing reference video to share with my friends when they inevitably come asking me for help to explain it to them.
Amazing! Thanks! You're very careful at explaining it in a realistic non-abstract way while also naming things and even showing some wizard tricks, what?! Best teacher! The kind that makes students like the topic more 😸
I have seen many videos on data structures and this is by far the best. Will be the number one source I will be recommending any other new programmers to gain a higher intuitive understanding of the concept. Please keep it up, this is fantastic.
awesome! I had no idea you could represent a Graph with just 2 arrays, Also as soon as you mentioned Modulo for the queue I genuinely got chills. It's such an amazingly useful operator.
This is super well done! I still sometimes have a hard time visualizing the actual code implementation of Hash Maps and Graphs, but this at least makes it a bit easier to picture. Thanks!
the thing that helped me understand pointers, etc. is showing what ptr[offset] translates to in for example C. It becomes this *(ptr + offset) and the compiler then also multiplies the offset by the size of the data type of the pointer. This is why C alows this: offset[ptr] as it just is turned into *(offset + ptr) and the compiler still knows which value to multiply.
Another excellent video Nic. The lesson for me here is that it really makes a huge difference to learn what's under the hood, how it all works. The concepts here really expose the underlying mechanisms in simple enough, practical terms to be easy to grasp and to be very helpful when I'm designing and coding. The basic principles are valuable on their own. Yet if I want to learn more about the algorithms and underlying code that these structures are built on, this video gives me excellent starting points.
Your explanation is always awesome. Really enjoyed the content, always explaining somewhat complex topics in easy to learn terms. Great work, thanks Nic.
I just failed my Data Structures course last trimester. I would have passed if my courses were this one single video: you've made things so clear. Do you have any ressources for diving deeper in the implementation of graph data structures? Thanks a lot !
Don't worry, you'll get it next time 💪 I personally struggled with these kinds of ideas at university, in part due to the fact that they were always taught so abstract, without any implementation. I'm a very "hands on" kind of programmer - I only really understand something when I've built it myself. Unfortunately I'm not really aware of any great resources on graphs, I'm going to make some videos in the future, though 😁
That was an amazing explanation. First principals, constructivism, extremely well thought out visuals. Do I sound like a bot? Anyways, I feel like my mental image is a lot less murky.
Thanks a lot Nic for this wonderful video and explanations. Would it be possible to create a implementation follow up videos in future for this topic. It would really cement the concepts via your explanations and code walkthroughs.
Hey Nic, thanks for another great video. Like others have said, I enjoyed it even though nothing was really new for me, simply because of your super engaging style of presentation. Do you have this educational content planned out in advance, or do you make videos whenever you feel like you have enough content in your notes? If you’re taking suggestions, I think a lot of people would love an explanation of async/await in your unique style! Not sure if this is necessarily the level of abstraction you’re aiming for with this content though. Hope you’re doing well, and thanks for the good work!
I have a giant list of possible topics for videos, and generally week to week I just pick the one that feels the most interesting at the time 🙂 async / await is a great idea, I've added it to the list!
Very good presentation. I'd have liked to also see illustration of how the more complex structures deal with deletions without leaving unusable holes in the collision array.
Really enjoying the recent uploads. Found you via the data-oriented design video. What do you use to make your visualizations for the video? Pretty slick!
I've been doing OOP/FP for so long I forgot how to think in pointers. After watching this I think I'll go diagram a sentence so I can overanalyze how speech works for the next week.
Excellent explanations! I wonder if, in the future, hardware allows for 2D or 3D physical memory (sheets or cubes of transistors or whatever), what kinds of data structure variations or optimizations would that allow?
Small addition I'd make is that In searching for a free spot in the hash case or tree case and well everything that has a linked list pointer in it, those pointers can be used to create a linked stack covering all emelents at first. Allocation and freeing is then popping and pushing from/to the free space stack. See it as a second root element with tons of children 😉
A stream is not really one of the standard data structures. So, it can be different things in different contexts. Do you have a particular programming language in mind?
15:44 endIndex % capacity == 0 would just be a condition to see if the endIndex is a multiple of capacity (e.g. capacity * 0, capacity * 1, etc) if you just want the index wrapped, you remove the condition part: endIndex % capacity Also, it may be better to just describe the modulo operator by what it is, the remainder operator, and then explain the useful side effects from that.
man....the modulo thing in queues....was sweet! really clever management of the memory block. But I would imagine there is some simple logic to not allow adding to the queue if it's full and there are no free slots. I suppose you would have a case where you could dequeue faster than you queue items... Also linked list implementations usually aren't backed by an array/memory block....But using a linked list over an array is also a neat trick...like having a metadata layer. And you could also add an "real_idx" to this metadata layer and can access the the idx faster...give you have the node in question already and you aren't searching through the linked list. About the Tree...so when some node becomes a "parent" you store it in the "parents" array. But doesn't this create duplicates? Or that's the logic of packing all nodes into only 2 arrays?
This is a great video, one thing that bothers me about it is that you are baking in the implementations of data structures with the abstract data type a couple times, like with the hashmap which uses a second array containing linked lists. That may well be a common implementation of a hashmap but I don't think you should give the impression that it is the standard or only implementation. In reality underlying data structures are actually independent from abstract data types like hashmaps, queues, lists etc. 12:24 I have heard that undo/redo is sometimes represented as a tree, does anyone know why that is the case?
Don’t know much about data structures but the ‘freedom’ you get from adding another array reminds me of how some (all?) knots are trivially unknottable by adding another dimension. Does this also mean that since programs are stored in memory, that the operations performed on arrays are just arrays that transform other arrays?
Why don’t store both the next and the previous index in the linked list, tree or graph structures? Also, regarding the arrays capacity, is there any standard data structure that links arrays? Like if an array hits the maximum capacity then a new array is created and linked to the previous one, so when iterating over it, the structure will know to continue in the newly created array and so on
You can store the previous index too, in which case it's called a _doubly_ linked list. Same for the tree and graph, where you'd have doubly linked lists of edges in the second array. But it's a trade-off to make since it takes more memory per element to store that information. That being said I think this just wasn't mentioned for simplicity. You can totally create a linked list of chunks. Some arena allocators are actually implemented that way for example. It's useful because it lets you make a trade-off regarding the memory taken by a chunk compared to the memory taken by a link to the next chunk stored inside of it.
Why does your profile pic look like you are the best man on my sisters wedding but in your video you look like the friend who tells me all the time that he needs weed to medicate and that it’s the secret cure for a dozen diseases?
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
i would never date a structure but I appreciate the proposition thanks nic
that's structural bias!!
Woof woof 🦴🐕🐕
these are all structures i *thought* i was familiar with, but you have blown my mind!! when i implemented data structures for college assignments i just used the object oriented approach, never thought about how the memory was laid out. it took this video to realize how much that approach leans on the allocator. i dont think i will ever code the same, i mean that sincerely, thank you!
none of this is necessarily new info to me, but you have such a great and straightforward presentation style that i cant help but enjoy watching anyway. keep it up!
You should absolutely have more subs. Your graph/tree explanation just gave me an approach to solve a project of mine. I'm a hobby C++ learner and so this is absolutely amazing.
underrated channel, liked the video and subscribed
This is quickly becoming one of my favorite programming RUclips channels. Great job!
A-M-A-Z-I-N-G video on data structures, one of the best I've seen so far. Clear, simple and engaging. Kudos to you, Nic 💪
Absolutely top tier video. If I may add just one thing, it is how to deal with managing the linked list nodes in the "linked lists array". Specifically, how to find an empty slot to place a node after you've added and removed a bunch. Searching through the array is slow so you don't want to do that. The solution is to always have a special linked list stored there, a *free list*, which keeps track of the empty slots. At the start it covers the entire array, every index pointing to the next index. When you add a new linked list node, you remove the first node of the free list and store the node at that index. When you remove a linked list node, you add its index to the free list. This gives O(1) insertion and removal at the cost of an extra field: the start of the free list.
Great comment, I was very tempted to at least mention the free list implementation but it felt like it was getting into too much detail - I'm going to make a video both on linked lists and freelists at some point so will save it for then 🙂
Just discovered your channel yesterday, and this introduction, this has to be the most intuitive formation of the concept of data structures I have heard. Usually it's all just, "it will help you code better" and "it helps solve problems", with no context on why and how. I already knew a lot of the concepts, but still watched through the entire thing. Amazing reference video to share with my friends when they inevitably come asking me for help to explain it to them.
Recommended my Data Structures teacher this video to show to my other classmates, it's pretty good!
This channel is a goldmine.
The video quality is increasing day by day. Enjoyed this very much.
This completely changed my perspective! Its like the link between software and hardware for me was finally understood. Thank you!
Amazing! Thanks! You're very careful at explaining it in a realistic non-abstract way while also naming things and even showing some wizard tricks, what?! Best teacher! The kind that makes students like the topic more 😸
I have seen many videos on data structures and this is by far the best. Will be the number one source I will be recommending any other new programmers to gain a higher intuitive understanding of the concept. Please keep it up, this is fantastic.
You are seriously awesome! I can listen to you explain me things all day.
Keep up the good work, always interesting!
Your Video Typically its Enlightenment to my Brain's Cells. Thanks Man.
awesome! I had no idea you could represent a Graph with just 2 arrays, Also as soon as you mentioned Modulo for the queue I genuinely got chills. It's such an amazingly useful operator.
This is super well done! I still sometimes have a hard time visualizing the actual code implementation of Hash Maps and Graphs, but this at least makes it a bit easier to picture. Thanks!
the thing that helped me understand pointers, etc. is showing what ptr[offset] translates to in for example C.
It becomes this *(ptr + offset) and the compiler then also multiplies the offset by the size of the data type of the pointer.
This is why C alows this: offset[ptr] as it just is turned into *(offset + ptr) and the compiler still knows which value to multiply.
Oh yeah, that very thing that at first causes confusion
4[array]
That Circular Queue is so cool!
here from your C programming tips, keep it up!
Another excellent video Nic. The lesson for me here is that it really makes a huge difference to learn what's under the hood, how it all works. The concepts here really expose the underlying mechanisms in simple enough, practical terms to be easy to grasp and to be very helpful when I'm designing and coding. The basic principles are valuable on their own. Yet if I want to learn more about the algorithms and underlying code that these structures are built on, this video gives me excellent starting points.
I know the most of the info in the video. BUT I STILL WATCHING IT, THIS IS SO GOOD
These videos are so good!
I've always found graphs so fascinating, but I've never really delved deep into them.
Your explanation is always awesome. Really enjoyed the content, always explaining somewhat complex topics in easy to learn terms. Great work, thanks Nic.
I just failed my Data Structures course last trimester. I would have passed if my courses were this one single video: you've made things so clear.
Do you have any ressources for diving deeper in the implementation of graph data structures?
Thanks a lot !
Don't worry, you'll get it next time 💪
I personally struggled with these kinds of ideas at university, in part due to the fact that they were always taught so abstract, without any implementation. I'm a very "hands on" kind of programmer - I only really understand something when I've built it myself.
Unfortunately I'm not really aware of any great resources on graphs, I'm going to make some videos in the future, though 😁
This is one of the best videos I've ever seen! The way you keep arrays at the core of every data structure is crazy.
First time I see a stack based linked list implementation that uses array indexes instead of heap allocating each node, really interesting.
This is very helpful keep up the good work.
Another banger of a video
this is one of the best computer science channels i've ever seen! Invaluable stuff
That was an amazing explanation. First principals, constructivism, extremely well thought out visuals. Do I sound like a bot? Anyways, I feel like my mental image is a lot less murky.
Thanks a lot Nic for this wonderful video and explanations.
Would it be possible to create a implementation follow up videos in future for this topic. It would really cement the concepts via your explanations and code walkthroughs.
Amazing video, I would never though that everything is just an array
Hey Nic, thanks for another great video. Like others have said, I enjoyed it even though nothing was really new for me, simply because of your super engaging style of presentation.
Do you have this educational content planned out in advance, or do you make videos whenever you feel like you have enough content in your notes?
If you’re taking suggestions, I think a lot of people would love an explanation of async/await in your unique style! Not sure if this is necessarily the level of abstraction you’re aiming for with this content though.
Hope you’re doing well, and thanks for the good work!
I have a giant list of possible topics for videos, and generally week to week I just pick the one that feels the most interesting at the time 🙂
async / await is a great idea, I've added it to the list!
@@nicbarkeragain thanks for considering it! Looking forward to the next talk regardless of topic though.
Keep it up and don’t burn yourself out :)
Very good presentation. I'd have liked to also see illustration of how the more complex structures deal with deletions without leaving unusable holes in the collision array.
Another great explanation video. Keep up the great work Nic.
Fantastic video
cool video, I knew these but presenting them in terms of building on top of arrays definitely helps when conceptualizing usage of arena allocators
Brilliant video. Changed the way I think about my code.
what software do you use for making these beautiful presentations?
Nice video, thanks for sharing it.
Really enjoying the recent uploads. Found you via the data-oriented design video. What do you use to make your visualizations for the video? Pretty slick!
Late night upload? This is the kind of content I want to watch at 12:28 AM
This is so well-paced I am shocked
Amazing video. RUclips please make this viral
Great explanation, thanks.
First time I see the circular Queue, nice af
I've been doing OOP/FP for so long I forgot how to think in pointers. After watching this I think I'll go diagram a sentence so I can overanalyze how speech works for the next week.
Excellent explanations! I wonder if, in the future, hardware allows for 2D or 3D physical memory (sheets or cubes of transistors or whatever), what kinds of data structure variations or optimizations would that allow?
Small addition I'd make is that In searching for a free spot in the hash case or tree case and well everything that has a linked list pointer in it, those pointers can be used to create a linked stack covering all emelents at first. Allocation and freeing is then popping and pushing from/to the free space stack. See it as a second root element with tons of children 😉
Great explanation
Great work! Thanks!
Excellent work thanks can we have next video on multi threading programming.
Correction: dequeue pronounced as deck 👍🏼🤷🏻♂️ but excellent videos, you deserve a subscribe and a like 👍🏼👍🏼
Please explain streams
A stream is not really one of the standard data structures. So, it can be different things in different contexts. Do you have a particular programming language in mind?
I'm also looking for information about C++ streams now
To work with them more effectively
Hey do you use clay to make the ui in the video??
PowerPoint, I guess
12:17
the undo example is actually a tree if you think about it deeply
Bonus Content: Pointers, Explained Simply
👍Thanks!
15:44
endIndex % capacity == 0
would just be a condition to see if the endIndex is a multiple of capacity (e.g. capacity * 0, capacity * 1, etc)
if you just want the index wrapped, you remove the condition part:
endIndex % capacity
Also, it may be better to just describe the modulo operator by what it is, the remainder operator, and then explain the useful side effects from that.
Is it possible to implement a variable length circular queue?
I think this video does a good job justifying why all programmers at some point should learn C. Because at the end of the day, it's all arrays.
man....the modulo thing in queues....was sweet! really clever management of the memory block. But I would imagine there is some simple logic to not allow adding to the queue if it's full and there are no free slots. I suppose you would have a case where you could dequeue faster than you queue items...
Also linked list implementations usually aren't backed by an array/memory block....But using a linked list over an array is also a neat trick...like having a metadata layer. And you could also add an "real_idx" to this metadata layer and can access the the idx faster...give you have the node in question already and you aren't searching through the linked list.
About the Tree...so when some node becomes a "parent" you store it in the "parents" array. But doesn't this create duplicates? Or that's the logic of packing all nodes into only 2 arrays?
Just in time for my dreams
cool dude!
This is a great video, one thing that bothers me about it is that you are baking in the implementations of data structures with the abstract data type a couple times, like with the hashmap which uses a second array containing linked lists. That may well be a common implementation of a hashmap but I don't think you should give the impression that it is the standard or only implementation. In reality underlying data structures are actually independent from abstract data types like hashmaps, queues, lists etc.
12:24 I have heard that undo/redo is sometimes represented as a tree, does anyone know why that is the case?
Don’t know much about data structures but the ‘freedom’ you get from adding another array reminds me of how some (all?) knots are trivially unknottable by adding another dimension.
Does this also mean that since programs are stored in memory, that the operations performed on arrays are just arrays that transform other arrays?
Please please tell me you have a paid course somewhere
When is the layout algorithm video coming?
I'm estimating about 8-10 days from now depending on how deep the rabbit hole goes 🙂
Why don’t store both the next and the previous index in the linked list, tree or graph structures?
Also, regarding the arrays capacity, is there any standard data structure that links arrays? Like if an array hits the maximum capacity then a new array is created and linked to the previous one, so when iterating over it, the structure will know to continue in the newly created array and so on
You can store the previous index too, in which case it's called a _doubly_ linked list. Same for the tree and graph, where you'd have doubly linked lists of edges in the second array. But it's a trade-off to make since it takes more memory per element to store that information. That being said I think this just wasn't mentioned for simplicity.
You can totally create a linked list of chunks. Some arena allocators are actually implemented that way for example. It's useful because it lets you make a trade-off regarding the memory taken by a chunk compared to the memory taken by a link to the next chunk stored inside of it.
Upcoming video on pathfinding +
You're an array, and you're an array. Everyone is array!
hell yeah
please try to add time stamps on videos longer than 6-7 min
Please stop using white backgrounds in your videos.
south african accent?
Why does your profile pic look like you are the best man on my sisters wedding but in your video you look like the friend who tells me all the time that he needs weed to medicate and that it’s the secret cure for a dozen diseases?