Data Structures Summary

Key Takeaways

[Music] so in cs50 we've covered a lot of different data structures right we've seen arrays and Link lists and hash tables and tries stacks and cues um we'll also learn a little bit about trees and heaps but really these all this end up being variations on a theme there really are these kind of four basic ideas that sort of everything else can boil down to arrays link lists hash tables and tries and like I said there are variations on them um but this is pretty much going to summarize everything we're going to talk about in this class in terms of C but how do these all measure up right we've talked about the pros and cons of each sort of in separate videos on them but there's a lot of numbers getting thrown around there's a lot of General thoughts getting thrown around let's try and consolidate it into just one place let's weigh the pros against the cons and consider which data structure might be the right data structure for your particular situation whatever kind of dat you're storing um you don't necessarily always need to use the super fast insertion deletion and look up of a try if you really don't care about inserting and deleting too much if you need to just quickly Random Access maybe an array is better so let's let's distill that right let's talk about each of the four major kinds of data structures that we've talked about um and just see when they might be good and when they might not be so good so we'll start with arrays so insertion that's kind of bad uh insertion at the end of an array is okay um if we're building array as we go but if we need to insert elements into the middle think back to insertion sort there's a lot of Shifting to fit an element in there and so if we're going to insert anywhere but the end of an array um that's probably not so great similarly deletion unless we're deleting from the end of an array is probably also not so great uh if we don't want to leave empty gaps which usually we don't we want to remove an element and then sort of make it snug again and so deleting elements from an array also not so great lookup though is great we have Random Access constant time lookup we just say seven and we go to array location 7 we say 20 we go to array location 20 we don't have to iterate across that's pretty good arrays are also relatively easy to sort and we've every time we talked about a sorting algorithm such as selection sort insertion sort bubble sort merge sort we always used arrays to do it because arrays are pretty easy to sort relative to the data structures we've seen so far the RS are relatively small there's not a lot of extra space you just set aside exactly as much as you need to hold your data and that's pretty much it so they're pretty small and efficient in that way but the another downside though is that they are fixed in size we have to declare exactly how big we want our array to be we only get one shot at it we can't grow and shrink it if we need to grow or Shrink it we need to declare an entirely new array copy all of the elements of the first array into the second array and if we miscalculated that time we need to do it again not so great um so arrays don't give us the flexibility to have variable numbers of elements with a linked list insertion is pretty easy right we just tack on to the front deletion is also pretty easy we have to find the elements that involves some searching but once You' found the element you're looking for all you need to do is change a pointer possibly two if you have a linked list a doubly linked list rather uh and then you can just free the node you don't have to shift everything around you just change two pointers um so that's pretty quick look up is bad though right in order for us to find an element in a link list whether singly or doubly linked we have to linear search it we have to start at the beginning and move to the end or start at the end and move to the beginning um we don't have Random Access anymore so if we're doing a lot of searching maybe a link list isn't quite so good for us they're also really difficult to sort right um unless you're the only way you can really sort a link list is to sort it as you construct it but if you sort it as you construct it you're no longer making quick insertions anymore you're not just tacking things onto the front you have to find the right spot to put it and then your insertion becomes just about as bad as inserting into an array so link lists are not so great for sorting data they're also pretty small sizewise um doubly link lists slightly larger than singly link lists which are slightly larger than arrays but it's not a huge amount of wasted space um so if space is at a premium but not you know a really intense premium um this is might be the right way to go hash tables insertion into a hash table is fairly straightforward it's a two-step process first we need to run our data through a hash function to get a hash code and then we insert uh the element into the hash table um at that hash code location deletion similar to link list is easy Once you find the element uh you have to find it first but then when you delete it you just need to exchange a couple of pointers if you're using separate chaining um if you're using probing or you're not uh if you're not using chaining at all in your hash table deletion is actually really easy all you need to do is Hash the um hash the data and then go to that location and assuming you don't have any collisions you'll be able to delete delete very quickly now lookup is where things get a little more complicated right so it's on average better than link lists if you're using chaining you still have a linked list which means you still have the search detriment of a linked list but because you're taking your linked list and splitting it over a 100 or a thousand or n elements in your hash table your link lists are all one one nth the size right they're all sub substantially smaller you have n link lists instead of one link list of size n um and so this real world constant factor which we generally don't talk about in time complexity it does actually make a difference here so lookup is still linear search if you're using chaining but the length of the list you're searching through is very very short by comparison again if sorting is kind of your goal here hash table is probably not the right way to go just use an array if sorting is really important to you and they can sort of run the gamut of size it's hard to say whether hash table is small or big because it really depends on how large your hash table is if you're only going to be storing five elements in your hash table you're probably and you have a hash table with 10,000 elements in it you're probably wasting a lot of space contrast being you can also have very compact hash tables but the smaller your hash table gets the longer each of those linked list gets and so there's really no way to define exactly the size of a hash table but I it's probably safe to say it's generally going to be bigger than a link list of storing the same data but smaller than a try and tri are sort of the the fourth of these structures that we've been talking about inserting into a try is complex there's a lot of dynamic memory allocation especially at the beginning as you're starting to build but it's constant time the it's only the human sort of element here that makes it tricky having to encounter a n pointer maloc space go there possibly maloc space from there again this sort of intimidation factor of pointers in dynamic memory allocation is the hurdle to clear but once you've cleared it insertion actually becomes quite simple um and it certainly is constant time deletion is easy all you need to do is navigate down a couple of pointers and free the node um so that's pretty good lookup is also pretty fast it's only based on the length of your data so if your all of your data is five character strings for example you're throwing five character strings in your try it only takes five steps to find what you're looking for five is just a constant Factor so again insertion deletion and look up here all constant time effectively another thing is that your try is actually kind of already sorted right by virtue of how we're inserting Elements by going letter by letter of the key or digit by digit of the key typically um your your TR ends up being kind of sorted as you build it doesn't really make sense to think about sorting in the same way that we think about it with arrays or linked lists or hash tables but in some sense your try is sorted as you go the downside of course is that this a try rapidly becomes huge from every Junction Point uh you might have if your if your key consists of digits you have 10 other places you can go which means that every node contains information about the data you want to store at that node plus 10 pointers which on CS5 IDE is 80 bytes so it's at least 80 bytes for every node that you create and that's not even counting data and if your if your nodes are letters instead of um digits now you have 26 pointers from every location and 26 * 8 is probably 200 bytes or something like that and if you have capital and lowercase you can see where I'm going with this right your nodes can get really big and so the try itself overall can get really big too so if spaces at a high premium on your system a try might not be the right way to go even though it's other benefits come into play I'm Doug Lloyd this is cs50