#Data #Structures #Computer #Science #Beginners
Hello, everyone, and welcome to an introduction to data structures. My name is Steven, and over the next three hours, we’ll be tackling the topic of data structures in relation to computer science. More specifically, we’ll be talking about what they are going over some different
Types of data structures, and discussing how we can use each of them effectively with examples. This course will be a general overview of data structures, and so we won’t be confining ourselves to one specific programming language. However, this series will require you to have a
Basic understanding of programming. If you are completely new to computer science, I would recommend our introduction to programming series, which will be linked in the description below. That video will give you all the information you need to traverse these topics comfortably.
Now, we’re almost ready to hop into things. However, there are a few housekeeping items that I want to go over beforehand for those wishing to enhance their learning experience. If you’re not interested in that and want to skip right to the content, go to the time shown on your
Screen now. For those of you staying though there are just a few things I would like to mention. Firstly, in the description, you will find timestamps for each major topic covered in this video, as well as timestamps taking you to every smaller section contained within those topics.
So please feel free to skip around if you’re already comfortable with one topic or only interested in a certain data structure. Next, we’ve decided to include the script and visuals used for the series also in the description below. That way you can
Follow along if you like or simply read the script if my soothing voice isn’t your style. Additionally, for each segment, I’ll be including the references and research materials used to write the script for each topic. That way, if you ever feel as if I haven’t explained a topic
Well enough, or we’re just simply like more information about a certain topic, you’ll have a readily made list of articles and websites, which you can use to supplement this series. If you feel like you have any questions throughout the series about maybe something I said or a
Certain visual, please ask your questions in the comments below. I’ll try to be as responsive as possible for the first few weeks on questions you guys may have about the series and such. And finally, in terms of housekeeping, I just like to say if you’re not already subscribed to
Our channel, no pointer exception, then consider doing so if you enjoy this type of content. as me and my co host Sean regularly post videos in this style. We’re trying to hit 1000 subscribers before the fall semester of college begins. So check us out if you end up enjoying the video. With
My shameless plug out of the way, we’re finally ready to tackle the topic of data structures. In this introduction segment, we’ll simply cover a general overview of what data structures are, and then go over what type of information will be covered throughout the duration of the series.
So the obvious question to start with is what exactly is a data structure? Well, in computer science, a data structure is a way to store, organize and manage information or data in a way that allows you the programmer to easily access or modify the values within them.
Essentially, it’s a way for us to store a set of related information that we can use for our programs. data structures, and the algorithms used to interact, modify, and search through them provide the backbone for many of the programs that you’ll end up writing,
I can almost guarantee that in 99% of your programs data structure will be involved. Each of the data structures that I’ll be talking about are designed for the sole purpose of storing information and allowing the end user to access and manipulate that information
In an efficient, effective way. But each one differs in the manner that they accomplish this. If you have a basic understanding of programming, you probably know about a few different data structures already, such as the array and the array list, also known as the list in Python.
But if you’re going to be pursuing a career in computer science, just knowing these two is definitely not going to cut it. Well basic data structures such as the array are used frequently by companies throughout their code. More advanced data structures are being put
To use all around you the Undo redo button in Google Docs, Google Maps on your phone, even the autocomplete feature through your text messages all require the use of more advanced data structures, which makes them extremely useful to learn and comprehend.
Okay, now, I can’t see you per se, but I can just tell that you’re jumping up and down in your seat hooked on data structures and how useful they can be. But before we jump too far into things, let’s discuss the information that we’ll be covering in this series. Now, before we talk
About any specific data structures, we’re going to have a brief talk about efficiency. We’ll discuss the metrics used to judge the speed and efficiency of different data structures, which will then give you a better understanding of why one data structure might be used over another one.
From there, we’ll start by diving headfirst into what I believe are the basic data structures, those being array. An array lists. While you may already have a good understanding of what these are, I would highly suggest that you still watch these segments, because we’ll be going into a
Little bit more depth as to why they’re so useful based on differences in how they’re stored in the computer’s memory. After that, we’ll move on to what I’ll call the intermediate data structures. These are a little bit more complicated than the basics and have a few special attributes which
Make them stand out from the rest. We’ll begin by taking a look at stacks which are the backbone for all recursive processes in your computer. Then we’ll look at the antithesis of a stack the queue. Moving on from there, we’ll be covering linked lists and their evolved form in the
Doubly linked list. Before moving on to the final of our intermediate data structures, the dictionary which includes a mini lesson on hash tables. Then we’ll wrap up the series talking about trees and tree based data structures, less linear and more abstract data structures beginning with the tree itself. We’ll then move
On to tries a very useful data structure used for a lot of word processing algorithms. And finally end off the series with a discussion on heaps and graphs. So in total, I’ll be taking you through four different segments containing 12 of the most common data structures that are practically used,
As well as providing examples of where and when to use them. section one on efficiency, section two on basic data structures, section three on intermediate data structures, and wrapping it up with section four on tree based data structures. With this knowledge, you’ll be able to take charge
Of your programming career and hopefully gain a competitive edge by implementing them when needed. Like I said, however, before we jump straight into the different ways to store information, I’d like to have a quick discussion on how we score the efficiency of these data structures
Using what is known as Big O notation. So let’s jump right in. Okay, so before we talk about all these crazy data structures, like maps, and heaps, we want a quantifiable way to measure how efficient a certain data structure is at the different tasks,
We might ask a bit. If we’re going to be storing extremely large amounts of data, being able to search through, modify, or access the information within a data structure needs to be fast and efficient. As we briefly mentioned before, the industry standard for this kind of
Implementation is big O notation. So what exactly is big O notation? And how do we measure it for a specific data structure? Well, that’s what we’ll be covering in this segment. For most of the basic and intermediate data structures in this series, we’re going to be spending some time talking about
Its efficiency using big O notation. So this is definitely a topic you’re not going to want to skip. With that being said, let’s begin. So because there are so many different ways to store information, like we talked about in the previous segment, programmers have developed this idea
Of big O notation as a way to basically score a data structure based on a few different criteria. This criteria can change based on who you ask, but for the purposes of this video, we will be using four criteria representing the most common functions you might want from
A data structure. The ability to access a specific element within the data structure, search for a particular element within the data structure, insert an element into the data structure and remove an element from the data structure. Now by measuring how efficiently a certain data structure can do these four things,
We can basically create a report card of sorts, which measures how efficient a certain data structure is. At a glance, this gives us a pretty good overview of what a certain data structure is good at, and what it is bad at. And it can help us decide which one to use.
If we need to store data that is easily accessible to the end user. For example, we might choose a data structure which can access elements the quickest, and vice versa, if accessing elements isn’t the most important thing to us, but we need a data structure which can be easily added
To and deleted from, we would go for one which is most efficient and that specific functionality. By looking at a data structures report card, if you will, we can get a quick sneak peek at what they’re good at and what they’re bad at.
Now, if we use big O notation to basically create a report card, like I said, there must be some way to actually grade each of these functions. And there is the four criteria mentioned, accessing searching, inserting and deleting are all scored using big O notation time complexity equations.
Now what is the big O notation time complexity equation? Well, I’m glad you asked. Besides being in an annoyingly long phrase, a big O notation, time complexity equation, or just time complexity equations, work by inserting the size of the data set as an integer n and returning the number of
Operations that need to be done. indicated by the computer before the function can finish. The integer n is simply the size or amount of elements contained within the data set. So for example, if we have an array, one of the data structures we’ll get into soon, with the size of 10,
We would place 10 into the different efficiency equations for accessing searching, inserting and deleting that represent the array, and returned back to us would be the number of operations that need to be conducted by the computer. Before completion of that function. It does get a little
Bit more complicated than this. But for the sake of keeping this series simple, all you need to know is that these equations help represent efficiency amongst different data structures. Also, an important thing to note here is that we always use the worst case scenario when judging
These data structures. This is because we always want to prepare for the worst and know which data structures are going to be able to perform under the worst conditions. You’ll see what this means in greater detail a little later on once we start putting this into practice. But for now,
Just keep in mind that when judging data structures, we always use the worst case scenario. Moving on, the reason that it’s called Big O notation is because the syntax for these particular equations includes a big O, and then a set of parentheses.
Inside these parentheses will include some function, which will correctly return the number of operations needed to be run by the computer. So for example, let’s say we have a fake function, it can really be anything, the purpose in this case is irrelevant. Now for this fake function,
Let’s say it’s time complexity equation was the one shown on your screen now, we would pronounce this time complexity equation as o of two, meaning it takes two operations from the computer before our make believe function can finish. If the time complexity
Equation was o with a five in the parentheses, instead, it would be o of five, and so on. Now, these are examples of time complexity equations, which run in constant time, meaning no matter the size of our data set, it will always take the same number of instructions to run.
This is usually not going to be the case though, when it comes to the four criteria we want to mention for our data structures. Most of the time are integer n, which again contains the amount of elements within the data set is going to have some adverse effect on how many operations
It takes to say search through our data structure, which makes sense, a larger data set means it’s going to take more operations from the computer to search through that entire data set. Now we score these four functionalities in number of operations performed, because measuring by how
Long the function takes to run would be silly. If we measured by a metrics such as time taken to completion, our results would be highly biased by the hardware used to run the function. a supercomputer used by Google is obviously going to be able to search through a data structure much
Faster than a laptop. time complexity equations essentially level the playing field by instead returning the number of operations to eliminate the bias in processing power that exists. So to sum up everything that we’ve learned so far, we measure the efficiency or speed of a data structure based on how well it can
Perform four basic tasks accessing, searching for inserting and deleting elements within itself. Each of these criteria is modeled by an equation which takes in the size of the data structure in number of elements and, and returns back the number of operations needed to be performed by
The computer to complete that task. By measuring these four metrics, we can get a pretty good understanding of what the data structure is good at, and what the data structure is bad. Now, it’s important to note that this isn’t the end all be all for deciding on which data
Structure to use in your program. As you’ll see, as this video progresses, many of the data structures were structured with specific quirks or features, which separate them from the rest and provide additional functionality. Big O notation is incredibly useful, and something
That you should definitely take into consideration when determining which data structure to implement into your program, but it should not be the only thing that you use. Cool. Now that we know a little bit about how we measure the efficiency of a data structure using time complexity equations,
Along with the four criteria actually used to measure them. Let’s dive straight into what the actual equations mean in terms of efficiency. That way, when we start grading data structures, you’ll have a good idea as to how good or bad each one is at that particular metric.
Basically, we’re going to cover the six most common time complexity equations from most efficient to least efficient. Now, the absolute best that a data structure can score on each criteria is a time complexity equation of o of one. This essentially means that no
Matter what the size of your data set is, the task will be completed in a single step. If your data set has one element, that computer will finish the task in one step. If your data set has 100 elements, one step 1 million elements one step 800 quadrillion
Elements, it does not matter, the computer will finish the task in a single step. This is why when we look at the graph of volume of data versus instructions required for o of one, the line remains constant at one. No matter the volume of data stored within the data structure,
That computer can complete that task in a single instruction. Whether it be accessing searching, inserting, or deleting, O of one is the gold standard absolute best top of its class time complexity equation. It is basically the Michael Jordan of big O notation when it comes to time complexity equations. Now the next fastest
Type of time complexity equation is O log n. While not as fast as instantaneous time, a function having a time complexity of o log n will still provide you with very fast completion. Now if you don’t fully understand logarithms entirely, just know that this efficiency is
Slower than instantaneous time of one and faster than the next level of efficiency known as O of n. Additionally, because the volume of data versus time graph follows a logarithmic curve, the larger the data set that you use, the more bang for your buck that you’re going to get.
Basically, as the amount of data you try to perform one of our four criteria on increases the rate of change of the amount of operations it takes to complete that certain task decreases. So as you can see, at the beginning of the graph here, when we increase the volume of data,
Our number of operations skyrockets. But when we do the same for larger and larger sets of data, our number of operations increases much more slowly than before. A good example of a non data structures related function, which has a time complexity of o
Log n is the binary search. If you know what a binary search is, then you’ll understand how it is that when the data set gets larger, the number of instructions needed to find the item you’re searching for, doesn’t increase at the same rate. If you don’t know what a
Binary searches, but would like to know, in order to better understand Oh login. A link in the description below will take you to that point in our introduction to programming series where you can learn about it. If not, let’s move on to the next equation.
O of n is the next common time complexity equation that’s going to come up frequently during this lecture. The graph of volume of data versus instructions needed for this function is linear, meaning that for every element you add to the data set, the amount of instructions needed to
Complete that function will increase by the same amount. So to perform a function with the time complexity of O of n on a data set with 10 elements, it will take 10 instructions 50 elements will take 50 instructions, 1000 elements, 1000 instructions, and so on O of n
Is really the last good time complexity equation that exists. Anything above this is considered inefficient and not very practical when it comes to data structures in computer science. The next type of equation that will come up is o n
Log n. This equation is the first that is relatively bad in terms of efficiency. The graph of volume versus operations shows a somewhat linear but increasing graph meaning unlike o log n, it won’t be better in terms of efficiency as the size of the data set increases.
Instead, the slope actually increases as the volume of data does. The last two types of equation are o n squared and o two to the N. These are both incredibly inefficient equations, which should be avoided if at all possible.
Because they’re both exponential in structure, which can be seen from their graphs of volume versus operations. The larger the data set that you use, the more inefficient it will become. While there are more time complexity equations that exist such as o n factorial, which is even
Worse than the two I just mentioned, the data structures we’ll be talking about, we’ll never have time complexity equations that exists outside of the five we’ve just covered. So we’re going to stop there. Now the final thing I want to say is just a reiteration of something I said before,
These time complexity equations are not the only metric you should be using to gauge which data structure to use. As we get deeper and deeper into this series, you’ll see that we might have some data structures which don’t seem that efficient at all based on their time complexity equations
For provide some other functionality or feature, which makes them extremely useful for programmers. Okay, now that we have some knowledge on how we actually grade these data structures in terms of efficiency, let’s hop into our very first data structure. The first data structure we’re going to be covering is the array.
Now I understand the array is a pretty common data structure taught in most programming classes, and that many of you might already know about the properties and uses of an array. But in this segment, we’ll be going into more detail on the array as a data structure,
Including its time complexity equations, storage methods, and more. So check the description for a timestamp to skip ahead to that section. If you already know the basics. If you’re not as versed in the array, though, or just want a general review,
Then stick around, because right now we’ll be discussing the basics of an array. An array is fundamentally a list of similar values grouped together in a central location, which makes sense because if you remember, we use data structures to store sets of similar information, so that we can easily use that information.
Basically, arrays can be used to store anything, usernames for an app, high scores for video game prices for an online shop, pretty much any list of values which are fundamentally similar meaning of the same type. So integers, strings, floats, objects, the list goes on and on.
Any primitive or advanced data type you can think of can be stored within an array. Every item contained within the array is referred to as an element of that array. And we call the collective total of elements, the array, this is going to be true for almost
All data structures we talked about, by the way, so just keep that in mind. An array will also have three attributes associated with it, the first being a name for the array, the second a type for the array, and the third a size for the array. Let’s start with the name.
The name, if you couldn’t tell is just simply a name for the array, which can be used to reference and interact with it. Say for example, we had an array called names, which contains the list of company employees. And then we also had an array called salaries which contained a list of
Salaries for those employees. If we wanted to search through the list of salaries, we would do so by referencing the salaries array with its name. This way the computer knows that you want to search through that specific array containing salaries, and not the names arraigns that
This works vice versa as well, of course, if we wanted to search through the names array instead. Now another thing to note really quickly, while we have this up is that these two arrays are also an example of parallel arrays. Parallel arrays are two or more arrays containing the same number
Of elements and have the property wherein each element in one array is related to the element in the other array, or arrays have the same position. So from our example, we can say that the first element in our names array, john smith, corresponds to the first element in the
Salary array, the integer 10,000. This would mean that john smith has a salary of 10,000. This is really good, because as you’ll see, later on, we can’t store different types of variables in the same array. So we couldn’t have the salary integers be stored in the same place as the name
Strings, making parallel arrays extremely useful for storing different types of data about the same entity. Alright, tangent over, let’s get back to the attributes of arrays. And the second one, we’ll be talking about the arrays type. Now an arrays type is simply what type of information is
Stored or will be stored within that array. One of the biggest stipulations about arrays is that it has to hold all the same type of information. So you cannot have an array containing integers and strings, it would have to be either an array of only integers or only strings. This works for any
Type of information you would want to store within the array, meaning every element or spot within the array must be of the same type. The third and final attribute that an array has is a size. This size is a set integer that is fixed upon the creation of the array.
It represents the total amount of elements that are able to be stored within the array. An array size cannot be changed. I’ll repeat that again because it’s extremely important and array size cannot be changed once created. Once you write the line of code which instantiates
An array You give it a defined size or fill it with elements until it has a defined size. And then at that point, the array size cannot be changed by conventional methods. This is actually pretty rare for a data structure. And it may seem really counterintuitive and useless. But later on
When we talk about an arrays efficiency, you’ll see that this is for a specific reason, and not just to be annoying to the programmer. So there you have it, the three attributes of an array,
A name to reference it a type to fill it with an A size to control it. Let’s now shift focus and talk about how we actually define an array ourselves how we reference and change values within an array, and then dive into the idea of two dimensional arrays.
There are actually two different ways to instantiate an array in most languages, you can either populate the array with elements that you want contained within it right then and there. Or you can set a specific size for the array, and then slowly populate it later on
As the program runs. We’ll be discussing how to do both, starting with the first creating the array with the elements already stored. Now defining and filling an array as soon as you create it is mainly used for when you already know which values are going to be held within it.
For example, let’s say you’re creating an array, which is going to hold the salary of 10 different workers at a company. And that information is being read in from a text file. Well, you already know the 10 salaries for those workers from the text file,
And so you’re able to immediately populate the array when you create it. This way, you’ll already have the information available to you as the program runs. The way you do this varies amongst different programming languages. But it’s shown here in three different languages, Java, Python,
And C sharp. To give you a basic gist of how this is accomplished. All three lines of code on your screen now will create an integer array of size three, containing the numbers one, two, and three. You can see that all of them involve the declaration of an array name,
Which is then set equal to the values you want to include within the array encapsulated by some sort of brackets or braces. This isn’t 100% how it’s going to be for all languages, but for the
Most part, it will follow this skeletal outline. As you can see, Java and C sharp require you to define the array type, whereas Python does not. But for the most part, the syntax is the same. Again, that is name of array set equal to list of comma separated values encapsulated by brackets or
Braces. This also develops the size of the array for you automatically. So since we populate the array with the numbers, one, two, and three, the array would instinctively have a size of three, as it now contains three integers. If we were to say go back and add in a fourth number, where we
Define the array, the size would dynamically increase to for the next time we run the code. Now the second way in which we can instantiate an array is by setting an initial size for our array, but not filling it with any elements and then slowly populating it as the program runs.
This would be used in the case that you don’t actually know what information you’re going to store in the array, but will as the program runs through. The most common case in which this happens is in the case where the end user will enter
Information into the program. And then that information will be stored inside the array. Since the information varies based on which user runs the code and what they input during that particular run, we have no way of populating the array as soon as it’s instantiated,
Forcing us to add the information later. shown on your screen now are two ways in which we can do this in Java and C sharp. Now you’ll notice that there is no Python section because of the fact that creating populate later arrays is not conventionally possible
In the base version of Python, without the use of more advanced data structures or packages. You can see However, with Java and C sharp that just as with the other example, there are slight differences in the syntax on how we do this, but it generally follows some set pattern, the type
Of the array followed by a name for the array, which is then set equal to a size for the array. Remember, this size is final and cannot be changed outside of this initial call.
If you end up creating an array with the size 10. But then later in the program, find that you need more space for it. You can always go back to where you instantiated it and change the size. But after that line of code runs, there’s no conventional way to increase it.
You may also be wondering what the brackets mean when instantiating an array and that’s true Way to signify to the computer that we are indeed trying to create an array and not just a variable. Now that we know the two different ways to instantiate an array, we need to know how we,
As the programmer actually get information that is stored within the array so that we’re able to use it. And the simplest way to answer that question is through the means of a numerical index. an index is simply an integer, which corresponds to an element within the array. Now, the most
Important thing to know about indexes is that for a certain array, they begin at zero instead of one. So if we have an array of 10 elements, the first index would actually be index zero, the second would be index one, and so on all the way up to the ninth index.
It’s a little bit weird at first, but trust me, you get used to it. Now, to retrieve information from a certain position within the array, you would reference it using both the arrays name, and then the index number of the element you wish to retrieve.
Say we have our array called numbers here, which contains the integers one through 10. To print out the element at the fifth index, in this case, the number six, we would reference the array name, in
This case numbers. And then in a set of brackets, we would place the index we want to retrieve, in this case, the number five. What this piece of code is basically telling the computer is to print out the fifth index of the numbers array, which again is the integer six. Now because indexes
Start at zero instead of one, it’s very important to note that to get the 10th element of the array, you would actually need to reference it using the number nine since there is no 10th index. If you do end up making this mistake, it will result in an array out of bounds error,
Since there is no 10th index in the bounds of the numbers array. Referencing and arrays index number is how we actually replace elements within the array as well. Continuing with our numbers array, let’s say we wanted to change the last element, the integer
10 to be the integer 11. Instead, what we would do is reference the ninth index of the numbers array, the one which currently contains the integer 10, and set it equal to 11. This tells the computer to take the element at index nine and replace it with the integer 11.
Essentially swapping 10 for 11. Now the last thing I want to talk about before we jump into the time complexity equations for an array is the practice of putting arrays inside of arrays. An array with an array at each element is known as a two dimensional array.
Think of a two dimensional array as a matrix. It’s similar to any other array, except for the fact that instead of a primitive data type like an integer how’s that each element, we would instead have a whole other array with its own size and indexes.
Two dimensional arrays are useful for a variety of purposes, such as if you were programming, a chess board, a bingo board, or even an image where each element in the two dimensional array contains an RGB value, which when combined creates an image. Now referencing an element
Within a two dimensional array is mostly the same as with one dimensional arrays, except you now need two indexes, the first number would be the index of the column that you want to reference, and the second number would be the index of the row that you want to reference.
By combining these two numbers, we can single out an element within the two dimensional array that will then be returned to us. As an example, let’s create a two dimensional array with 16 names contained within four rows and four columns. Now to access the name Carl,
You’d first single out the column, which contains the name you’re looking for. In this case, Carl is in the third column, meaning it’s in the second index. Next, you would single out the row which contains the name you’re looking for. In this case,
The name Carl is in the third row. So we would again use the second index to reference it. Combining these two pieces of information gives us the index location two comma two. And if you look, Carl is indeed at index location two comma two. Just as another example,
Adam is in the first column two rows down. And so to reference Adam, you would simply call upon the element at index locations zero comma one. two dimensional arrays are just the beginning. You can also have three dimensional arrays, four dimensional arrays, and so on for containing
Large amounts of advanced relational data. But two dimension is where we’re going to stop for today. All right, that concludes the background information on arrays. Now that we know what they are, let’s actually talk about arrays as a data structure.
This is where we’re finally going to be using our big O notation knowledge from the previous segment. to judge the array as a data structure. We’ll be going through the four criteria we talked about previously, accessing elements within an array, searching for an element within an array,
Inserting an element into an array, and deleting an element from an array, and scoring it based on how effectively they can complete these four tasks using time complexity equations. Now accessing an element within an array can be conducted in an instantaneous of one time.
This means that for any element within your array that you want to know the contents of, you can do so immediately by simply calling upon its index location. This has to do with the way that an array is stored within memory.
For example, sake, let’s look at a fake portion of memory in the computer. You can see we have some information near the beginning, maybe some integers or strings that we’ve initialized, that’s not important. What’s important is that when we get to the part in our
Code, which instantiates an array, we already know exactly how large the array is going to be. Either because we’ve populated it with the elements needed, or given it a definitive final size. This means we also know exactly how much space we need to reserve in memory for that array.
Combining these two pieces of knowledge means we can instantaneously figure out the location of every single element within the array by simply taking the starting location of the array in memory, and then adding to it the index of the element that we’re trying to find.
So let’s say our array contains three elements, each of them integers. And we want to know what the element at the first index is. Well, we know that the array start storing data here. And we also know that every element within the array is stored contiguously together
In memory. And so by taking the starting location for the array in memory, and adding one to it, we now know that that’s where the first index of our array is going to be, and can return that stored value appropriately. This is the main reason why array sizes cannot be changed. All of
The information within an array must be stored in this one place. So that we’re able to do this, the contiguous structure of an array prevents you from adding space to it after it’s been initialized, because it literally can’t without breaking up the data and adding in the space to store new elements
Down the road away from the initial array. This would make accessing elements instantaneously not possible. Hopefully now you can see why both accessing an element within an array is O of one, as well as why array sizes are final, because not many other data structures allow you to have
Instantaneous accessing power, meaning arrays have a huge advantage on the others in this metric. Next up searching through an array is O of n. This is because for the most part, you will be working with unsorted arrays, those being arrays which are not in alphabetical numerical or some sort of quantifiable order,
Meaning that to find an element within the array, you may have to search through each element before you can find it. This is known as a linear search. And if you want to know more about it, click the card in the top right corner, and it will take you to that section
In our introduction to programming series. A link will also be provided in the description below. Now while there are faster ways to search through an array, those only work when the array is sorted. And so for a basic array, in worst case scenario, searching through it to
Find a particular element is going to be O of n. Now Sure, there are going to be cases where the element you’re searching for is the first element in the array, or even somewhere in the middle. But remember that when working with big O notation, we always use the worst case scenario.
And in this case, the worst case scenario is that the item that you’re searching for ends up being the last element within the array, which for an array of size n would take n operations to reach. Finally, inserting and deleting elements from an array both have a time complexity equation of O
Of n for inserting this is because adding an element into the array requires you to shift every element that’s after the index, you want to insert the value at to the right one space. For example, if you have an array of size five, currently filled with four numbers,
And you want to insert the number one into the array at index zero, you would first need to shift every element to the right of the zero with index right One, essentially freeing up the space for the new integer, while also retaining all of the information currently stored within the array.
Then, and only then can you actually insert it. This requires you to traverse through the whole array of size n, which is why the time complexity equation is O of n. Now, sometimes you might not
Have to shift the whole list, say in the case, you had the same array of numbers, only this time the fourth index was free, and you wanted to insert the number five in that open spot.
Since you don’t have to move everything to the right one, in order to make space for this new element, does that make inserting into an array have a time complexity equation of o of one? Well, no, because again, when we talk about a functions time complexity equation, we always
Refer to it in the worst case scenario, the most amount of operations that we’re going to have to conduct before we can insert an element into an array is n, the size of the list, making it’s time
Complexity equation O of n. Deleting an element from an array follows mostly the same idea, you shift every element to the right of the one, you want to delete down one index. And essentially, you have deleted that element. Again, let’s say we had an array of numbers one through five,
Only this time, we want to delete the number one at the zeroeth index, what we would do is set the zeroeth index to whatever is contained at the first index, in this case, the integer two. And then we simply repeat this process until we get to
The end of the array, finishing it off by setting the last element in the array to be some no value. This deletes the element from the array by basically replacing it with a value to the right. And then this process is repeated into it frees up one space at the end. Essentially,
We’re just moving the entire array down one. Now worst case scenario, we’re going to have to shift every element in the array of size n, making deleting from an array also have a time complexity equation of O of n. So there you have it the four time complexity equations for an array,
Accessing is O of one and searching, inserting and deleting are all O of n. Arrays are a really good data structure for storing similar contiguous data. Its ability to access any item in constant time makes it extremely useful for programs in which you would
Like to be able to have instant access to the information contained within your data structure. It’s also a lot more basic than some of the other data structures that we’ll end up talking about, making it both easy to learn and reducing the complexity of your code. Now, some disadvantages
Of the array are the fact that the size of the array cannot be changed once it’s initialized. Inserting and deleting from an array can take quite a while if you’re performing the function on larger data sets. And if you have an array which is not full of elements, you’re essentially
Wasting memory space until you fill that index location with a piece of data. Overall, the array is a pretty reliable data structure. It has some flaws as well as some advantages. A program that you write could use the array if need be, and it would work just fine. But sometimes you might
Want some extra functionality. And that’s where more advanced data structures come into play. One of those more advanced data structures is what’s known as the ArrayList. The ArrayList fundamentally can be thought of as a growing array,
We just finished talking about the array and how one of its major flaws was the fact that once initialized an array size could not be changed using conventional methods. Well, in contrast, an ArrayList size expands as the programmer needs. If you take a look at the
ArrayList on your screen now full of four elements, and you decide to add one to it, it will simply expand its size to fit five elements. As you can probably tell this is extremely useful. Which begs the question of why not just always use ArrayList. I mean,
In comparison, the array list seems to provide all the functionality of an array and then some Well, that’s definitely a valid question, and one we will get to later on in this section. But before we can do that, we need to cover the basics of an ArrayList including some of
The properties and methods associated with it. Alright, let’s hop in. So as we said before, an ArrayList is simply a resizeable array, making them extremely similar in structure. This is furthered by the fact that an ArrayList is actually backed by an array in memory,
Meaning that behind the scenes of your code, the ArrayList data structure uses an array as its scaffolding system. For this series, we need not go further than that. But for us, it just means that a lot of the functionality will be the same. Now, this doesn’t mean everything is going to be
The same, which you’ll see later on. But it’s still important to make note of before we get too deep into things. The next thing I want to do before we talk about functionality is actually go over how we initialize an ArrayList. To do this, again, is going to vary based on which language
You’re using. So shown on your screen now are two different ways to do so in Java and C sharp, you may notice again, that there is no Python on the screen. And this is because in the base version of Python, arrays and array lists are actually not separate
Entities. They are frankensteined together into a single data structure called lists. Lists take some functionality from arrays and some from array list. It’s a lot more complicated than that. But for this series, that’s all you’re going to need to
Know as to why we are not including Python. In this section. We discussed initializing Python lists in the previous section. So if you’re interested, you can go back and look at that. Now going back to ArrayList initializations. Another thing you may notice is that it
Looks a little bit awkward in the way that these statements are structured. And that’s mainly due to the fact that the ArrayList is actually its own separate class outside of the base version of these two languages. Now, I’m not going to get into class hierarchy and object oriented programming right now,
Because that’s a whole other topic with big concepts and even bigger words. For right now, this just means that to create a new ArrayList, we have to invoke the ArrayList class when defining it, which as you can see is done at the beginning of both initializations.
After that, you can see that we give it a name, which is then set equal to new ArrayList with a set of parentheses. Now in this parentheses, you have a few options, you can either enter in an
Integer, which will then be used to define a size for the ArrayList. Or you can just leave it blank. Leaving the parentheses blank like that will automatically define a preset size of 10 for the ArrayList. Again, just as a reminder, this can be dynamically increased as time goes on
If we add enough elements, but it’s just meant as a base size. Now you may be wondering if we can actually populate the array with elements when initializing it as we could with arrays. But array lists actually do not support this type of declaration.
Moving on, let’s talk about functionality. Now the array list can be thought of as pretty much the evolved form of an array. It’s a bit beefier has a little bit more functionality and is overall more powerful than array. That’s certainly not to say that it’s better in every case. But for
The most part, the ArrayList is going to be thought of as the older sibling amongst the two. This is attributed to the fact that it belongs to the prebuilt ArrayList class, which we talked about earlier. The fact that the ArrayList belongs to a class means it’s going to come with pre built
Functions that are already at our disposal from the moment we define and instantiate an ArrayList. More specifically, the ArrayList comes with methods we can use to access change, add to or delete from an easily if you were using an array, you would have to program most if not all
Of these methods by hand. And so having them pre built into the ArrayList class makes it especially useful. You’ll see that this is the case with a lot of the data structures down the road, we’re having a data structure belonging to its own class cuts out a lot of programming time,
You have to spend making appropriate methods for the functionality that you might want. Now the types of methods that you’re going to get will vary based on language. For example, in Java, you’ll have a variety of methods to use, including ones to add elements
To the ArrayList, remove them from the ArrayList, clear the ArrayList entirely, return it size, etc, etc. as well as tons of other more specific functions. And another language though, such as C sharp, you’ll have some of the same methods as the Java
ArrayList. But you might also have some methods so that the Java version does not and vice versa. The C sharp version might not have some of the methods that the Java version does. The same is going to apply for any other language you use, which might implement the ArrayList data structure.
Because of the variability surrounding the ArrayList amongst languages. In this series, we’re simply going to be covering six of the most common methods that are both useful and can be found in 99% of the ArrayList classes. These six methods are the Add method, the Remove method,
The get and set methods, the clear method, and the to array method. This may look like a lot but remember, all of these are pre programmed for you And so you don’t have to make them all
By hand, all you have to do is call them on a pre made array list and you’re set to go. Speaking of pre made array lists, before we dive into each of these functions and how they work, let’s first create an example ArrayList, we can use to manipulate and show how they work.
Let’s call it example a list and give it a size of four so that it’s not preset to 10. And we’re set to go. Now, the Add method actually comes in two different types. One, which takes in
Only an object to add to the end of the ArrayList. And one which takes in both an object to add to the ArrayList, as well as an index value representing the index to insert the object at.
Let’s start with the simpler of the two, one, which simply takes in an object. This method is for more basic cases where you don’t care about where in the ArrayList, the object you wish to
Add is going to end up, it will simply append the object you pass in as an argument to the end of the ArrayList. So let’s take our example ArrayList and run the Add method on an integer of two. Now, normally, ArrayList only hold objects, not primitive types, like the integer two that we’re
Trying to pass in. However, the computer will automatically convert our primitive integer into an integer object with a value of two, so that we can still add it easily. This is known as auto boxing. And it’s going to be used throughout the rest of the series to modify data structures with
Primitive types. So I just thought I’d mention it now so that you’re not confused later on. Okay, so when we run our code, since the ArrayList, is empty, and we ran the Add method, which doesn’t care about location, it’s going to add the integer to at the first index,
Index zero. Now if we run another add method, and this time pass in the integer five as an argument, since the zero with index is already taken, it will be slotted in as the first available open index, that being the first index. So as you can see, it’s pretty simple.
It takes in an object and we’ll put it at the first open location available. Moving on to the second type of add method, one which takes in an object to add to the ArrayList, as well as an index to place it. This one works very similarly to the previous
Only makes sure that the object that you’re adding is appended at the index provided. Again, let’s say now we want to add the number one to our example ArrayList. But we want to make sure it’s placed in numerical order. In this case, at the zero with index,
What we will do is call the Add method, providing the integer one as an argument. In addition to the index zero, we want to add to the ArrayList. Once the code has run, the ArrayList will automatically
Shift our integers two and five to the right one, in order to make space for the integer one. This works for any index contained within the bounds of the array list. So if we wanted to do it again, only this time, insert the number three at the second index,
So that the list remains in numerical order. We’d call example, a list dot add, and then in the parentheses passing the integer three and the index location two. After the code has run, you’ll see that we have added the integer into our ArrayList.
Now it’s important to note that because there are two integers being passed in as arguments, you must know which one your computer’s treating as the integer and which one the computer is treating as the index location. mixing these up could cause the computer to try and insert the
Attempted index location at a different location than the one you were attempting to insert at. So just be careful and knowledgeable as to the order your methods arguments are in. Now the next method that comes pre packaged in the ArrayList class is the Remove method. And this
One also comes with two different types. The first takes in an integer as an argument, and just as the name suggests, will remove the object if there is one at the index location provided and return
It back to the user. The second takes in an object and will simply remove the first instance of that object within the ArrayList If present, and will then return true or false whether an object was removed. So if we wanted to remove the number five from our ArrayList, we would have two different
Options. We could call example, a list dot remove, and inside the parentheses placed the index of the value we want to remove, in this case three, and the program will remove the object at index three. The other option would be to run another remove method, only this time passing an
Integer object of five. It has to be an integer object because if we were to just use five, the computer would try to remove the fifth index of the ArrayList, which doesn’t even exist. By creating an integer object, we can ensure that when the code runs,
The computer knows that we want to remove the first instance of the number five in our ArrayList. And running this will return true and remove the integer from our list. Now, if there is no integer five in the ArrayList, the Remove method will simply return false.
Now I quite like the number five, so I’m actually not going to permanently remove it from the ArrayList just yet. Up next is the get method. Now the get method is pretty much the same as referencing an index for an array, it takes in an index location, and will
Return back to you the value at that location. So example a list dot get with an argument of zero would return one example a list dot get with an argument of two would return three, and so on. The next method is the set method, which is how we replace elements within an ArrayList.
Much like the name implies, it takes in an index and an object as arguments. And we’ll set the index location of the index you passed in to the object you also passed in. So if we wanted to set the number five in our ArrayList, to be four instead, so that it matches
Nicely with the other integers, what we would do is call example, a list dot set, and within the parentheses pass in the index location of the element, we want to set, in this case three, and then also the object we want to replace at that index. In this case, the integer for
This method call will override the element at position three to be four instead of five. Now, you should be really careful when you’re using this method, because you don’t want to accidentally override an important element within the ArrayList. Next up is the clear method for
When you simply just hate your ArrayList. This is perhaps the simplest of them all. It has not taken any arguments, and will simply clear the ArrayList deleting every element entirely. Calling example a list clear on our ArrayList would delete all the objects within it. But I
Don’t really want to do that right now, especially with one more method to go. So for the sake of this series, let’s just keep the ArrayList filled with the values that it currently has. The final method that we’ll be covering in this section is a little bit different from the rest.
And that’s the to array method, which is used to convert an ArrayList to an array. I thought I would include this one because it’s really useful for combining the strengths and weaknesses of arrays and array lists.
The two array method takes in no arguments, and will simply convert the array list into an array. Now for this to work, of course, you need to set it to be equal to the creation of a new array,
Like shown on your screen now. But if it is done correctly, you’ll end up with a brand new array, which contains all of the contents that used to be in the old array list. You may notice though, that
Instead of an array of integers, it’s actually an array of objects. This mostly has to do with that object oriented programming stuff we talked about in the beginning. But for now, it won’t make too much of a difference, we can still treat it as a regular array, printing out indexes to
The console, placing elements within it. Typical array functionality. The only thing that changes is that it now contains integer objects instead of primitive integer types. So there they are the six major functions that come with any given version of the ArrayList class. Having these
At your disposal will account for much of the functionality, you might use an ArrayList for making them extremely valuable to now Let’s now move on to the array list as a data structure, again, we’re going to be looking at its four time complexity equations for accessing, searching,
Inserting and deleting. Now, if you remember back to the beginning of this segment, we mentioned that the ArrayList is backed by an array in memory. And this means just like the array, it too will have over one accessing power. Essentially, this means that when we use our get method,
Which takes in an index location, it will return to us the value at the index provided in instantaneous time. Now you might be wondering, how is this possible since the data stored within an ArrayList is certainly not contiguous? With is actually due to a really interesting
Reason. So interesting that before scripting the series, I actually had no idea was the case. So because it is my series, I’m going to take a moment to talk about it. So if we pull up our example ArrayList and memory, you can see that it looks a little bit different.
Let’s break down what’s going on. instead of storing the actual objects which are contained within itself, an ArrayList actually stores references or pointers to the locations of those objects in memory. So the zeroeth index based on the ArrayList is stored at the 87th location in memory, which is currently storing the integer one.
Checking back to our example ArrayList, you’ll remember that that is indeed what was stored at the zero with index of the example ArrayList. And this goes for every element within the ArrayList. The first is stored at the 91st memory location, the second at the 100th, and so on.
So as you can see, while the actual data is not stored contiguously the references to that data are. So when we run our get command, all it has to do is return the value that’s stored at whatever the index location points towards. It’s a bit more complicated than that, especially
The way that these references get stored. But that covers the gist of it. This is the reason our ArrayList can have instantaneous accessing power without having the data stored contiguously. Alright, tangent over, let’s get back to big O notation, time complexity equations
For the ArrayList. So we know accessing is going to be o of one. And searching is going to be O of n. This is for the same reason that arrays were o n. If we want to find out if an object
Is contained within our ArrayList. And that object is at the last index of the array list, we’re going to have to search through each and every element within it of size n to make sure because remember, we always go based on the worst case scenario.
Now inserting into the ArrayList is going to be O of n. Because worst case scenario, if we are inserting an element at the beginning of the ArrayList, we need to shift every element after the index we’re inserting to the right one, just like we needed to do for the array.
This requires a number of operations equal to the size of the array, making inserting O of n. Deleting is O of n for the exact same reason. If we want to delete the first element within the ArrayList, we would then have to shift every element down one to save space.
Additionally, if we want to delete an object contained at the last index, we have to search through the whole list to find it. Either way, it will be O of n. Alright, so there are four time complexity equations, accessing his old one and searching
For inserting and deleting are all O of n. If that sounds kind of familiar, that’s because these are the same as the arrays time complexity equations. See I told you they were similar. Now this does bring back up the question we posed at the beginning of the episode. Why even use an array
In the first place in comparison to the ArrayList the array just does not seem as useful? Well, let’s get into that by sizing these two data structures against each other mano a mano. Let’s compare. An array is a collection with a fixed size, meaning it cannot be changed,
Whereas an array list has a dynamic size, which can be updated to fit the needs of the programmer. Arrays can store all types of data, meaning both primitives and advanced types, whereas array lists can only store objects, not primitives. Now this problem is mostly solved through the auto boxing
Situation I talked about previously, but the fact still stands. Moving on an array is built into most languages, meaning it doesn’t have any methods pre made for you to interact or modify it. Whereas an array list is its own class, meaning it comes with useful methods to help you utilize it.
Finally, an array is very primitive in nature and doesn’t require a lot of memory to store or use. Whereas an array list is again a class, meaning it requires more space and time to use than an
Array will. Hopefully now you can see that while the array list is more powerful, it still does have some drawbacks which make using an array sometimes more appropriate. In general, you want to use arrays for smaller tasks where you might not be interacting or changing the data that often
And array lists for more interactive programs where you’ll be modifying the data quite a bit. So that’s the ArrayList. As a review, it is a dynamically increasing array which comes with a slew of methods to help work it as the array list is a hefty topic in computer science.
If you feel I didn’t do a good enough job explaining some of the concepts in the video. The sources used to write the script for this video will be linked in the description below. But if not, let’s move on to our next data structure.
The next data structure we’ll be talking about is the stack. Now at this point in the video, we’ll be diverging from what are known as random access data structures, ie arrays and array lists, and diving into sequential access data structures. What’s the difference? Well, if you remember back
To our discussion on arrays and array lists, we were able to access any element within the data structure by calling upon its index location. This would then result in the computer instantaneously returning the value at that location. Each element was independent of the one before or after it,
Meaning obtaining a certain element did not rely on any of the others contained within the data structure. That basically describes the gist of a random access data structure, one where each element can be accessed directly and in constant time.
A common non computer science example of a random access would be a book. Getting the information contained on a certain page doesn’t depend on all the other pages within that book. And getting an element contained within a random access data structure doesn’t depend on
All the other elements contained within that data structure. In contrast, elements in a sequential access data structure can only be accessed in a particular order. Each element within the data structure is dependent on the others and may only be obtainable through those other elements.
Most of the time, this means that accessing a certain element won’t be instantaneous. A common non computer science example of sequential access would be a tape measure. To get to the measurement of 72 inches, you would first have to go through inches one through 71.
There’s no way to just instantly get to 72 inches without first breaking every law of thermodynamics and probably the space time continuum. These are also sometimes called limited access data structures, because unlike random access,
The data is limited by having to obtain it through a certain way. So there you have it, random access data structures, which allow instantaneous accessing power and independent elements such as the array and array list. And then you have sequential access data structures,
Which only allow accessing through a particular order with dependent elements. For the next few segments, we’ll be covering a few of the popular sequential access data structures, such as stacks, queues, linked lists, and so on. Beginning of course, with the stack, we’ve
Already danced around the subject long enough. So let’s finally talk about what a stack actually is. Now, the stack, by definition, is a sequential access data structure in which we add elements and remove elements according to the lifepo principle. The lifepo principle,
Which stands for last in first out, means that whichever element we added to the stack last will be the first one we retrieve. Hence, last in first out, think of this as a stack of books.
Each time you add another book to the top, you do so by stacking it on top of the others. Then, if we want to get a book in the middle of that stack, we would first have to take off
All the books on top of it, we can’t just grab that book from the stack and expect the entire thing not to fall in on itself like some sort of literature ristic Jenga. The same goes for the stack as a data structure, we add elements to the top of the stack and
Retrieve them by taking them off the top of the stack. There’s only one way in and one way out for the data. We can’t simply access or modify an element within the stack all willy nilly like we
Were able to do with the array and the array list. This might seem like a weakness limiting the flow of data to one single point. But remember what I said during this segment on time complexity, many of these data structures have a built in functionality, which gives them an edge over
The others. And the stack with its life. Oh property is a prime example of that. Next up, let’s talk about some of the methods commonly associated with the stack. Now the stack class will always come with two methods pre built into its class, those being
Push and pop. These are the fundamental methods which we use to interact and modify the stack, making them extremely important to comprehend. In addition to those two, I’m also going to cover two more methods peak and contains, which are both useful and can be found in the stack class
Associated with most programming languages. Now, just like we had an example ArrayList let’s also create an example stack to help us show off these methods. And just like that, we’re ready to roll. Now push is a method which pushes an object onto the top of the stack. All it takes in as
An argument is an object to add to the stack and will return no value. When we do this, that object becomes the form front of the stack, and its size is dynamically increased by one. Let’s start running some push commands on a variety of different strings,
You’ll see that the stack slowly gets built. Now channel this to subscribe, a series of completely random words seamlessly pushed onto the stack. As you can see, we’re only adding information to one spot the top, there’s no insert method where we can just jam a string into the middle of the stack.
Moving on, the pop method is used to remove an element from the top of the stack, it does not take in any argument and will return the element that is popped off the stack back to
The user. Once a pop method has run, the element that was at the top of the stack is removed and returned back to the programmer. And the element which was second from the top becomes the new top
Of the stack. And so on our example stack, if we popped off each element, you’d see that each time one of these completely random strings is taken from the stack and returned back to the user until we are left with a sad, empty stack with no shameless promotion. Let’s add the strings back,
Obviously, just for the sake of the next two methods that we need to cover, and not for continuing the free advertising. So push and pop are how we add and remove the data within our stack. So they’re fundamentally
The backbone of the data structure. The next two I want to talk about peak and contains are more so used to interact with the data inside the stack without actually changing it. Not as useful for modifying data, but still extremely important. The first of these is the peak method,
The peak method allows you to get the value at the top of the list without actually removing. We talked about before that the only way to access elements in a stack was through the top. And this method is simply a way to look at what the top value is without having to pop
It off. It takes in no arguments and we’ll just return back the contents have the top element. In our case, if we ran it on our example stack, subscribe would be returned back to the user. Now if we popped off the top element and ran it again, two would be returned, it’s that
You get the idea. Again, let’s push subscribe back on at the top for educational purposes. Now the final method I’ll be covering is the contains method. This one is used for searching throughout the stack. It takes in an object as an argument
And will return a Boolean of whether or not that item is contained within the stack. Essentially, this method allows us to search through the stack without popping off every element until we find the one that we’re looking for, as the contains method does not modify the stack in any way.
So for example, example stack contains with an argument of subscribe would return true example contains with an argument of this would also return true. But example contains with an argument of Hello would return false. So there they are four common
Stack functions which are going to be vital if you ever want to construct a stack based program. Moving on to time complexity, for accessing the stack has a time complexity equation of O of n.
This is because in order for us to reach a certain element within the stack, we first have to pop off every element that’s above. Think of it like this, if we had a stack of stones, and needed to
Get to the bottom one, we’d first have to take off every stone on top of it. So worst case scenario, if the element we want is at the bottom of the stack, we first have to pop off every
Element above it. This would require a number of operations equal to the size of the stack, making the time complexity equation Oh event. This is one of the major drawbacks to using stacks. with arrays and array lists, we could easily access any element within the data structure
Instantaneously. And with a stack, that’s just not possible because of the way that it’s structured. Searching is going to be O of n for the exact same reason. Worst case scenario, if we’re searching
For an element that’s at the bottom of the stack, we have to go through the whole thing just to find it. Now, inserting and deleting make up for this by having time complexity equations of o of one. This essentially boils down to the fact that using our push and pop methods
Really only requires one operation. Since the data only flows in and out of a single point, inserting or removing an object from that point can be done immediately. For the push method, we simply add it to the top of the stack. And for the pop method. We just take it off from
The top. It’s not rocket science. Actually, it’s computer science but that’s Besides the point, there’s no need to rearrange data or move elements around like there was for the array and ArrayList, because we don’t have to the data that we’re modifying is right there on top.
So there you go, the time complexity equations for the stack. Now, you might be wondering if there are even uses for a first in first out data structure, because it seems kind of out there, I mean, limiting your data to a single entry point.
But you would actually be mistaken. stacks are used everywhere, both in the actual writing of other code as well as in real world situations. In fact, one of the most fundamental processes of computer science uses stacks as a way of keeping track of active functions or subroutines.
Of course, I’m talking about recursion. Now, I won’t get into recursion too much here. But basically, it’s the process of functions repeatedly calling themselves when the function calls itself, that call is added to a stack of processes. And when that
Stack finally reaches what’s known as a base case, the functions are all then popped off one by one. It goes much, much deeper than that. But we don’t have time for a full blown lesson on recursion.
Right now. If you want that, you can click the card in the top right corner of your screen, or the link in the description below, which will both take you to that part in our introduction to programming series where we cover it. Either way, stacks are the backbone for recursion.
And recursion is the backbone for a plethora of computer science related functionality, such as traversing data structures, keeping track of active subroutines in code, and much, much more. Some examples of stack based functions outside of computer programming, which you use
Every day include the Undo redo button in word processors and the back paging on web engines. Both use stacks. Similarly, they continually add tasks you’ve completed to a stack, either web pages that you’ve visited or words that you’ve typed. And then when you press Undo, or the
Back button in a web browser, all we have to do is pop off whatever the last task was off the stack. And bam, you’re right back to where you were a second ago. It’s like magic, but better in a way.
As you can see, the stack has a lot of real world applications, both on the consumer side and the client side. You interact and use stacks every day without even realizing it. And we’ll use stacks frequently as you continue along your computer science journey. And so by learning them,
You’re opening up a world of opportunities. That concludes our discussion on the stack. To review. It is a sequential access data structure in which we use the lifepo principle to add and remove elements from and again, life O stands for last In First Out of next we’ll be talking
About an equally useful data structure that functions very differently than the stack while also working very similarly. And that data structure is known as the queue. So now that we’ve talked about the stack, a sequential access data structure, which follows the life principle, we need to cover the opposite, which in computer science,
We obviously call a queue. Now by definition, a queue is a sequential access data structure, which follows the FIFO principle, or first in first out, the stack and q are very much a dynamic duo when it comes to the world of comp sigh. So you’ll notice a lot of similarities between the
Two and the way that they’re structured and how they work. Today, and in this segment, we’ll cover a lot of the same topics as we did with the stack, only for the queue. Now timestamps can be found in the description correlating to these topics. But if you’re sticking around,
Let’s dive deeper into what the queue actually is. Well, the queue like the stack is a sequential access data structure, meaning we can only access the information contained within it a certain way. Now, if you remember back to stacks this certain way was through the lifepo methodology, or lastin.
First out with the last element pushed onto the stack would always be the first one we popped off, similar to a stack of books that we add to and remove from. Now in contrast, the queue follows what’s known as the FIFO methodology, or first in first out,
Where the first element added to the queue will always be the first one to be removed. We can think of this as a line to your favorite amusement park ride. Mine as a kid was always
The Ring of Fire. So let’s just use that one as an example. The first one to get there, assuming we don’t have any cutters will always be the first one who gets to go on the ride.
The later you show up, too long do you have to wait. This is the strategy used for cues when adding and removing objects. The first element to be added will also be the first one to be removed. Another big difference between stacks and queues is the location we add and remove elements from.
You might remember that with the stack, we added and removed elements from one spot the top. With the queue. However, this is different. We add elements, the back, also known as the tail, and we remove them from the front, also known as the head. This allows us to make sure that we
100% follow the FIFO methodology. So there’s your background information on the queue, sequential access FIFO methodology, add elements the back and remove them from the front. Got it? Good. Now, let’s dive headfirst into how we can actually use a queue by jumping into some common queue methods.
So just like the stack, we’re going to have two methods used to add and remove elements from the queue. For the stack, we added elements with push and removed them with pop. In contrast, with a queue, we add elements using on cue and remove them using dq. In
Addition to these two methods, we’re also going to cover peak and contains, which if you watched the previous segment should look pretty familiar. Alright, let’s start. on cue is the first method and the one we use to add elements to the tail of the queue. It takes
In an object to put at the end of the queue, and simply adds that object, we’ll also increasing the size of the queue by one, let’s pull up an example queue, which can see currently has a size of zero.
But say we call on queue on a completely random string, let’s say the string now, that would be added to the tail of the queue, and the size would increase by one. Now, because there’s only one
Element in the queue, at this point, the string now is acting as both the head and tail for us. We can of course fix that by on queueing a few more completely random strings. If we add the
String video, the size goes to two, we can add this and it goes to three, like makes it four, you get the idea. And now we have a fully functional queue, as you can see, like is
Acting as the tail being that it was the last string added. And now is being treated as the head which makes sense considering it was the first string to be added. Moving on. dq is the method
We use to actually remove elements from the head of our queue. It takes in no arguments and will return the element that was removed from the queue back to the user. So if we ran a dq command on our
Example queue, you’d see that now is both returned back to the user and also removed from the queue. Additionally, the size of our queue has been dynamically decreased by one. If we run it again, video is returned and removed from the queue and the size goes down by one yet
Again, you get the idea. We can keep doing this for every element in the queue until it’s empty. But the next methods we’re going to talk about need some information to work with. So for now, let’s refill the queue back to its original four elements. The next method that I’ll
Discuss is peak. Now we’ve actually covered peak just a few moments ago in our segment on stacks. But if you forget or just didn’t watch that particular part, peek returns the object that’s at the forefront of our queue. It doesn’t take in any arguments and simply returns the foremost object
Of the queue without actually removing it. The key word there being without this method allows you to look at the head of the queue before you actually be queuing. There are a multitude of reasons that you might want to do this, maybe to make sure that the element that you’re about
To dq is the correct one, or to check to see if an element you need is still there, etc, etc. Whatever the case is, we can use the peak method to fulfill our needs.
If we were to run it on our example queue, you’d see that the string now is returned. But if we dq the first two elements and run it again, you’ll see that the string This is returned, pretty simple, but extremely effective. Again, let’s add video And now back into the queue for
Our next and final method. That method of course, being the contains method, the name pretty much says it all. The contains method will take an object and will return a Boolean of whether or not the queue contains that object. running it on our example queue with an argument of queue
Would return false because as you can tell, there is no q string contained within our queue. However, if we ran it on a string, such as video, it would return true because as you can see,
The string video is indeed in the queue. And there they are all together now on cue dq peak and contains four methods which will help you utilize a queue to its maximum efficiency. Speaking of efficient See, that takes us perfectly into the time complexity equations for the queue.
Now accessing an element within a queue is going to be Oh event, let’s say you had a queue full of three elements. If you want the object at the tail, you first have to dq every element off the
Front into the one you’re looking for is the head of the queue, Then, and only then can you actually get the value contained. Since this may require you to go through the entire queue of size n, accessing is going to be O of n. Remember, now queues are sequential access data structures
And not random access, meaning we can just grab an object from the middle of the queue. That’s just not how things work. Searching is going to be O of n for the exact same reason, trying to find an element contained at the tail of a queue requires you to iterate across the
Entirety of that queue to check for it. So in that scenario, we have to check every element within that queue of size n, making the time complexity equation O of n, inserting two and deleting from
A queue are both going to be an instantaneous o of one. This is because just like with the stack, we’re only ever on queuing at a single point, and we’re only ever D queuing at a single point.
This means that no matter how large the size of the queue is, it will always take the same number of operations for any magnitude to either insert or remove an element. And there they are, in all their glory, the time complexity equations for the queue, you may notice
That they’re identical to the stack, which if you’ve been paying attention is the truth for most of the properties about a queue. They’re very much a yin and yang, one in the same type deal different slightly in terms of the methodology you use to add and remove objects from them.
You’ll often see these two data structures talked about together frequently, just because of how similar their functionality is. The final thing I want to cover on the topic of queues are just some common uses for them within programming. What are these things actually used for?
And the answer is quite honestly, a lot on your computer. Right now. queues are being used for what’s known as job scheduling. The process through which the computer determines which tasks to complete for the user. And when like opening up a web page or a computer program.
It’s used many times in printers to keep track of when multiple printers Try to print and determining whose documents get printed first. Heck, if you’re looking for real world examples, Google even uses cues and their new pixel phones to enable what’s known as zero shutter lag,
In which they strategically use cues to eliminate the time between when you take a picture and what the phone actually captures. So yeah, in terms of functionality, the queue can be used in a variety of fields. So it’s good now that you know what they are and how to use them. This also
Concludes our discussion on the queue. To review the queue is a sequential access data structure, which follows the FIFO principle, were first in first out to add elements to the back and remove elements from the front. Up next, we’ll continue on the sequential access data
Structures train and talk about one of my personal favorite data structures. Next, we’ll be covering the linked list, and it’s a good one. So strap into your seats. Let’s just jump into things by talking about the elephant in the room. What exactly is a
Linked list? Well, to answer that a linked list is a sequential access linear data structure in which every element is a separate object called a node. Each node has two parts, the data and the reference, also called the pointer, which points to the next node in the list. Wow,
That is a pretty big sentence with a lot of ideas within it. So let’s break it down part by part. The sequential access part of that statement means that the information contained within the link list data structure can only be obtained through a certain methodology. We talked about this in
Our segment on the stack. If you remember, during that segment, we compare them to a tape measure. Because Similarly, you can only get measurements from a tape measure through a specific method. The specific method for a linked list will be covered a little bit later
For moving on. The linear part of the definition simply means that the information or data is organized in a linear fashion in which elements are linked one after the other. Now when we state that every element is a separate object called a node, this means that unlike
An array or an ArrayList, where every element is just let’s say a number, each element in a linked list will actually be an object which can have multiple attributes or variables. And I won’t dive too far into object oriented programming right now.
If you want a good introduction to that, you can check out the link in the description below, which will take you to our introduction to object oriented programming lecture. For this series, we essentially mean that the objects or note stored within each element of
Our linked list will hold two separate pieces of information. These two pieces of information come together to form the node. And these nodes are what make up our linked list. More specifically, those two pieces of information are the actual data or information stored within
That node, and the reference or pointer to the next node in the linked list. The data is where our strings or integers or Boolean values are kept the actual contents of our data structure. And the other piece of the puzzle is the pointer. This reference or pointer points to where the
Next node in the linked list is stored in memory. This helps link all of the nodes in a linked list together to form one long chain of information. Kind of like a computer science conga line, you should now be able to understand what a linked list is. Again, it’s a sequential
Access linear data structure in which every element is a separate object called a node, in which each node contains both data and a reference to the next node in the linked list. This cumulatively creates a string of nodes which we call the length list. Feel free to rewatch this
Explanation if you’re still confused, because I know it can get pretty hectic pretty fast. The next thing I want to do in this section is just visualize how one of these linked lists is set up. That way, you can actually see what I mean when I say nodes, error, and pointers and everything
Else, etc. So every linked list starts with what’s known as the head node of the list. This is just an arbitrary label, which represents a node containing some form of data, and also a reference to the next node in the linked list. For now, let’s just store the integer one in our head
Note. Now, since this is the only node so far in our linked list, the head node will simply point towards a no value, which is just to say it’s not pointing anywhere. Essentially, it’s pointing to nowhere and just being used as a placeholder until we actually give it something to point towards.
Let’s do that by adding another node to the link list and store the integer to inside of it. Instantly, you can see that now our head node points to this second node instead of a null value. You’ll also notice that this new node, which I’ll call the two node points to a
No reference value, just like the one node used to do, as it is now the last node in the linked list. This is a pattern you’ll notice as we continue adding nodes. The last node in the linked list,
Also known as the tail node will always point towards a null value. This is our way of telling the computer that we reached the end of our linked list and that there are no more nodes to traverse
Towards. Anyways, let’s now create our third node and inside store the integer three, this node now becomes the tail end points towards a North value. And the second node that we created, the one that used to point towards a null value. Now points to this new node which contains the integer three.
Essentially, we’re just adding a node to the tail of a linked list and then setting the references of the previous node to point towards that new node. And if you can understand that concept, you pretty much comprehend the gist of how these nodes interact. The two main takeaways are that every
Node has both information and a pointer. And the last node in a linked list points towards a null value. That’s pretty much the setup for a linked list. Definitely more abstract and fluid than, say an array or ArrayList, but hopefully not too complicated. Next up, we’re going to be discussing
How we add and remove these nodes from a linked list. Unfortunately, for us, adding and removing elements from a linked list isn’t going to be as simple as it was with the other data structures
Such as the stack or the queue. This has to do with the simple fact that we are actually able to insert and remove elements easily within a linked list at any location. With a stack or a queue,
We weren’t actually able to do this because the data could only flow in and out of a few specified points. This made it so we couldn’t remove an element from the middle of the stack or jam an
Element in the center of a queue. The way that they’re structured just didn’t allow for this. Using link lists. However, we can easily remove elements from the middle or jam elements in the center. And so today, we’ll be covering the different methods used to do so.
More specifically, we’ll be covering three different ways to both insert and remove nodes from a length list. Adding to and removing a node from the head, the middle and the tail of a linked list. These are all going to revolve around those pointers we talked
About at the beginning of the episode. Because whenever we change up a node in a linked list, we also have to change its pointers. And that can get pretty complicated pretty quickly. Luckily, that’s why I’m here. I’ve set up a basic linked list on your screen now with three nodes that we
Can use to play around with. Each node has a value of course representing the data inside the node, and also a pointer which points to the next note, the green and red coloring on the nodes with the
Integers one and three, simply indicate which node is the head node and which node is the town node. Green means head node, and red means it’s the tail node. Now in an actual link list, these pointers would be locations in memory. But for the purpose of this series will be representing
The pointers visually perfect. So let’s cut the chitchat and just jump right into it. The first method we’re going to be covering is adding and removing nodes from the head of a linked list. Lucky for us, this is pretty simple. To add a new node to the head of a linked list,
Literally, all we have to do is make that new nodes pointer point to whatever the current head node of the linked list is. By doing this, we simply take away the title of head node from the current head and bestowed upon this new node that we’re adding, it looks a little bit
Something like this. Let’s take a node with the integer zero and add it to the head of the linked list. All we have to do to do this is set its pointer to point towards the current head node.
Now, you’ll see that none of the other nodes have changed in the slightest. The only thing that has changed is that this new node with integer zero is the head node, and it now points towards the old head node. extremely simple, and the best part is that it works in reverse as well.
Removing a node from the head of a linked list is just as simple. All we have to do is set the head nodes pointer to some null value. Once we do, the head node will get cut off from the flow of information essentially removed from the linked list. If we
Did this on our example linked list, you’d see that once we set the zero nodes pointer to No, because it no longer points to the one node and no node points towards its location. It has been cut
Off from the rest of the nodes and exiled from the linked list. The old head node regains its position. And it says if this integer zero node never even exists. Moving on the next methods we’re going to cover are inserting and deleting a node from the middle of the linked list.
These two methods are definitely the most difficult of the bunch. And this is because we need to insert the node in such a way that the pointers get readjusted accordingly without losing any of the information. If we accidentally set the pointers wrong, or do things out of order,
The data could get lost forever. But luckily, I’m here to teach you how to do it the right way. We’ll start with adding a node to the middle of a linked list. Adding to the middle of a linked list is a two step process.
We first make the pointer of the new node point to the node after the location we want to insert at. Then we set the node before the location we want to insert that to point towards the new note. So
If we wanted to insert a node with the double value 1.5 after the node containing the integer one, but before the node containing the integer two, what we would first do is set the new nodes pointer to point to the node containing the integer two, then we would make the
Node containing the integer one point towards our new node which contains the double 1.5. By adjusting the pointers of the nodes before and after the location, we want to insert that we can strategically jam this node in the correct place without moving or modifying the entire list.
As you can see, now we have a linked list of length for where the link has not been broken and is also still contiguous. Removing a node from the middle of a linked list is even simpler.
All we have to do is make the pointer of the node previous to the one we’re removing to now point to the node after the one removing. Then if we set the pointer of the node we want to remove equal
To ignore value, we again cut the node off from the linked list and it is removed. Simple as that. So following these steps, if we now wanted to delete our 1.5 node, we’d make the one node again point towards the two node instead of the 1.5 node. Then if we delete the pointer
Of the two node, by setting it equal to null, it gets cut off from the flow of the linked list. No changes are externally made to the rest of the list. Just one lonely node removed. The final type of insertion and deletion we’ll be covering is inserting to and deleting from the end
Of a linked list. Doing this simply requires To modify the tail node of the length list, the one which currently points towards some null value. for adding a node to the tail, you simply make the current tails pointer, which is currently set to no to point towards the node you want to add.
So if we wanted to add a node with the integer four, we would just make the three node point towards this new node. Then by setting the four nodes tail to point towards No, we’ve made this
New four node the tail of the linked list, and the old tail node with integer three now points to the new tail. Removing the tail of a linked list is just as simple. If we want to remove the tail,
We just set the previous tail to point towards a null value instead of the current tail. This leaves the current tail node with no connection to the linked list, isolating it from the pack. Doing this on our list would look like making the three node point towards No.
And now because no node now points to our tail node continuing integer four anymore, it gets cut off from the linked list and essentially removed making the old tail node, the one containing the integer three, the current tail node once again. And so after a bit of pointer readjustment,
Hopefully now you can understand the pseudocode behind inserting and removing elements from a linked list with ease. Up Next are the time complexity equations for a linked list. Now accessing an element within a linked list is going to be O of n. This is because linked lists,
Again are sequential access data structures. This should be all too familiar if you watch the sections on stacks and queues. But if not, let’s just use a simple review. sequential access data structures can only be accessed through a particular way, meaning we
Can’t get any element we want instantaneously. resulting from this is the stipulation that if we want to get a certain element within a link list, we need to start at the beginning of the list and cycle through every node contained within it. Before we can finally access the one that we want.
We do this by using the pointers as a little map for the computer. First go to node one node one’s pointer gives you the location of node two in memory. And node twos pointer will take you to the memory location, which contains the
Node with the information that you want. It’s like a computer science treasure map and a way for a linked list of size n. This means you could have to traverse the entire linked list before finding your information making it’s time complexity equation O of n
Searching is O of n for the exact same reason, we check a node and if it’s not the one that we want, we use that nodes pointer to take us to the next node and check that one.
We do this for every node until we either find the node containing the value we want, or get to a node which points towards no indicating that we’ve reached the end of the linked list that the value that we’re searching for just isn’t contained within that particular length list.
Inserting and deleting from a linked list is a little bit complicated. Since linked lists usually only store the head and sometimes the tail nodes location in memory permanently. If we want to insert or delete an element at the beginning or end of a linked list,
We can do so instantaneously using the methodology we talked about previously. However, if we want to insert a node within the linked list, things become a little bit more complicated. In order to insert a node within the link list, we must first traverse to the location we want to insert it.
This means following that treasure map until we reach the insertion point. And then and only then can we actually follow the instructions to insert or delete a note. So depending on how and where you want to insert or delete a node at its time complexity equation will be either O of n
Or o of one a little confusing, yes, but necessary dimension for when it inevitably comes up. So in review, accessing searching, and sometimes inserting and deleting are all going to be O of n. And other times inserting and deleting will be instantaneous. Cool.
Now let’s finish up by talking about some real world applications of the linked list. Now, something I haven’t talked about before, but would be scolded by people in the comments for not mentioning is that linked lists can actually be used in the backing of other data structures.
What do I mean by this? Well, basically, we can use linked lists to make stacks, queues and some other data structures we haven’t talked about. This is in the same vein as earlier when I mentioned that the ArrayList uses the array as a backing support system in memory.
Now this goes a little bit above an introductory series, but it’s one of if not the most important uses of a linked list in computers. Science. So I thought I’d mentioned it here. Basically, because of the way that it’s structured. Having a stack or queue use the nodal methodology that we
Talked about during this episode, which comes with the link list to be the back end of it structure makes a lot of sense. If you’re curious, I’ll have an article linked below explaining this idea in better detail. I just thought it was a little bit above the complexity for an introductory course.
Now, that’s not to say link lists can’t be useful in other ways. A queue on Spotify, for instance, where each song in the queue doesn’t contain just an integer or a string, but an entire song with WAV data, a title, a length, etc. Then, when the track is done, it automatically points
To the next song in the playlist. Another example could be a photo viewing software where each node is an image, and the pointers simply point to the next photo in the list. Like I said, the main functionality of a linked list might be to back other data structures,
But it also has tons of uses in other areas of expertise. In Review, a linked list is a sequential access linear data structure, in which every element is a separate object called a node containing two parts, the data and the reference pointer
Which points to the next node that comes in the linked list. These pointers allow us to easily shift around each node, adding or removing it without having to move massive amounts of data like we would have to do in the case of an array or some other data structure.
One thing I haven’t mentioned yet about linked lists is that this pointer system does come with one big drawback. With a normal linked list, we can only ever go forward with our pointers never backwards from the computer’s eyes. Once we follow a pointer to a certain nodes, location and memory,
There’s no way to go back or undo to the previous one. Much like a shark, we can and only will ever go forward. This problem is fixed however, through the use of a data structure known as the doubly linked list, which coincidentally is the subject of the next segment in this video
Smallworld All jokes aside, Next up, we’re going to be covering the doubly linked list so strap into your seats. A doubly linked list is almost exactly the same as a linked list. That is to say it’s a sequential access data structure which stores data in the form of nodes.
Except with doubly linked lists. There’s one small difference. With the doubly linked list, we’re able to traverse both forwards to the next node in the list and backwards to the previous node in our list. Again, using pointers. How? Well let me explain.
With regular link lists. Each element was a node composed of both a data section and then a pointer which would take you to the memory location of the next node in the list. Using this, we were able to traverse a linked list easily to search for information,
Access data within a link list, or add and remove nodes from within the list with ease. A doubly linked list simply builds upon this by also having a pointer which points to the previous node location in memory. It’s an undo button of sorts, which allows you to fluidly go
Through the link list in either direction, instead of just limiting yourself to go in one direction. This is great since it allows us to jump around the linked list and have a lot more flexibility when it comes to modifying information.
Now because this can get pretty confusing very quickly, I want to do a visualization. Before that though, let’s use some lingo to help consolidate the terminology that I’ll be using. When I refer to a nodes. Next, I’m referring to that particular nodes
Pointer which points to the next object in the list, whether that be another node or no value. Similarly, when I refer to a nodes previous abbreviated to prevx, on the vigils, I’m talking about its pointer which points to the previous object in the linked list,
Again, either another node or no value. Doing this just helps keep things a little bit more simple because as you’ll see having both a previous and a next pointer makes things a little bit more complicated. Now on to what these doubly linked lists actually look like.
Just like with a regular linked list, every doubly linked list is going to start with a head note. Since it’s the first node in the list, both its previous pointer and its next pointer will point towards a null value. This is of course, because it can’t point to information which isn’t there.
We can fix this though by adding another node. Once we do, you can see that a few things have changed. The head nodes next pointer now points towards this new node instead of No, the new nodes previous pointer now points to the head node. And the new nodes next pointer now
Points towards a null value. As you can see, it’s Little bit more complicated than adding a node to a regular link list in which we only had to worry about one set of pointers as opposed to two, but still manageable. Let’s add one more node for demonstration purposes.
And you’ll see the same thing happens again. The second node now points to this new third node. And this third node gets initialized with a pointer which points both to the previous second node and also forward to some null value. You can see that with any two nodes,
The next pointer of the first and the previous pointer of the second come together to form sort of a cyclical connection which ties the two nodes together. Then at the head and tail of the list, there’s a connection which ties them both towards some no value. Most of this should
Be common sense, but it’s still good to go over. doubly linked lists are a little scary at first, but once you break them down, you realize that they’re just an evolved form of linked lists. of next we’re going to be talking about adding and removing nodes from a doubly linked list.
Again, using the three different methods that we talked about in the previous segment, adding and removing from the head, the middle, and the tail. I’ve also set up a basic doubly linked list with three nodes containing three strings to help us out with this next segment.
Finally, just like the last segment, the green on top of a node signifies that it’s the head node, and the red signifies it’s the tail node. Alright, with all that being said, let’s get into it. Now adding to the head of a doubly linked list is quite simple.
The first step is to take our new node that we want to insert and set its previous to no second, we set the new nodes next to point towards the current head node of the linked list. Then all
We do is set the current heads previous to point towards this new node instead of a null value, and we’re set to go. Doing this rearranges the pointers in such a way that the new node we want
To add becomes the head of the doubly linked list. Pretty simple. So if we wanted a new node with the string, aim to be the head of our doubly linked list, we would just follow the steps.
First, we set the aev nodes next to point towards the atom node, then we set its previous to point towards the null value. And finally, by setting the atom nodes previous to point towards the AV node, we have successfully added that node to the head of the list making it the head note.
Removing a node from the head is even simpler, we first set the head nodes next to point towards a null value. And then by setting the second nodes previous to also point towards a null value,
We can easily remove the head node from the list. This is how it would look in our example, we’d first set the aid nodes next to no, then we would set the atom nodes previous to also be no and then we’re done. Now because the aid node doesn’t have anything to point towards,
Nor does it have anything pointing towards it, it will be deleted from the list. The Atom node will regain its position as the head node and the program will carry on. Up next is inserting and deleting from the middle of a doubly linked list.
This is where things get really tricky, so make sure you’re paying attention. To insert a node into the middle of a doubly linked list, we follow a three step process. The first step is to take the node we want to add and set its previous to point towards the node
Previous to the position we want to insert at. Then we take that same node the one we want to add. Instead it’s next pointer to point towards the node after the position we want to insert. Finally, we set the next on the node at the position before the one we’re inserting, and
The previous on the node after the position we’re inserting to both point towards this new node. That is a lot of words, some of which might not even make sense to you. So let’s open up the space
On our screen real quick and do an example with our list. Let’s take a new node with the string Chris and add it between the Adam node and the bed node by simply following our steps.
First, we want to set the new nodes previous to point towards the node previous to the position we want to insert at. This means setting the Chris nodes previous to point towards the Adam node. Simple enough. Second, we set the new nodes next to point towards the node after the position we
Want to insert that this entails setting the Chris nodes next to point towards Ben. So far, so good. Then the last step is to set the node on the next before we’re inserting and the previous on the node after we’re inserting to both point towards this new node. So in this case, the
Atom nodes next and the Ben nodes previous both get set to the new Chris node. This completes the addition into list. Obviously, this is a little bit more complicated than inserting or deleting from the head. But as you can see, we’ve now inserted this new node into its rightful place.
It may be hard to see since the pointers are a little bit messy, but the flow of the list has remained constant without any breaks in the pointers, which is the most important part. Removing a node from the middle of a doubly linked list is also a three step process.
First, we set the node before the one we want to remove next to point towards the node after the one we want to remove. Then we set the node after the one we want to remove the previous two point towards the node before the one we want to remove.
The final step is to set both pointers of the node we want to remove to point towards a null value. Again, a little complicated, so let’s take it to our example list and try it out. Let’s delete the Chris note just for the sake of keeping things consistent.
Following the steps that we’ve laid out, we would first set the next of the node before the one we want to remove to point towards the node after the one we want to remove. So in this case, we said the atom nodes next to point towards the Ben note,
Essentially skipping over the crisnet. Then we set the previous of the node after the one we want to remove to point towards the node before the one we want to remove. So we set the bend node to point towards the atom node, again skipping over the Chris node.
Finally, we have to set the Chris nodes pointers to point towards null values. Now that we’ve done this, because no nodes point towards it, and it doesn’t point towards any nodes, the Criss node gets deleted from the doubly linked list,
The list is back to its original form with no breaks or errors. Adding a node to the tail of a doubly linked list is also a three step process. Step one entails setting the next pointer of the
Current tail to point towards the new node, we want to become the tail. Step two is setting the previous of the new node that we’re adding to point towards the current tail of the list. And step three is making the new nodes next point towards a null value. Again, let’s do an example
Where we add a new node containing the string Ethan to the tail of the doubly linked list. Following our steps, we first set the next pointer of the current tail, the coral node to point towards the Ethan node. Then we make the Ethan nodes previous point towards Carl,
And it’s next to point towards an O value. And we’re all set. Ethan has been successfully added as the new tail of the list in three quick and easy steps. Removing from the tail of the list is even easier and only requires two steps. We first set the tail nodes previous to
Point towards No. And then we set the second to last nodes next to also point towards No. On our example list, it looks like this. We first set the Ethan nodes previous to point towards No. Then we set the coral nodes next to also point towards No. This isolates any pointers going to
Or from the Ethan node and deletes it from the list making the coral node the tail once again. adding and removing information from a doubly linked list might sound like a hassle. But remember, we only have to use this pseudocode to program these functions once in whatever language
We’re implementing them in. And then we’re able to reuse them an infinite amount of times. Now for time complexity equations, since the doubly linked list is really just an extension of the linked list, it’s time complexity equations are going to be exactly the same
As they were for the link list. And for the exact same reasons, O of n for all four cases and sometimes over one for both inserting and deleting. If you didn’t watch the linked list segment and are wondering how we arrived at these equations, you can check the description for a
Timestamp which will take you to the discussion we had on linked lists time complexities. Finally, in terms of doubly linked lists, I just want to talk about some of the uses for a doubly linked list because there are a ton. The back and forth functionality of a doubly linked list
Lends itself to be implemented in a lot of stack like functionality, ie cases where you want to go back and forth between information that you’re storing for the user. Some examples of this could be the browser caches which allow you to go back and forth between webpages, the Undo redo
Functionality in many programs, applications which allow you to utilize an open recent functionality. The list goes on and on. Basically any case in which you need to store a list of objects with multiple attributes, a doubly linked list is going to be a safe bet to get it done.
Linked lists and their evolved form and the doubly linked list are a great way to store information because of the adaptability of the nodal structure. Since we’re not working with raw information like primitive types, and we’re storing All
Information inside of a shell, it makes it a lot easier to move the information around. This combined with the pointer system allows for non contiguous but still fast operating speed, making these two data structures a staple in computer science. Up next,
We’ll be covering dictionaries. And with that a little mini lesson on hash tables. This is the last of what I refer to as the intermediate data structures at the beginning of the lecture, and is honestly personally one of my favorites. So let’s not wait any longer and just jump into things.
Before we get too far, though, we should probably clarify that when we say dictionary, we’re not referencing that thick book you probably have lying around your house and haven’t used in years. Actually, dictionaries are one of the most abstract data structures which exist in computer
Science and can be used for a variety of purposes. Another thing I’ll clarify really quickly is that dictionaries are also sometimes called both maps and associative arrays by the computer science community. This moreso has to do with language specifics and preferences and not any
Functional differences, since all of them work in almost identical ways. But for this series, we’re going to be referring to them as dictionaries, just to keep things simple and organized. Now a dictionary in computer science, by definition is an abstract data structure, which
Stores data in the form of key value pairs. This means we have two main parts to each dictionary element, the key and the value. Each value within a dictionary has a special key associated with it. And together they create a pair which is then stored in the dictionary data structure
As an element. Think of a key value pair like a social security number. Each social security number is a key, which is then paired with a value, that value being an individual person. These social security number key value pairs then
Come together to form a dictionary of every human being living in the United States. This is very different from many of the data structures we’ve talked about previously, because we index dictionaries using these keys instead of a numerical index.
For example, with an array, we would index each element within the data structure according to a numerical value, which started at zero and ran the length of the array. With a dictionary, however, we index each element by using its key instead of some arbitrary integer and obtain information
Through that index instead. So what exactly are these key value pairs going to look like? Well, they can be just about anything. The keys and a key value pair can be any primitive data type that you can think of, we can have a dictionary which has integers as the keys,
One with strings as the keys, one with doubles as the keys, there’s really a lot of flexibility. As for the values, but we have even more flexibility with those. We can have keys and our dictionary correspond to pretty much anything, strings. Sure. Billions, of course,
Another dictionary with its own set of key value pairs, you can even do that too. This allows us to have tons of combinations in the way that we store our data, making dictionaries extremely powerful. as powerful as they are, though, there are two extremely important restrictions that we have
To cover when it comes to dictionary. And they are as follows. Every key can only appear once within the dictionary, and each key can only have one value. Let’s start with the first one. Each key has to be unique and cannot be replicated, duplicated, cloned,
Copied or anything else that would cause there to be two keys of the same value in a dictionary. Think of it like this, when you create a key value pair, the computer creates a little locked box in memory to store the value, then the computer spends days and weeks creating a customized
Handcrafted one of a kind key that corresponds directly to that locked box. This key cannot be replicated in the slightest. And that’s the same mindset you should use when working with dictionaries, no two keys can be the same. If you were to try and make
A dictionary with too similar keys, you would be thrown in error by the computer. The second stipulation is that each key can only have one value. Think back to our custom key example. It wouldn’t make sense for this one of a kind key to be able to open multiple boxes.
The same is true for our keys and computer science. They can only correspond to one value. Now one rule that we don’t have to follow is that there can be duplicates of values within a dictionary. Meaning we can have two separate keys both point towards equivalent values. As long
As the keys are different. The computer does not care. Alright, now that we know what dictionaries are and how they work, let’s jump into the time complexity. For a dictionary, or at least try to, let me explain. Now for a dictionary, the time complexity equations are a little bit funky.
Previously, we talked about linked lists and how they are sometimes used as the backing of other data structures in memory. For example, a stack might implement the linked list structure as its way of storing information. Well, the most common way to initialize a dictionary is to implement it
With what’s known as a hash table. Hash tables are a little more advanced than the content I wanted to cover in this series. But they are a huge part of dictionaries, especially when it comes to time
Complexity. So we’re going to give a little mini lesson on them today. Doing this will help you better understand the time complexity equations for a dictionary, as well as give you some background on Advanced Data structures. Alright, let’s begin with a little thought experiment.
Imagine this scenario for a second. say we have a dictionary which contains a few key value pairs like shown on your screen. Now, let’s just assume that to store all this information in the computer’s memory, we use an array like how it is shown on your screen now,
With a position that a cell is in the table also corresponds to the key and the key value pair stored in our dictionary. So the zero with cell would contain a key with the integer zero, which leads to a value. The fourth cell would contain a key with the integer four,
Which leads to another value, and so on. Any cell which we don’t have a key for is empty, or what the computer scientists refer to as nil. Why does this not work? Why can’t we just use an array like
This to back our dictionary in memory, since it looks like actions such as accessing and searching would run in constant time, since all the keys correspond to their table values in memory, all we’d have to do to get a value is simply reference the key at the index we’re looking for?
Well, this actually isn’t the case, because it’s based upon the simple assumption that the size of the array is not too large. Sure, this might work great for this dictionary where we have 10 or so elements. But let’s say instead of 10 elements evenly spaced out, we want to have one which has
10 values, which are sporadically placed from one to a billion. We want to keep the keys as being in the same index position as their values, so we can know exactly where they are and reference them easily. But by my count that is 999,999,990 nil values, just taking up space in memory.
And that is not good whatsoever. There’s got to be a better way to do things, right? Well, this is where our hash tables come in. Hash tables are fundamentally a way to store this information in such a way that we’re able to cut down the amount of nil values, while also
Allowing for the information to be stored in such a way that it is easily accessible. Basically, by using hash table, we’d be able to store these 10 keys in our dictionary, which range from one to a billion in a table with only 10 elements, while also being able to keep constant time.
How is this possible? Well, through the use of a trick program is used known as hash functions. A hash function will take all the keys for a given dictionary and strategically map them to certain index locations in an array, so that they can eventually be retrieved easily.
Essentially, by giving a hash function both a key and a table, it can determine what index location to store that key add for easy retrieval later. These hash functions can be pretty much anything which takes in a value and returns an index location.
The goal of a good hashing function is to take in a key, whatever that may be, and reliably place it somewhere in the table so that it can be accessed later by the computer. So with that being said,
Let’s just jump into an example. Because I know a lot of you might be confused. Let’s say we have our dictionary which contains keys in the form of integers from one to a million by a factor of 10.
So the keys are 110 101,000 10,000 100,000, and so on. A good hash function for this data set would be to take the key divided by itself, and then multiply the result by the number of digits in
The key minus one. So to find out where to store the value corresponding to the 1 million key, we would take a million divided by itself, which yields one and then multiply that by the number of digits in that integer minus one, in this case, seven minus one or six. This means we’d
Store the 1 million key at index location six. If we do this for every key in the dictionary, we can see that each key in the key value pair is stored at some index from zero to nine.
We’ve consolidated the 10 keys for One to a billion into 10 index lots instead of a billion. A pretty good improvement in my opinion, you might think this is a little over complicated for storing 10 elements. But remember, sometimes we might be working with 1000s of keys at a time,
Ranging in the billions, or even strings as keys, which is a whole other story. Now the best part about these hash functions, let’s say that we now want to get the value which is paired with a 1 million key, all we need to do is put 1 million back into our hash function,
And it will tell us where the value tied to that key is stored at within the table, in this case at the sixth index. Doing this allows us to pretty much instantaneously find where any key value pair is stored at within the table. All of this information may be
Pretty confusing. If you still aren’t 100%, I would recommend watching this part over again. However, in layman’s terms, and for this series, all I want you to be able to comprehend is that dictionaries are built upon these hash tables. And the keys in our key
Value pairs are stored in these hash tables and indexes which are determined by hash functions. And if you can understand that you’ve got a pretty good base for understanding hash tables. Now the final thing I want to talk to you guys about in regards to hash tables,
And the reason dictionary time complexity equations are so funky has to do with one small problem. What happens when we run two different dictionary keys into a hash function, and the computer tells us to store them at the same index location. For example, let’s say we
Have two dictionary keys with the strings, Steven and Shawn. And when we run both of them through our hash function, the computer instructs us to store both of them at the ninth index location, this should be impossible. How are we supposed to put both of them at index location nine.
This little problem is what’s known as a hash collision and can be solved one of two ways, either open addressing or closed addressing. With open addressing, we just put the key in some other index location separate from the one returned to us by the hash function. This is usually done by
Looking for the next nil value in the table, ie the closest location which contains no key. So with our example, the key Steven would get hash to the index location nine, mostly because it’s a better name. And the inferior key Shawn would get stored at index location 10,
Because it’s the closest open location available. This does make it harder to interact with the data in our dictionary later on, and can lead to problems if we eventually have a value which hashes to the index location 10, which is why computer scientists developed closed addressing.
Closed addressing uses linked lists to chain together keys that result in the same hash value. So the keys Steven and Shawn would get stored together in a linked list and index location nine. The main drawback to this is that whenever we want to interact with the value stored within a
Key value pair for either Steven or Shawn, we end up having to look through the linked list for that piece of data that we want. If there are 200 keys hash to one index, that’s 200 keys, we might have
To search through to find the one that we want. And that’s not very good. And with that concludes our mini lesson on hash tables. Now we can get back into dictionaries, and finally talk about their time complexity equations. Now remember back to the segment on time complexity really quickly.
Back then I mentioned that for these time complexity equations, we generally measure a data structure based on its worst case scenario. But when it comes to dictionaries, if we are to assume the worst case scenario, things get a little outrageous,
We basically end up assuming that our hash function makes it so that every key value pair ends up in the same index, meaning that each of our keys gets stored in a linked list, assuming that closed addressing is being used, then worst case scenario,
We have to assume that every operation functions how it would for accessing searching for inserting or deleting from a length list, which, if you remember is O of n for all four. This is of course preposterous and would probably never happen with the bare minimum decent hash
Function. Which is why in addition to the worst case, scenario, time complexity equations, I’ll also go over the average time complexity equations for these four operations. Now Lucky for us, they’re all going to be over one. This has to do with these hash functions we talked about before.
To access search for insert or delete a key value pair from our dictionary. All we need to do is run that key through our hash function, and it will tell us what index in the hash table to go to in
Order to perform that operation. There’s no time wasted looking through preset indexes because we, the programmer generate the indexes ourselves. And that’s the power of the hash table in the flesh. Overall, dictionaries are a very useful data structure when it comes to computer science
For a few reasons. They differ from the rest and quite a few big ways. The fact that they don’t use a numerical index to retrieve values, rather a preset key, the notion that those keys
And the key value pairs can be a range of types from strings to integers, to chars, and so on the implementation of the hash table, which allows for super quick utilization that is sure to come in handy in any program that you write. In conclusion, and overall, the dictionary is just
A solid data structure that can be used to fill in the gaps in your data structures knowledge. And with that, we have now completed all of the intermediate data structures if you will. Next, we’ll be moving on to trees and tree based data structures. This is the point in this series
Where we will be dropping our discussion on time complexity equations, because if you thought that the dictionary time complexity equations were complicated with hash tables and hash functions, trees, and there are many variants only further complicate things to the point where I no longer
Feel comfortable including them in an introductory course, we might mention that certain tree based data structures are good for accessing or searching. But as for discussions on all four time complexity equations, dictionaries are where we leave things. With that being said, let’s move
On to the final few data structures as we round out this introduction to data structures series. Next up on our list of data structures is the tree. No, not those big green things that inhabit the outside world and that you can climb on and get fruit from,
Rather the computer science data structure, which is way more fun in my opinion. Now, before getting into trees, we need to talk about data structures in general. Every data structure we’ve covered up until this point has been stored linearly. arrays, stacks,
Linked lists, all of these had a definitive start and end to their data, and you could point them out easily. Even the dictionary could be laid out in such a way to be represented linearly. Everything was so nice and neat and easy to visualize. On the other hand, trees store data
Hierarchically as opposed to linearly. What does that even mean? Well, besides being an extremely hard word to pronounce, it’s an alternative way to store data that we’re going to be using for the remainder of this series. It’s a little hard to visualize. So I’m going to start with an example.
The most common real world example of hierarchical data would be a family tree, each person would be an element of the family tree, and connections wouldn’t be based on a simple linear fashion. Rather, connections would be more abstract and can lead to multiple
Paths or branches, instead of just a single data point. Each generation is ordered on a hierarchy, which is where the name comes from. And as you can see, there’s no definitive end to the family tree. Sure, there are the ones at the bottom, which you could argue are the
Ends of the family tree, but which one of them is the definitive end, there is none. Another example could be a file structure system on your computer, you’d have a base folder, such as your desktop. And then inside of that, you might have multiple
Other folders for different types of information. And then inside of those, you might have more folders representing more types of information. And then finally, you would have your documents. Again, it sets up a network of those files on different levels, just like how we had with the
Family tree. Trees and the trees. Many variants are all dependent on storing data hierarchically, which of course finally begs the question of what exactly a tree is. Well, a trees in abstract data structure which consists of a series of linked nodes connected together to form a hierarchical
Representation of data. The actual information or data is stored in these nodes. And the collection of nodes along with the connections between them is what’s known as the tree. This is sort of like a linked list only instead of each node only pointing to one location, it has the option of
Pointing towards multiple, and also branching off on its own or pointing to no other nodes. Each of the nodes in a tree can also be called vertices and the connections between vertices. What linked two nodes together are called edges. Now the free flowing structure of a tree lends
Itself to a lot of different configurations. And with that comes a plethora of terminology about certain nodes, vertices, and just the structure of a tree in general. So what we’re now going to do is go over a lot of the terms associated with specific nodes based on where they are on
The tree and how they’re connected to other nodes while also visualizing the general structure of a tree at the same Time. Okay, let’s start. Let’s begin with the things we’ve already talked about. A vertices is a certain node in a tree, and an edge is a connection between nodes.
The first new thing is that every tree starts with what’s known as a root node. This is always going to be the topmost node of a tree. Let’s add a node with the integer 50 to serve as our root node.
Next up, let’s connect the two vertices to our root node using two edges. These two nodes we just added are what’s known as child nodes, since they are both connected to the node containing the integer 50. child nodes can thus be defined as a certain node which has an
Edge connecting it to another node one level above itself. Vice versa, the root node, the vertices containing the integer 50, is now what’s called a parent node to these two child nodes. Thus, we can define a parent node as any node which has one or more child nodes. Think back
To our family tree. If we were using people instead of integers, it makes perfect sense that the nodes directly connected to each other have some sort of familial relationship. Let’s continue on by adding two child nodes to the node containing the integer 20. When we do this,
The 30 node becomes a parent node, and the two nodes we’ve just added become child nodes. We have now branched off from the 20 node completely, and that the two child nodes containing the integers 10 and 15, respectively, share no direct association with it.
Speaking of the 20 node, since it does not have any children, it is what’s known as a leaf node, or a node in a tree which doesn’t have any child nodes. In this context, the 10 and 15 nodes would also be leaf nodes.
Finally, let’s add one more node as a child of the 10 node and there’s our tree in all its glory. As a quick review, the 50 node is the root node, the 30 and 20 nodes are children of that root
Node and the root node is thus the parent of the 30 and 20 node, then the 10 and 15 nodes are children of the 30 node. And the 30 node is thus a parent node to both the 10 and 15 nodes.
The five node is a child of the 10 node and the 10 node is a parent to the five node. And finally, the 515 and 20 nodes are all leaf nodes because they do not have any children. As you can see, one node or vertices on our tree can have many different titles
Depending on where it is in the tree and what other nodes are connected to it. For example, the 30 node is both a parent node to the 10 and 15 nodes, but also a child of the 50 node.
The 15 node is both a child of the 30 node, and also a leaf node as it has no children. This terminology really comes in handy when we start talking about trees which contain 1000s of vertices and edges, and the data becomes very complicated to order and maintain.
Moving on the next two pieces of terminology I want to go over with you guys are the height and depth of a tree. The height is a property of a particular tree in it of itself. And the depth is a property of each individual nodes are contained within a tree.
Let’s start with the height. The height of a tree is the number of edges on the longest possible path down towards the leaf. So in our tree example, since the longest path in our tree, which
Leads to a leaf is from the 50 node to the five nodes, and there are three edges in that path, the height of the tree would be three. The depth of a certain node is the number of edges required
To get from that particular node to the root node. For example, let’s take our 30 node. Since there’s only one edge connecting it on the way up to the root node, its depth would be one. For the 15 node. However, since there are two edges, which separate it from the root node,
The 15 node would have a depth to that’s pretty much all you need to know about the terminology associated with trees and computer science. As a review, we have the height and depth obviously. Then we have vertices, edges, root nodes, parent nodes, and leaf nodes.
Now there’s probably something that’s been scratching at the edge of your mind for quite a while now. And that’s why the heck are these called trees. They look nothing like trees. Regular trees are not upside down like this data structure would lead you to believe.
So who named trees and why? Well, there’s actually a simple answer to this. The tree is said to have been invented during the 1960s by two Russian inventors. And the last time that a computer scientists got up from the chair and went outside to actually see a tree
Is rumored to have happened back in 1954. Ever since then, it’s been grinding arrayed screens watching hours upon hours of their favorite youth. superchannel so please forgive them for their confusion when it came to naming conventions, they must have just forgotten trees aren’t upside down.
Now regular trees, like the ones we just created are great for storing hierarchical data. But their power can really be heightened when you start messing around with how the actual data is stored within them. by imposing rules and restrictions on what type of data is stored within a tree,
As well as where we can effectively use the tree data structure to its full potential. I could talk about the different types of trees for a long time, so long that many of them are full segments in this lecture. But for now, I just want to cover one popular variant.
This will be a good introduction to how trees can vary without simply diving into a huge deviation from what we already know. More specifically, the tree variant I want to talk to you guys about is the binary search tree. A binary search tree is a simple variation on the standard tree,
Which has three restrictions put on it to help organize the data. The first is that a node can have at most two children. This just helps make it easier to search throughout the tree as we don’t have to spend time looking through each of the eight children for a particular node.
Keeping it limited to two helps us do this. The second restriction or property is that for any given parent node, the child to the left has a value less than or equal to itself. And the child
To the right has a value greater than or equal to itself. This might seem weird, but it comes with certain advantages and disadvantages over using normal trees, which we’ll get to in a bit. The final restriction put on binary search trees is that no two nodes can contain the same value.
And this is just to prevent weird things from happening when we begin searching through the tree. Now, how do imposing these restrictions on a tree actually help us? Well, the biggest advantage of binary search trees is that we’re able to search through them in logarithmic time.
Because there is a natural order to the way that the data is stored. It makes it extremely easy to search for a given value. logarithmic time, if you remember back to the segment on time complexity is the equation in which we get more bang for our buck the greater number of elements
Or nodes have in our data structure. It works like this. All we have to do when searching is tell the computer to go left if the value we’re searching for is less than the current node, and right if it’s greater than the current node. We can then wash rinse and repeat this strategy
Until we find our desired note. This makes binary search trees really popular for storing large quantities of data that need to be easily searchable. Of course, this also translates to inserting, deleting and accessing elements within the data structure. But for the most part,
Searching efficiency is what really sets the binary search tree apart from the rest. stepping away now from binary search trees and into trees in general, let’s talk about common uses for them in computer science. The most common uses for trees in computer science includes storing data with a naturally hierarchical structure.
These are like the examples we touched upon at the beginning of this segment. Data Sets such as file structure systems, family trees, a company’s corporate structure, all of these could be stored and implemented using the tree data structure very easily.
These are all general examples though. As I mentioned before, when we put restrictions on trees, like in the case of the binary search tree, we can expand it to uses even further. A trees based structure is incredibly useful, and it can be modified in so many ways,
Which only add to its functionality. One of these ways is through what’s known as a try and is the next data structure on our agenda. So stay tuned for that. Next up, we’ll be talking about another one of the special trees with restrictions. We just finished
Discussing the binary search tree. And with that we mentioned how trees usually become even more useful once you start setting restrictions on how and where the data can be stored within them. Well, a try is another one of these special trees, which have special restrictions put in place to
Help store the data in an effective manner. This data structure is often overlooked since it’s only used in specific situations. But without the use of tries within those specific situations. Some important features of your computing life would be a whole lot harder. So we get it Steven tries a
Special tree with restrictions. But what are those restrictions and how can they help us? Well, let’s start with the basics. A try is a tree like data structure whose nodes store letters of an alphabet in the form of characters. We can carefully construct this tree of characters
In such a way Which allows us to quickly retrieve words in the form of strings by traversing down a certain path of the try. These are also sometimes called Digital trees or prefix trees by the computer science community. We’ll be calling them tries for today’s lecture. Trees are used in the
Retrieval of data in the form of words, which is actually where the name try comes from, as it’s smack dab in the middle of the word retrieval. Essentially, in layman’s terms, we use tries to retrieve words extremely fast by traversing down a tree of store characters. This is hard to
Explain without actually showing you. So let’s do an example of what a try might actually look like. Now, just like with a tree, every try is going to start with a root node only in our case,
That root node will be empty with either some null value or a blank string. Now also stored within this node will be a set of references, all stored within an array. These references are set to know at the beginning of the Tris existence, but can be slowly filled with references to other notes.
For example, let’s say we were creating a try to store words that start with the letter D. The root node would contain an array which contains a reference to a node containing the character D, signifying the start of our word. Now imagine for a second
That this D node also has an array containing references. Only this time, it contains references that point towards all characters in the English alphabet, which serves as the first two characters of a word in the English dictionary. So da serves as the first two
Characters and a lot of English words such as dad, or Tao, or dad if you really want to go that far. And so the array contained within the D node would hold a reference to an a node. Now since there
Are no English words, which start with DB that I know of, we wouldn’t have a reference to a b node. Since we know we will never have to retrieve a word from our try, which starts with dB. We continue this process for all letters in the alphabet, only including references to characters
Which serve as the first two characters in an English word. But that is a lot to visualize. So for now, let’s just put up on the screen two nodes that this first D node would point towards.
More specifically, the node, we’ve already added the a node, as well as the E node. Now to continue building our try, we would simply repeat this process for all of the nodes that this D node points towards. So we’d store pointers in the a node, which would point towards characters and the
English alphabet that serves as the first three characters of a word in the English dictionary. So you’d have a B, A, D, A y, and many, many more nodes as well. But we’re just going to stick with those three for now. For E, you’d have pointers which point towards nodes containing characters
Like n and w. Obviously, there’d be more nodes than the one shown on your screen right now for all levels of nodes. But what we’ve created here is a very simple try. As you can see, it’s exactly like I said it was in the beginning, a tree like data structure,
Which stores characters that can be used to make words by traversing down paths. As we traveled down different paths of our tree, we can make different words, dab, Dad day down the one path, and then and do down the other. By following the nodes downwards, we can easily build strings of words,
Which you’ll learn towards the end of the episode can be extremely useful. We can even take this process further by having one path contain multiple strings. For example, if we isolate the den path, we could continue the process to go on to words like dense or Denver or
Dent, the list goes on and on. We wouldn’t have to just stop at the word then since then, is also a prefix for numerous other words, and that’s what makes storing data and character format so useful. One path down to try can represent multiple words depending on where you stop along the process.
This does provide a bit of a problem for computer scientists though, how do we know when a word has ended? Let’s take the Denver path as an example. If we wanted to retrieve the word den from this try, how would we know to stop at the end node and not continue
Along to Denver? Well, there’s actually a pretty simple fix to this and it’s known as flagging. We simply mark the end of the word by having it also point towards a flag to let the computer know
That the end of a word has occurred. So in our Denver example, not only would the end nodes array contain pointers to whichever characters follow it, it would also contain a pointer to a node
With a flag to tell the computer to stop there. In this case, I’ve just chosen a period as a flag. This way we can control tries in such a way where an each word is marked by an ending point. And the different words that may branch off from the prefix can continue
To use that word as a prefix in whichever retrieval program ends up getting used. Okay, so now it’s time to talk about the general use cases of a try. If you remember back to the beginning of this segment, I said that the use cases for a try were
Limited, but extremely effective. And now we’re going to talk about what that statement means. Now, have you ever used the autocomplete feature on your iPhone or spellcheck on a Google Doc, because if so you have already experienced the overwhelming power of tries, as they are used for both of these extremely useful features.
This mainly has to do with the fact that for big programs like iOS or Google Docs, they’re not just storing a try containing a few words, or even all the words starting with a certain letter, like we tried to replicate their storing the entire English dictionary.
Storing the entire dictionary in a try seems like a tall task. But it can and has been done. Each node would simply have 26 nodes connected to it. And those 26 would have as many nodes
Connected to them as needed, and so on. And so now I can hear you asking you in the comments. How does this help us with autocomplete and spellcheck? Well, let’s say you’re typing out a word. For the sake of this video, let’s say it’s the word subscribe. You start with
The s. At this point, that computer has already eliminated 95% of words that you could be typing. We know it’s not going to be a word which starts with n, or with a or o or H or l etc, etc.
Then you type the letter U and bam, another 95% of possible options get deleted. With each character you type, you eliminate millions of possible words that you could be working towards. Using this fact, as well as popularity data, which could also be stored within the node,
The computer can start making educated guesses using that information, as well as context from previous words, to make a suggestion as to what word you’re trying to type out. The AI that works. This feature is immensely complicated, but it is backed by the tri data structure and helps
Autocomplete work easily on your phone. As for spellcheck, well when you spell a word wrong, a spell checking algorithm can use the root of your word and compare it against try data to make an educated guess as to what you were trying to spell. The slightly misspelled words will usually
Have a similar path from the root of the try. If you accidentally type chalk a lotta instead of chocolate, the computer can take the first few characters of the word you typed in correctly, and see where you may have gone wrong. Basically, by comparing the misspelled word to certain paths
Of the dictionary try, they can pretty accurately detect which word you were meaning to say and correct you accordingly. So there you have it, the try. Like I said, it is often underrated in the computer science world since it can only be used in certain situations.
But as I hope this segment has shown you, those situations are still important. Nonetheless, we are nearing the end of our introduction to data structures series. Now, only two more left before we part ways. So stay tuned, because now we’re going to talk about heaps. Now back in our segment
On trees, we talked about the binary search tree, a special type of tree which has a few properties. Each node can only have two children, the child to the left must have a value less than the parent
Node, and the child to the right must have a value greater than the parent node. And also no two nodes could contain the same value. Well, a heap is sort of like this, but a little bit different. More specifically, by definition, a heap is a special tree where all parent nodes compared
To their children nodes in some specific way, by being either more extreme or less extreme, ie greater than or less than. This specific way determines where the data is stored and is usually dependent on the root nodes value. There are two different methodologies generally used in computer
Science, and they are known as min heaps and Max heaps. In a min heap, the value at the root node of the tree must be the minimum amongst all of its children, and this factor must be recursively.
The same for any and all parent nodes contained within the heat. So each parent node must have a value lower than all of its children nodes. As you can see from our example, on the screen now
10 is the root node and also the minimum value in the tree. In addition to this fact, if we pick any parent node on the tree, and look at its children and their children and so on, the parent node will
Have the lowest value of the mall. Take 14 for example, its value is less than 2631 4435. In 33, this must be the case for every single subtree, which is contained within the heap. Max heaps on the other hand are the exact opposite. In a max heap,
The value at the root node of the tree must be the maximum amongst all of its children. And this fact must be recursively, the same for any and all parent nodes contained within the heap. If you take a look at the example max heap we have on the screen now, again,
You’ll see that this is the case 44 is the root node and also the largest value within the heap. If you take a look at say the sub tree, which is parented by the 35 node,
You’ll see that 35 is a maximum value amongst all nodes in that subtree greater than both 19 and 27. When we store data like this, and heap, whether that be a min heap or a max heap, it makes it
Extremely easy to insert or remove from. This lends itself to a lot of useful implementations within computer science. Now to show you this, I’d like to build an example max heap, the one which has the greatest integer stored in the root node. For the sake of keeping
Things simple, let’s pull up an array of seven elements with integers ranging from zero to 100, and simply convert it into a heap one element by one. This can be done in a few easy steps.
Step one is we add the first integer in as the root node. So 70 would get inserted into our tree as the root node, then we add another node to the tree in the bottom left most positions
Available. So we would first insert a node as the child of the root node to the left. For our heap. This means adding the integer for as a child of the 70. The final step is to recursively go up
The heap and swap nodes if necessary. Now when we say if necessary, we mean that if the node we just added is more extreme, either greater than or less than the node above it, depending on the type of heap that we’re trying to create, we swap them to maintain order amongst the heap.
Since we’re building a max heap, and 70 is greater than four, no swaps are necessary in this case. Now we just simply repeat steps two and three until we’ve built our heap. So next, we want to add the integer 90. And since the leftmost slot on the tree is already taken by
Our four node, the right slot ends up being the leftmost location on our tree. So we insert it there. And then since 90 is greater than 70, we actually end up swapping the 90 and 70 nodes. Doing this helps keep the max heap property intact, where every level is greater than the
One below it. Let’s keep going. Next, we add 45 to the heap. Now, since we’ve run out of space, on the second level, we move on to the third level and add 45 as a child of the four node,
Then we compare it to four, which is greater than so we swapped the nodes. Now we have to compare this node to the node above it again. Because remember, we recursively go up the tree until we reach the root or don’t need to swap. Now 45 is not greater than 90,
So it stays put where it’s at. Next up, we add 23 as another child of the 45 node, only this time on the right side, we compare and since it’s not greater than 45, we keep it as is.
Moving on, we next insert 76 into the tree as a child of the 70 node, then we compare and swap the 76 and 70 nodes as 76 is indeed greater than 70. We then compare 76 and 90. And since 90 is greater than 76. Keep the 76 node in place for now.
The next node we add is the 100 node, we compare it to the 76 node and see that it’s greater, so it gets swapped. And then we compare it again, this time to the 90 node. And since it’s also greater than that integer, it gets swapped yet again to become the root node,
Signifying it is the greatest node in the heap. As you can see, it’s a pretty simple concept, you add a node and then keep trying to swap up until the node you’ve added is in its rightful place. Deleting from heap is also pretty simple, at least in our case.
This is because the type of deletion I want to talk about is just the process of removing the root node from the heap. And you’ll see why later on. To delete the root node from a heap, you follow a three step process. Step one is actually removing the root node from our heap.
So in our case, we delete the 100 node. What you do with it is up to the programmer, you can return it back to the user stored somewhere else, print it out, etc, etc. Either way, then
Step two is replacing it with a node furthest to the right in this case It would be the 76th note. Finally, for step three, we do what’s known as a heapify. To fix up the heap, we start with the
Root node and compare it to its children to see if we need to swap any values. So for the 76 node, we compare it to its two child node. And since 76 is less than 90, we end up swapping those two.
Then we wash rinse, repeat for every subtree that we have. So on the right side, we swapped 90 with 76. But since 76, remains the greatest integer on that particular subtree, it stays in the same spot. On the left side, we didn’t change anything, but 45 is still the greatest integer
Amongst the three nodes in that subtree. So no swapping is necessary on that branch of the heap. And so we’ve completed our heapify, and all heap properties are still intact. That is inserting and deleting nodes in a nutshell. Now let’s talk about how we
Can use this to our advantage. Heaps are most commonly used in the implementation of heapsort. heapsort is a sorting algorithm which takes in a list of elements, builds them into a min or max heap, and then removes the root node continuously to make a sorted list.
Because heaps always start with the minimum or maximum value contained within them at the root node, we’re able to simply just remove the root node over and over again, keep refining the data structure after every pass. And after every element has been removed, we are
Left with a sorted list. On your screen, you’ll see we have an unsorted list on the left. In the middle, we’ve inserted all of those integers, and in doing so created a max heap. And then finally, on the right, we have continuously removed those elements from the root node into a now sorted
List. heapsort is a really cool algorithm, and it will be part of our upcoming series on sorting algorithms, which is kicking off very soon. So if you’re interested in that, make sure you subscribe to our channel so that you don’t miss it, a link will be in the description below.
Another extremely popular use of heaps is through the implementation of priority queues. priority queues are an advanced data structure, which your computer uses to designate tasks and assign computing power based on how urgent a certain matter is. Think of it like a line at the
Hospital. You wouldn’t want your line to follow a regular queue methodology which implements first in first out. Since then you could have patients with extremely urgent matters like heart attacks, waiting behind people coming in for a routine checkup. And the same way you wouldn’t want
Your computer to update an application before it finishes rendering a video. Otherwise your entire progress would be lost. priority queues take care of all the task scheduling done by your computer, and the heap data structure is used as the backing system for it. And with that ends
Our discussion on heaps. To review, they are a special tree in which each level contains nodes with values more extreme either greater than or less than the nodes on the level above it. Next up is unfortunately the last segment in the series on yet another tree based data structure
The graph. The graph is arguably the most dynamic data structure in our introduction to data structure series and an absolute banger to go out on. So let’s just hop right into it. Before we get into the nitty gritty details, I first want to do a short little exercise.
Visualize for a second a few of your favorite places to eat on a map around your town. For me personally, it’d be places like five guys chick fil a Panera, Wawa and Domino’s. Now imagine for a second that you are ravished absolutely starving. And so your plan is obviously to drive around to
Each of your favorite places to eat in order an ungodly amount of food from each location. Each food location has a few possible paths going to and from it. And so we add those to the map as well. Now you can see what we now have looks like a network of delicious foods,
We can start anywhere, and all we have to do is make sure to hit all five. You may not know it, but what we’ve essentially done here is set up a simple graph. Basically, graphs are composed of pieces of information like the restaurants and the path set run between them.
Of course, this is just generally, by definition graphs are a nonlinear data structure consisting of nodes and edges. There are a finite set of these nodes or vertices, which are connected by edges. nodes and edges should be familiar to you if you watch the segment on trees.
The big difference between trees and graphs however, is that with a tree we had a specific starting point. Sure, there were multiple paths down the tree that branched off from the initial starting point. But you always had to begin at the root note. In contrast with a graph there
Is no specified starting point, we can begin from any node and traverse to any node. Just like how on our food example, we are able to start at any restaurant. graphs are a huge concept and escaped the bounds of computer science often being used in many places you wouldn’t even think of.
But before we get into anything crazy, though, like the difference between a directed or undirected graph or a cyclic versus cyclical graphs, let’s get down the basics. Now, every graph is composed of these nodes or vertices and the edges that connect them. Let’s
Pull up a sample graph really quickly and talk about it. We represent graphs visually like this a lot, because it makes it way easier to comprehend. But notationally wise, a graph actually looks like this, which is much harder to comprehend. So let’s break it down. First,
We have the vertices set, which contains a comma separated list of all vertices within the graph. That’s the simple part. Each comma separated value simply represents a node within the graph. Then we have the edge set, which is a little bit more complicated. Each element of the edge set is
An ordered pair which describes relationships between nodes. For example, the first one describes a relationship between the six and four nodes. The fifth indicates a relationship between the five and two nodes, and so on. Using these two sets, we’re able to visualize a graph pretty
Easily by laying down both the information and the connections that fall between them. One final thing I want to mention about the basics of graphs is about the relationships that occur between two nodes. If we have an edge, which connects two different vertices, they are known as
Adjacent to one another. So for example, the five node would be adjacent to the four two and one nodes. Okay, now that we have the basics down, I now want to jump into the different attributes that a particular graph might have. Starting with directed versus undirected.
An undirected graph is one in which the direction you traverse the nodes isn’t important. This is most prominently indicated by a lack of arrows pointing to specific nodes. Such was the case with our first example graph, or even the food example from the beginning of the episode.
We can hop between nodes or even go back and forth between them without problem. A good way to visualize undirected graphs is like a network of friends on Facebook, where each edge indicates a friendship, if you will.
Because of the fact that when somebody accepts to be your friend on Facebook, you are both added to each other’s friends list. The friendship goes both ways and direction is unimportant. In contrast, a directed graph is one in which the direction you traverse the nodes is important.
This is usually indicated by arrows representing which nodes a certain node is able to traverse to. The edges could point both ways but they don’t have to. It’s very possible the edge only points one way. A good way to visualize directed graphs is by thinking them as a network of friends on
Instagram. Sure, I can follow famous celebrity Will Smith, but the odds that he follows me back fairly low. And so in that case, the relationship only goes one way. undirected and directed graphs both have their uses. As we discussed with the social media example,
Both provide different functionality which will be useful to you and your computer science journey. Just like the next type of property a graph can be classified as either cyclic or a cyclic acyclic graph is one which contains a path from at least one node back to itself.
So you can see by the example on your screen now that the four node leads to the three node which leads to the two node which leads to the one node, which finally leads back to the four node, forming
A cycle, essentially, we’re able to follow at least one path that eventually leads back to our starting point. A small thing to note here is that all undirected graphs end up being cyclical. The bi directional nature of nodes within undirected graphs theoretically forms a cycle between any two
Nodes. So judging by that logic, all undirected graphs end up being cyclic. In a acyclic graph is one which contains no path from any one node which leads back in on itself. This property can really only apply to undirected graphs like we mentioned previously. Essentially, this means that for any
Given node, there is no path which will eventually lead back to itself. undirected directed acyclic and a cyclic are all properties we can use to classify types of graphs based on their nodes. But the last property I want to talk about actually applies to the end. Have a graph instead.
And it’s the process of waiting. Waiting the edges of a graph means associating a numerical value with each edge, often called the cost of that edge. Each weight represents some property of the information you’re trying to convey. For example, again, going back to our food location scenario,
Since the information that we’re trying to convey is a good route, which takes us to each location, a good weight for our edges, and that scenario could be the distance between nodes. This comes in handy a lot, especially with navigation, such as the case with our restaurant example.
As we of course, always want to find the path of least cost or weight between the different nodes. So there are the major properties of heap that the different nodes and edges can have directed or undirected, cyclic or a cyclic and weighted or unweighted. There are a couple more
Obscure ones out there, but those six are what we will be covering today. Combining these three properties together leaves us with numerous types of graphs, which all have different strengths and weaknesses. It would take a while to talk about each of these and there are implementations.
So for now, I’ll just pick out three types of graphs which are used in the most popular cases. Now probably the most famous implementation of the graph data structure is through the undirected cyclical graph with weighted edges. This one gets a lot of use, especially through its implementation in Dykstra shortest path algorithm.
This algorithm given a graph and a source vertex within that graph, compiles a list of the shortest possible paths from that source vertex to all other nodes. As you might be able to tell just from its description, this has a multitude of uses across the entire tech world.
Google uses this algorithm for Google Maps. It’s used in the process of IP routing, and it can even be implemented in telephone networks. Another type of graph, which you probably use quite often is the unweighted cyclical graphs both undirected and directed,
As these make up the follower systems of a majority of social media websites. We already talked about these in the cases of Facebook, which would use a cyclical representation, as well as Instagram which would use an a cyclical representation. However, this example encapsulates
Much more than just those to Snapchat, Twitter, tik tok, even all these platforms can represent your follower following base through a graph and oftentimes do Facebook even has a graph API, which you can use to interact with the models that they use to illustrate each user’s web of friends.
As you can see graphs and there are many different forms provide a lot of the functionality that you interact with in everyday life, contributing to almost any facet of the internet. And with that concludes our discussion on graphs. As we review, a graph is a data structure which is
Represented by a set of nodes and edges. These come together to form a visualization of data, whether that data be food locations on a map or friends on social media. The different types of graphs provide a multitude of implementations in computer science. And with that concludes our
Introduction to data structure series. After around three hours and 12 data structures, you should now have the basic knowledge to take with you as you continue along in your computer science journey. And if you’ve made it this long, you obviously liked what you saw. So stick around
For an extra 30 seconds while I’ll pitch to you why you should check out my personal channel. Now I introduce myself at the beginning of the series, but again, my name is Steven. I’m an 18 year old computer science student who runs a YouTube channel called nullpointerexception with
One of my good friend Shawn. We’ve been producing content like this seriously for about four months now. And I’ve grown a good audience of around 800 subscribers, which we couldn’t be happier about. If you’d like to join us, you can check out our channel linked in the description below
And just try out a few of our other videos. And if you like what you see, you can subscribe. That ends my pitch and with that I have nothing else to say. I hope you have enjoyed this series as much as I’ve enjoyed making it. Thank you so much for watching.