Skip to main content
Loading Explore guides…
Memory & Arrays · Acedra
Home
Explore
Computer Science
Memory & Arrays
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
65 segments
Copy
Hide video
0:00
conceptually memory on a computer can be thought of as a large number of tiny boxes arranged in a line with each box holding some fundamental unit of data like a bite the boxes are all labeled with a sequential number called an address and the interface the computer provides you for working with this memory is extremely simple as long as you know the address of the Box you're looking for the computer can perform two operations writing data to an address and reading data from an address address
0:30
and if that sounds suspiciously familiar to you it's because in programming what I'm describing is called an array and in software terms that's all memory really is so despite the fact that they're usually very large and displayed in hexadecimal a memory address is just another way of describing an index into the array that is your memory in the end absolutely everything that runs on a computer is built on top of this array and as a result is built using the only
0:58
functionality that an array provides which is writing data to a particular index or reading data from a particular index now that can be a lot to wrap your head around if you've never really thought about things this way before so let's just start by building the simplest possible implementation of this concept of memory which would be an array with just one element in it say a single bite if we want to use our one bite of memory to store one bite of data for example a single English character
1:27
we don't have any choice at all about how to do it it just goes in the one box we have at index zero and that's it but as soon as we have two elements to work with now we have a choice if we want to store two characters there are now two different possible orders to store them in three bytes gives us six possible choices and of course with any simple pattern like this there's a mathematical formula to describe how many possible Arrangements there are given an array of
1:53
certain length which you might remember from school as a factorial as a result as the number of elements increase es the number of possible choices we have for the ordering of these elements increases astronomically and that gives us some insight into an interesting problem if I told you that I'd filled a million boxes with a million random English characters and I offered you an amazing prize if you could tell me if the letter Zed was anywhere in this million character set how would you go
2:22
about doing it well given that all we have to work with is our two operations of writing data to an index and reading data from an index X I think you'd quite quickly come to the conclusion that the only option we really have is starting in address zero and checking every single letter in order until you either find a zed or reach the end of the array in the case that there's no Zed at all it would be incredibly time consuming now imagine I asked you the same
2:48
question but I told you up front that the characters in the array were sorted in ascending alphabetical order figuring out if there's a zed in the array is now trivial all you have to do is look up the very last element by its index if the final character is a zed the answer to the question is yes otherwise it's no but now imagine I ask you to tell me the most frequent character that is the character that appears the most number of times chances are you'll end up
3:16
resorting to just searching through the entire array again if you try really hard you might come up with a solution that gives you a little bit of an edge on the naive approach of iterating through every item one by one but nothing compared to that light in fast just check the very last item in the array approach that we had for finding the Zed and of our 1 million factorial possible Arrangements of the data of course there's an arrangement that makes finding the most frequent character much
3:43
faster which funnily enough is arranging characters in order of their frequency putting the most frequent one at the start there are two foundational computer science Concepts here that I think are very important to understand the first is that because everything is built on an array of memory and all you can do with an array is read from and write to an index eventually every data access strategy and programming boils down to figuring out an array index the
4:12
second is that when it comes to figuring out that particular array index every different possible ordering of the elements in that array has different strengths and weaknesses that can be exploited and so to finally connect with this video's title I'm going to offer you a very simple definition a data structure structure is just a strategy for finding something in an array that's all it is like the two concepts all data structures have two halves the first is
4:40
the particular ordering of the elements in the underlying array the second half is the logic used to perform operations like finding a particular element inserting a new element or removing an element our initial example showcased one of the most common and most useful data structures which is a sorted array our character lookup example was extremely simple and we were able to sort our array based on the element data itself the character but in a real scenario you might be storing larger
5:09
composite objects like a user for example and sorting those larger elements based on some subfield like the user's ID it's also common to have arrays that aren't sorted by the data stored in the array at all for example if you need to look up your users by ID and also by name you might create two arrays of index indes into your actual user array where the indexes in one array are sorted by the user's name and the indexes in the other are sorted by the user's ID and notice that this data
5:40
structure is actually using multiple arrays underneath one to store the actual user objects which may or may not be sorted and one to store sorted indexes which are functionally just pointers to the user objects if you're not used to working with pointers this might seem a little bit confusing but you can imagine it just like books in a library each physical book itself can only be in one place at a time obviously but of course people want to find books by
6:07
title or by author or by genre so rather than duplicating the entire physical library and having three buildings with the same books in them one sorted by Title One sorted by author and one sorted by genre the library will have a computer system that allows you to look up a book by whatever criteria you want the book itself isn't stored in the computer it's stored in a stable location on a shelf and the various searches you can perform will return directions that tell you where to find
6:36
that book just like a pointer tells you where to find the actual data you're looking for I have other videos on specific data structures that go into a lot more depth and so in this video I'm just going to give you an overview of a few of the most common and useful data structures and specifically how they're all implemented underneath using arrays an array list is an ordered collection of elements and on the surface looks very similar to array it supports reading and writing to an arbitrary
7:02
index but adds a few very useful features on top the first is the ability to add a new element to the end of the list increasing the element count of the list by one which is different to arrays which have a fixed length but if arrays have a fixed length how can a list increase its number of elements if it's built over the top of an array well in order to be able to add a new element to the end of our list the array underneath our list actually has to be be larger
7:30
than the list itself the length of the backing array is usually referred to as the capacity and the number of items in a list is actually a separate piece of data often called the size or the count so when we call our array lists add function really what we're doing is we're using the List's internal count as an index for what boils down to a standard array right then increasing the count by one the second useful feature a list provides is the ability to remove
7:58
an element from some arbitrary position in the list which shifts any subsequent elements backwards by one to fill the hole this is much closer to how humans conceptualize a list of items but it's not how arrays work because arrays have a fixed length there's no way to individually remove one of the elements from the array because of course underneath that would correspond to removing the piece of physical memory that the index actually maps to so the best you can really do with a normal
8:27
array is set the data at that index to zero in order to provide the remove functionality that a list offers using array Primitives internally when we remove an element our list has to copy every single subsequent element in an array backwards by one to fill the ho which of course for very large arrays is extremely slow the mirror image of the remove functionality provided by the list is insert which can create a new element partway through a list shifting all subsequent elements forwards and of
8:58
course also result results in a copy that is a read and then a write of all of those elements this is such a good example of why understanding that everything is implemented over the top of an array is so important as a new programmer it's very easy to assume that if your programming language provides you with a construct like a list common operations like inserting and removing elements should have high performance because assumably the designers of the language are very smart and qualified
9:27
but it doesn't matter how smart you are if you're trying to fight the laws of physics every ordering of elements in an array has strengths and weaknesses and if you're leaning on the weaknesses the language designers can't help you but as with everything in programming the best choice depends on the actual data that you have and the patterns of access that you're expecting stacks and cues are data structures that can offer fantastic lookup iteration insertion and deletion
9:55
performance with one major caveat which is that you only ever insert or delete elements at the beginning or the end a stack data structure specifically limits any changes to the last element and the reason it's called a stack is because conceptually it's like a vertical stack of objects in the real world if you have a vertical stack of blocks you need to remove all the blocks on top before you can get to a block halfway down the only Block in the stack that is directly
10:23
accessible is the one on the very top a stack is functionally just a more constrained version of an array list and can be implemented in exactly the same way you have an underlying array with some fixed capacity and an internal variable that tracks the count of how many elements there are in the stack when using a stack we refer to the last element in the internal list as the top you can imagine a stack of blocks being represented on its side as array elements here adding an element Works in
10:53
exactly the same way as adding an element to a list we just write the data one pass the current last element and increase the count by one Stacks also provide the ability to remove elements from the list but just like our stack of blocks they only support removing the very last element and if you think about it removing the last element is actually a special case because by definition there are no elements after the last element that need to be copied to retain
11:19
our ordering so we can just reduce the count by one and we're done and in stack terminology this is referred to as popping the element off the top of the stack and it's just worth mentioning here that there's a symmetry in these fast list operations really ad is just a special case of insert at the end and pop for Stacks is just a special case of removing an element at the end because there's no elements after the end of a list there's no need to copy any subsequent elements to create space or
11:49
fill a hole as long as our data access pattern matches the natural characteristics of a stack that is we only ever add and remove elements from the end stacks provide amazing performance and simplicity and a great use case that's often used as an example for Stacks is keeping track of undoable changes in a text editor if we push all the users changes into a stack data structure when they press undo they expect only the most recent change to be reverted which maps to removing and
12:19
handling only the last element in the underlying array of changes if you're wondering about handling redo it's as simple as keeping a second stack of redoble Chang es if the user types a brand new change in we just empty the redo stack a q we can see as an extension of a stack and provides a single piece of additional functionality which is being able to also remove elements from the front of a queue not just the back like a stack cues just like cues in real life are used for
12:50
processing things in the order that they're added with an example being a web server processing incoming requests if we used a stack to process incoming web requests every new request that came in while we were busy would push the old requests deeper down and depending on how heavy the load is on the server the request at the very bottom of the stack might never get processed at all whereas using a queue would mean that responses go out in the same order that requests
13:19
came in giving us a much more reasonable median response time so how do we Implement a queue over the top of an array deleting elements at the end was quite straight forward but if we want to delete an element from the beginning of the queue surely that means we're going to have to copy all the elements backwards by one to fill the hole right there's a couple of really cool tricks here we can use firstly we just need one more variable in addition to our count
13:45
that tracks the index of the first item in the queue I've also just renamed the count in this case to end index to make it clear what's about to happen now obviously the start index starts off as zero so when we need to remove the first item what do we do well removing the item at the front of the queue is referred to as a DQ operation and all we do is just increase the start index by one and treat the array as if it starts from index one index zero doesn't exist
14:13
at all anymore it's a beautifully Simple Solution but you can probably see that as we process more and more items through our queue the start index will keep growing and we'll have more and more dead space at the beginning of our array and eventually we'll just overflow the capacity of our under lying array all together so how do we fix this problem well we can use the amazingly useful modulo operator I'll link you a comprehensive explanation of how mod works but in the case of our Q how we
14:41
actually use it is that whenever we want to access an element in our underlying array instead of directly using the index we mod the index by the capacity of the array first it might not be immediately obvious what this does but you can basically think of the mod operator as generating a repeating series of numbers across a range where each of the series has the number of elements that you mod by watch what happens when the end of the queue moves past the end of our underlying array as
15:10
the end index gets to the point where it would overflow when we insert a new element at the back of the queue the mod operator causes that index to wrap around to zero as we continue to add items to the back and remove items from the front of the queue the mod operation causes the entire queue to wrap around the corner like a game of snake allowing us to manage our queue inside a fixed size array without having to reallocate or resize or copy anything I just found
15:39
this so cool the first time someone taught it to me this is technically referred to as a circular Q rather than just a que but if I ever need a queue I always end up implementing them like this before we move on to a couple of the more advanced data structures we need to learn about one of the fundamental building blocks that they rely on which is the rather Infamous linked list rather than leaning on the natural ordering of the underlying array to keep elements in order a linked list
16:07
as the name suggests keeps elements in order by linking them together that might sound like magic but just like everything else it's built over the top of an array if we were storing user objects in a linked list a simple implementation would be wrapping each of those user objects in a struct or similar that as well as the user also includes the array index of the following ing user in the linked list so if I start with my linked list and my underlying array empty the first user I
16:35
add just goes into index zero in the array then let's say we want to add another user which I'll call user three don't worry it's for a good reason in addition to adding user 3 to the underlying array I set the next index field of user one to the index of user 3 essentially linking user one to user 3 this might seem pointlessly complicated until I try to insert a user in between user 1 and user 3 for an array list that would mean that I would have to copy any
17:05
elements after the target user forwards by one to make space but in a linked list I just add user two to the end of the underlying array and update the next index Fields so they correctly point from user one to user 2 to user 3 removing user 3 would be even more simple we just change the next index of user 2 to -1 to indicate that it's at the end of the list list so given that we don't have to do any of the expensive copying when we insert or remove an element in a linked list if we scale
17:36
this up to a million elements we should get great insert and deletion performance now right well not exactly you might have noticed that when we inserted user two it ended up in the third slot in the underlying array even though in our link list it's correctly second because linked lists don't rely on the natural ordering of the array they're built on top of it also means we lose the ability to easily access elements based on their index because the underlying array index is not
18:05
necessarily the same as their position in the linked list as a result if you have a linked list with a million items and you want to remove something at position 300,000 in a naive implementation you would have to start at the first element and follow the next index 300,000 times before you arrived at the element you're looking for so the trade-off we've made here is that we have great performance inserting and removing elements if we have a direct reference to the element before or after
18:34
the target but we've lost the ability to efficiently find the element at the nth position and in addition to this just iterating through elements of a link list in order is significantly slower than iterating through an array due to the somewhat random pattern of memory access having poor cache performance because of these particular quirks I find it quite rare to actually use a link list to store a normal collection of ordered elements but because of some properties that they have they make
19:01
fantastic building blocks to put other data structures on top of just like linked list themselves are built on top of arrays just a small note before we move on if you've done some programming before you might be a bit confused thinking well the link lists that I Implement don't use an array I just create the nodes using the new operator or maloc and they don't use indexes for the links they use pointers or references to each other and that's a totally valid point of confus Fusion
19:29
it's something I didn't understand properly for a long time either but given that the way that software interacts with memory at the lowest level is an array pointers are really just an index into memory when you use the new keyword or maloc or similar what you're doing is you're interacting with an internal data structure which is usually referred to as the Heap provided to you by the programming language or the standard library and of course what that data structure is built on top of
19:56
is an array of memory provided by EOS and in practice the data structure for Heap allocation has to be extremely generic in order to handle any possible workload and as a result if you allocate your link list nodes using new or similar you're likely to get worse performance than if you were managing it inside an array yourself and using indexes now I know I promised you some more advanced data structures so let's crack on next up we have the hashmap hashmaps are also sometimes referred to
20:25
as dictionaries and they're incredibly common and useful data structures instead of using a numerical index to look up data a hashmap uses some other kind of data like a string which we call the key in this case we're looking up the prices of flowers using their name as the string key and of course because you know that hashmap has to be built using an array you can probably guess there must be some way of transforming arbitrary data like a string into an array index and indeed there is it's
20:54
called a hash function and it's where hashmaps get their name calling a hash function function with a string key will give you back a number that's reasonably evenly spread across a large range like the maximum of a 32 or 64 bit integer and because that number is too large to feasibly use as our array index directly we can use the same modular approach that we used for our circular q and just mod the array index by the length of our internal array this Maps the output of
21:21
our hash function into a repeating range of 0 to the length of the array minus one which means we've converted string into a valid index in our internal backing array which solves our original requirements that we had but what happens if our approach returns us the same index for two different strings that's called a collision and there's a couple of ways to handle it the first approach remains resolutely committed to using a single array to store the data if there's a collision we just iterate
21:51
forwards through the array until we find an empty slot and then read or write the data there of course this means that after we've converted ConEd our string into an index we can't just assume that the resulting array holds the data that we want we need to store some identifying info like the flower name in each hashmap item so that we can compare to see if it's actually the item we want and if not start iterating through the array and comparing until we find the
22:16
data that we're looking for or an empty slot indicating that the key we're looking for doesn't exist in the array at all this approach has some downsides with the main one being that it Trends towards creating long consec itive runs of stored elements called clusters which means that you might need to iterate for a long time until you find an empty slot an alternative approach of using just one array to store your hashmap is using two arrays and the great thing about
22:42
this is it will allow me to demonstrate one of the really cool characteristics of a linked list that's not very well known so in this approach instead of storing all the items in one array directly with all the collisions stored consecutively we use two arrays we store the first item for a particular hash in the first array and to handle any collisions we give each item an index of the next Collision forming a linked list all the colliding elements are then stored in the second array and linked
23:10
together looking up items with this approach is very similar to the one array approach except now we're following a linked list instead of iterating forwards through an array and you may or may not have noticed but the cool link list trick I mentioned earlier is already visible one of the most amazing natural properties of linked list is that because the underlying array items don't need to be consecutive it means that we can store multiple separate linked lists of the same type
23:37
in the same array each of our hashmap collisions results in a new linked list being created and it doesn't matter at all that all those lists are interleaved in this second array because we're following links not iterating through array indexes if you wanted to store collisions in Array lists instead of linked lists you would need to allocate a separate array list for every Collision bucket which would end up being a tremendous number of allocations and even then you can't really predict
24:04
ahead of time how the collisions are going to be spread across buckets which further complicates capacity planning you'd probably need to make those arrays resizable so that's an awesome natural property of a link list you can store multiple link lists of the same type in a single array even if you don't know ahead of time how the total capacity is going to be spread out between those link lists in all the data structures we've discussed so far the only relationship between elements has been
24:30
the order in which they appear in the array a link between two elements in a linked list doesn't imply that there's any particular relationship between those two elements just that one appears after the other but there are some cases in which tracking relationships between elements is incredibly useful if you're building a user interface you intuitively understand that there's a relationship between the elements in the interface rather than every element being positioned relative to the screen
24:58
UI elements can be positioned relative to each other to their container or parent element so that when the parent moves all the children implicitly move too in a single update instead of having to set the position of every internal element manually this type of structure when visualized looks like this and the name we generally give to this type of data structure is a tree each of the elements in a tree is called a node and the relationships between nodes only go
25:27
in One Direction from top to bottom we refer to the node at the top of a relationship as the parent and the node at the bottom as a child each child has only one parent but each parent can have multiple children so how is a tree built over the top of an array in much the same way as our hashmap implementation we can easily build a tree over just two arrays by using linked lists if you think about it a tree is actually very similar to a linked list except instead
25:57
of each element poting to just a single next linked element in a tree each node can point to multiple different nodes after it which we call the children and if we can build something using a linked list that means we can build it using an array we can start to implement our tree by placing all the nodes of our tree into the first array each node has a child index which points into our second array which stores the relationships between the nodes each relationship is
26:25
just a simple object containing the index so of the child node in the first array and the index of the next linked list item in the second array that is the next child so if we wanted to Traverse downwards through our tree to the icon of the first menu item in the list that little new document icon what we're going to do is get the first child of the dropdown which is the menu item and then the second child of that which is the icon so in terms of our underlying tree operations we would
26:55
start at the root and follow the child indexing into the second array because this is the first child we'll follow the node index back to the first array and we've got our first menu item we then follow the child index to the first child of our menu item which is the new text and instead of going to the node we follow the next child index to get to the second child of the menu item which is the icon and then follow the node index back up into the first array this
27:23
is just one of many different ways you can Implement a tree using arrays there are approaches that can pack the tree into a single array and there are approaches that will give you better performance with larger trees if you know the details of the data you're planning to store and the way you're planning to access it and now a tree data structure in academic terms is actually a constrained version of a more generic data structure called a graph if we take a look at our tree remember how
27:49
I mentioned one of the constraints of a tree is that the relationships are asymmetrical a parent can have multiple children but a child can only have one one parent well if we relax that constraint and allow a child to have multiple parents we now have what's called a graph the easiest way to think of a graph is in terms of starting with our linked list and progressively removing the constraints a linked list only allows us to have a single link from the previous element and to the
28:18
next element a tree relaxes that constraint by allowing us to have multiple links to next elements creating the parent and children relationship and a graph takes it further by allowing us to have multiple links from previous elements as well and in graph terminology specifically those links are referred to as edges the nodes are sometimes referred to as vertices or vertexes but that's a little bit less common I tend to just call them nodes likely the most well-known use of graphs
28:48
these days is something called AAR which is a pathf finding algorithm that is it finds the shortest path between two points and it's used in an enormous number of video games for calculating the best route for a character to travel from their current location to a Target location graphs have been a topic of very focused academic research for a long time and I'm not going to go into too much detail here but in the spirit of the video let's have a look at how
29:14
graphs are implemented using arrays well as it turns out I don't even need to because the implementation is exactly the same as the one I gave you for the tree you store the nodes in your first array and the edges in your second array and each node just stores the index of the first Edge in a linked list of edges the difference in this case is in the operations not in the data Arrangement there are some specialized types of graphs that require a slightly different
29:40
implementation but in the vast majority of cases you can get away with just two arrays underneath the one notable difference is that if you want to Traverse in any direction through the graph rather than just from parent to child like you do in a tree you'll need to store a duplicate of the vertex so it's except accessible in both directions from both nodes I hope this has given you a nice overview and helped you build some base intuition for what a data structure actually is and if a lot
30:07
of this felt very new to you I have one final piece of advice which is to start simple the next time you're approaching a novel programming problem try building it using just an array see how far you can push it you really will be surprised at how much you can achieve with just a single array and who knows by doing that you might come up with a novel structure that fits your data and your situation perfectly enjoy
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat