Data Structures for Beginners Full Course Tutorial

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 time stamps for each major topic covered in this video as well as time stamps taking you to every smaller section contained within those topics so please feel free to skip around if you are 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 would 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'd just like to say if you're not already subscribed to our channel no point or 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 1 000 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 this 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 a 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 while 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 head first into what i believe are the basic data structures those being arrays and 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 the revolved 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 1 on efficiency section 2 on basic data structures section 3 on intermediate data structures and wrapping it up with section 4 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 of it 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 the 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 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 in that specific functionality by looking at a data structure's report card if you will we can get a quick sneak peek at what they're good at and what they are 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 a 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 conducted 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 a 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 its time complexity equation was the one shown on your screen now we would pronounce this time complexity equation as o of 2 meaning it takes two operations from the computer before our make believe function can finish if the time complexity equation was o with a 5 in the parentheses instead it would be o of 5 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 our 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 metric 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 n 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 at 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 quarks 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 the computer will finish the task in one step if your data set has 100 elements one step one 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 1 the line remains constant at 1. no matter the volume of data stored within the data structure the computer can complete that task in a single instruction whether it be accessing searching inserting or deleting of 1 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 o of 1 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 search is 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 a 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 1 000 instructions and so on o 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 2 to the n these are both incredibly inefficient equations which should be avoided if at all possible because they are 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 will never have time complexity equations that exist 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 but 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 time stamp 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 a video game prices for an online shop pretty much any list of values which are fundamentally similar meaning of the same's 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 talk about by the way so just keep that in mind in array we'll 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 contained a 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 array instead 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 of 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 ten thousand this would mean that john smith has a salary of ten thousand this is really good because as you'll see later on we can't store differing types of variables in the same array so we couldn't have these 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 all right tangent over let's get back to the attributes of arrays and the second one will 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 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 an 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 counter-intuitive and useless but later on when we talk about an array's 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 and 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 3 containing the numbers 1 2 and 3. 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 1 2 and 3 the array would instinctively have a size of 3 as it now contains 3 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 four 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 a 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 is no conventional way to increase it you may also be wondering what the brackets mean when instantiating an array and that's just a 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 1. so if we have an array of 10 elements the first index would actually be index 0. the second would be index 1 and so on all the way up to the 9th 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 array's 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 1 through 10. to print out the element at the fifth index in this case the number 6 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 tenth 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 an array's 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 9 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 housed at 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 are 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 2 comma 2. and if you look carl is indeed at index location 2 comma 2. just as another example atom is in the first column two rows down and so to reference atom you would simply call upon the element at index location 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 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 it can complete these four tasks using time complexity equations now accessing an element within an array can be conducted in an instantaneous o 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 starts 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 1 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 of 1 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 1 space for example if you have an array of size 5 currently filled with 4 numbers and you want to insert the number 1 into the array at index 0 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 5 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 1 well no because again when we talk about a function's 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 its 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 zeroth index what we would do is set the zeroth 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 null value this deletes the element from the array by basically replacing it with a value to the right and then this process is repeated until 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 of one and searching inserting and deleting are all 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 arraylists i mean in comparison the arraylist 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 array list 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 resizable 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 array list 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 frankenstein together into a single data structure called lists take some functionality from arrays and some from array lists 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 arraylists actually do not support this type of declaration moving on let's talk about functionality now the arraylist 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 an 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 pre-built 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 it 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 where 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 wants to add elements to the array list remove them from the array list clear the arraylist entirely return its size etc etc as well as tons of other more specific functions in another language though such as c-sharp you'll have some of the same methods as the java array list but you might also have some methods 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 two 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 examplealist and give it a size of 4 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 array list 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 2. now normally arraylists only hold objects not primitive types like the integer 2 that we're trying to pass in however the computer will automatically convert our primitive integer into an integer object with a value of 2 so that we can still add it easily this is known as auto boxing and is 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 2 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 will 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 at this one works very similarly to the previous only make 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 would do is call the add method providing the integer 1 as an argument in addition to the index 0 we want to add to the array list once the code has run the array list will automatically shift our integers 2 and 5 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 examplealist.add and then in the parentheses pass in the integer 3 and the index location 2. 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 is 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 5 from our arraylist we would have two different options we could call examplealist.remove and inside the parentheses place the index of the value we want to remove in this case 3 and the program will remove the object at index 3. the other option would be to run another remove method only this time pass in an integer object of 5. it has to be an integer object because if we were to just use 5 the computer would try to remove the 5th 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 5 in our arraylist and running this will return true and remove the integer from our list now if there is no integer 5 in the arraylist the remove method will simply return false now i quite like the number 5 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 will 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 5 in our arraylist to be 4 instead so that it matches nicely with the other integers what we would do is call examplealist.set and within the parentheses pass in the index location of the element we want to set in this case 3 and then also the object we want to replace at that index in this case the integer 4. this method call will override the element at position 3 to be 4 instead of 5. 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 array list next up is the clear method for when you simply just hate your arraylist this is perhaps the simplest of them all it does not take in any arguments and will simply clear the arraylist deleting every element entirely calling examplealist.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 arraylists the twoarray method takes in no arguments and will simply convert the arraylist 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 know let's now move on to the arraylist 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 of 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 what this 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 in 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 zeroth index based on the arraylist is stored at the 87th location in memory which is currently storing the integer 1. checking back to our example arraylist you'll remember that that is indeed what was stored at the zeroth 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 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 all right tangent over let's get back to big-o notation time complexity equations for the arraylist so we know accessing is going to be 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 array list and that object is at the last index of the arraylist 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 array list 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 all right so there are our four time complexity equations accessing is of 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 array's 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 mono e mono 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 autoboxing 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 media requires more space and time to use than an array will hopefully now you can see that while the arraylist 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 an array lists for more interactive programs where you'll be modifying the data quite a bit so that's the array list 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 i.e 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 1 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 through the next few segments we'll be covering a few of the popular sequential access data structures such as stacks cues 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 lifo principle the lifo 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 literaturistic 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 the 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 lifo 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 array list 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 forefront 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 arguments and will return the element that has 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 it 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 will just return back the contents of 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 2 would be returned instead you get the idea again let's push subscribe back onto 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 we're looking for as the contains method does not modify the stack in any way so for example examplestack.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 it 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 o of n this is one of the major drawbacks to using stacks with arrays and arraylists 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 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 array list 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 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 will 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 lifo principle to add and remove elements from and again lifo stands for last in first out up 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 lifo principle we need to cover the opposite watching computer science we obviously call a q now by definition a q is a sequential access data structure which follows the fifo principle or first in first out the stack and queue are very much a dynamic duo when it comes to the world of compsci 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 lifo methodology or last in first out where 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 down 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 the longer 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 cues 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 cue however this is different we add elements to 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 to the back and remove them from the front got it good now let's dive head first into how we can actually use a cue by jumping into some common cue 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 the queue we add elements using onq 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 all right let's start oncue 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 while also increasing the size of the queue by 1. let's pull up an example cue which you can see currently has a size of 0 but say we call on cue 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 1. 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 cueing 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 cue 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 1. 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 peak 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 keyword there being without this method allows you to look at the head of the queue before you actually dequeue it 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 dequeue is the correct one or to check to see if an element you need is still there etcetera etcetera 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 dequeue 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 in 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 q would return false because as you can tell there is no queue 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 efficiency that takes us perfectly into the time complexity equations for the queue now accessing an element within a queue is going to be o of n let's say you had a queue full of three elements if you want the object at the tail you first have to dequeue every element off the front until the one you are 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 cues are sequential access data structures and not random access meaning we can't just grab an object from the middle of the queue that's just not how things work searching is going to be ofn 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 q are both going to be an instantaneous o of 1. this is because just like with the stack we're only ever on queuing at a single point and we're only ever dequeuing at a single point this means that no matter how large the size of the q 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 are very much a yin and yang one in the same type deal differing 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 cues 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 cues 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 in 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 eq is a sequential access data structure which follows the fifo principle or 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 linked 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 compared 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 but 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 array list 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 now 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 notes 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 to 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 linked list feel free to re-watch this explanation if you are 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 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 the next node in the linked list for now let's just store the integer 1 in our head node now since this is the only node so far in our linked list the head node will simply point towards a null 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 length list and store the integer 2 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 null 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 a 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've 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 3. this node now becomes the tail and points towards a null 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 3. 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 linked 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 linked 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 it to the next node the green and red coloring on the nodes with the integers 1 and 3 simply indicate which node is the head node and which node is the tail node green means head node and red means it's the tail node now in an actual linked list these pointers would be locations in memory but for the purpose of this series we'll be representing the pointers visually perfect so let's cut the chit chat 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 node's pointer point to whatever the current head node of the linked list is by doing this we simply take away the title of headnode from the current head and bestow it upon this new node that we're adding it looks a little bit something like this let's take a node with the integer 0 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 0 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 headnode's pointer to some null value once we do the headnode 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 node's pointer to null 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's as 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 at to point towards the new node so if we wanted to insert a node with the double value 1.5 after the node containing the integer 1 but before the node containing the integer 2 what we would first do is set the new node's pointer to point to the node containing the integer 2. then we would make the node containing the integer 1 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 at 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 4 where the link has not been broken and is also still contiguous removing a node from the middle of the 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 we're removing then if we set the pointer of the node we want to remove equal to a null 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 2 node instead of the 1.5 node then if we delete the pointer of the 2 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 you to modify the tail node of the linked 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 null to point towards the node you want to add so if we wanted to add a node with the integer 4 we would just make the 3 node point towards this new node then by setting the four node's tail to point towards null we've made this new 4 node the tail of the length list and the old tail node with integer 3 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 3 node point towards null and now because no node now points to our tail node containing the integer 4 anymore it gets cut off from the linked list and essentially removed making the old tail node the one containing the integer 3 the current tail node once again and so after a bit of pointer readjustment hopefully now you can understand the pseudo code 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 linked 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 1 node 1's pointer gives you the location of node 2 in memory and node 2's 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 in 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 its time complexity equation of n searching is o n for the exact same reason we check a node and if it's not the one that we want we use that node's 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 null indicating that we've reached the end of the linked list and that the value that we're searching for just isn't contained within that particular linked 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 node's 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 linked list we must first traverse to the location we want to insert at 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 node 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 1. 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 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 cues 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 computer science so i thought i'd mention it here basically because of the way that it's structured having a stack or cue use the nodal methodology that we talked about during this episode which comes with a linked list to be the back end of its 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 linked lists can't be useful in other ways a cue on spotify for instance where each song in the queue doesn't contain just an integer or a string but an entire song with wave 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 mass 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 node's location in 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 small world 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 note in the list and backwards to the previous note in our list again using pointers how well let me explain with regular linked 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 linked 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's location in memory it's an undo button of sorts which allows you to fluidly go through the linked list in either direction instead of just limiting yourself to going 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 node's next i'm referring to that particular node's pointer which points to the next object in the list whether that be another node or null value similarly when i refer to a node's previous abbreviated to prev on the visuals i'm talking about its pointer which points to the previous object in the linked list again either another node or null 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 node 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 node's next pointer now points towards this new node instead of null the new node's previous pointer now points to the head node and the new node's next pointer now points towards a null value as you can see it's a little bit more complicated than adding a node to a regular linked list in which we only had to worry about one set of pointers as opposed to 2 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 null 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 up 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 all right 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 null 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 abe to be the head of our doubly linked list we would just follow the steps first we set the abe nodes next to point towards the atom node then we set its previous to point towards a null value and finally by setting the atom nodes previous to point towards the abe node we have successfully added that node to the head of the list making it the head node 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 node's 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 abe nodes next to null then we would set the atom nodes previous to also be null and then we're done now because the abe 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 and set its next pointer to point towards the node after the position we want to insert at 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 atom node and the bend 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 atom node simple enough second we set the new nodes next to point towards the node after the position we want to insert at 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 bend nodes previous both get set to the new chris node this completes the addition into the 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 removes previous to 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 set the atom nodes next to point towards the bend node essentially skipping over the chris node 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 node's 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 chris 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 2 is setting the previous of the new node that we're adding to point towards the current tail of the list and step 3 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 karl node to point towards the ethernode then we make the ethern node's previous point towards carl and it's next to point towards a null 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 null then we set the second to last nodes next to also point towards null on our example list it looks like this we first set the ethern nodes previous to point towards null then we set the coral nodes next to also point towards null this isolates any pointers going to or from the ethern node and deletes it from the list making the carl 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 pseudo code 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 its time complexity equations are going to be exactly the same as they were for the linked list and for the exact same reasons of n for all four cases and sometimes of 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 time stamp which will take you to the discussion we had on linked list 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 i.e 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 web pages 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 in 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 more so 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 0 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 in 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 well we have even more flexibility with those we can have keys in our dictionary correspond to pretty much anything strings sure booleans 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 two similar keys you would be thrown an 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 in 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 equations 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 all right 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'd use an array like how it is shown on your screen now with the position that a cell is in the table also corresponds to the key and the key value pair stored in our dictionary so the zeroth 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 1 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 million 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 a hash table we'd be able to store these 10 keys in our dictionary which range from 1 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 programmers use 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 at 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 ten so the keys are one ten one hundred one thousand ten thousand a hundred thousand and so on a good hash function for this data set would be to take the key divide it by itself and then multiply the result by the number of digits in the key -1 so to find out where to store the value corresponding to the one million key we would take a million divide it 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 6. 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 0 to 9. we've consolidated the 10 keys from one to a billion into 10 index slots 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 thousands 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 the one million key all we need to do is put 1 million back into our hash function and it'll 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 at 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 sean 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 9 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 i.e the closest location which contains no key so with our example the key steven would get hash to the index location 9 mostly because it's a better name and the inferior key sean 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 stephen and sean would get stored together in a linked list at index location 9. the main drawback to this is that whenever we want to interact with the values stored within a key value pair for either steven or sean 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 linked 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 of 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'll 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 in 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 structure's 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 the 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 their 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 structure 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 could 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 tree's many variants are all dependent on storing data hierarchically which of course finally begs the question of what exactly a tree is well a tree is an 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 link 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 vertice 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 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'd make 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 is 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 5 node is a child of the 10 node and the 10 node is a parent to the 5 node and finally the 5 15 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 thousands 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 and of itself and the depth is a property of each individual node 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 a 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 node 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 of 2. 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 scientist got up from their chair and went outside to actually see a tree is rumored to have happened back in 1954. ever since then it's been grinding away at screens watching hours upon hours of their favorite youtube channel 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 2 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 no nodes we 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 write if it's greater than the current node we can then wash rinse and repeat this strategy until we find our desired node 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 include storing data with a naturally hierarchical structure these are like the examples we touched upon at the beginning of the 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 its uses even further a tree's base 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 stephen a try is 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 but we'll be calling them tries for today's lecture tries are used in the retrieval of data in the form of words which is actually where the name tri 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 note 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 null at the beginning of the tri's 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 serve as the first two characters of a word in the english dictionary so d a serves as the first two characters in a lot of english words such as dad or dao or dab 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 serve 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 ones 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 travel 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 den since den is also a prefix for numerous other words and that's what makes storing data in character format so useful one path down a 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 there is 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 n 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 the flag this way we can construct tries in such a way wherein 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 spell check 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 they're 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 on now i can hear you asking in the comments how does this help us with autocomplete and spell check 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 the computer has already eliminated 95 percent 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 percent 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 auto-complete work easily on your phone as for spell check 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 chocolata 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 it 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 structure 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 compare to their children nodes in some specific way by being either more extreme or less extreme i.e greater than or less than this specific way determines where the data is stored and is usually dependent on the root node's 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 fact must be recursively the same for any and all parent nodes contained within the heap 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 26 31 44 35 and 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 note 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 subtree which is parented by the 35 node you'll see that 35 is the maximum value amongst all nodes in that subtree greater than both 19 and 27. when we store data like this in a 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 0 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 leftmost position 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 4 as a child of the 70 node 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 4 no swaps are necessary in this case now we just simply repeat steps 2 and 3 until we've built our heap so next we want to add the integer 90 and since the leftmost lot on the tree is already taken by our 4 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 a third level and add 45 as a child of the four node then we compare it to four which it is greater than so we swap 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 can pair 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 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 store it somewhere else print it out etc etc either way then step two is replacing it with the node furthest to the right in this case it would be the 76 node finally for step 3 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 nodes and since 76 is less than 90 we end up swapping those too 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 heap sort 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 keepifying 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 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 cue 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 in 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 and 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 paths that run between them of course this is just generally by definition graphs are a non-linear 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 node 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 in our food example we were able to start at any restaurant graphs are a huge concept and escape 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 acyclic 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 in your computer science journey just like the next type of property a graph can be classified as either cyclic or acyclic a cyclic 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 the cycle between any two nodes so judging by that logic all undirected graphs end up being cyclic an 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 cyclic and acyclic 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 edges of a graph instead and it's the process of waiting weighting 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 are 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 in 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 a heap that the different nodes and edges can have directed or undirected cyclic or acyclic 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 their 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 views especially through its implementation in dijkstra's 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 acyclical representation however this example encapsulates much more than just those two snapchat twitter tick tock even all these platforms can represent your follower following base through a graph and often times 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 a 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 3 hours and 12 data structures you should now have the basic knowledge to take with you as you continue along 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 stephen i'm an 18 year old computer science student who runs a youtube channel called null pointer exception with one of my good friend sean we've been producing content like this seriously for about four months now and have 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

Channel: Geek's Lesson

Views: 314,378

Rating: 4.9698339 out of 5

Keywords: data structures, data structures full course, data, structures, data structures full course tutorial, data structures tutorial, data structures for beginners, data structures course, data structures for data science, data structures advanced

Id: YOfXMQnUlZY

Length: 179min 26sec (10766 seconds)

Published: Sat Aug 22 2020