Data Structures For Python Developers (w/ Flask) - Course

people often learn about data structures out of context but in this course you will learn foundational concepts by building a real world api with python and flask giorgio is the instructor and he has a knack for helping people understand data structures in a practical way hey what's up everybody my name is giorgio and in this video we're going to learn about what i consider to be the most foundational data structure concepts by building an api using flask and python this video is directed towards both beginners and experienced programmers the only prerequisite for this tutorial is a basic understanding of python we'll start with installing python in flask and setting up our virtual environment and then we'll move into configuring our database and coding up our api skeleton from there we'll add the routes to our api by making use of data structures such as linked lists hash tables binary search trees and stacks and queues and of course if you're interested in more from me be sure to subscribe to my youtube channel essie like a pro for more content like this and without further ado let's get started to begin we'll need to install both python and flask the installation process for python starts at python's website here which i will also link in the description so to start you'll just want to go to this downloads tab and then download python 3 for your operating system after the download is complete you'll be able to access the installer which is self-explanatory once you've completed the python 3 installation process you should be able to check that the installation was successful by typing in python 3 dash dash version at the command line most likely my python version will be different from yours i have an older version but as long as you have the most updated version you'll be okay for this series now that we have python installed we can move on to installing flask the flask installation documentation can be found here which i will also link in the description the flask installation is pretty straightforward the documentation will go over the benefits of using a virtual environment and will also instruct us on how to set up our virtual environment now a virtual environment essentially just compartmentalizes our project and its dependencies so that there won't be any clashes with additional projects that we might make in the future so within this virtual environment that we create all of the libraries and the version of python that we use at the time of the initiation of the virtual environment will be preserved and contained within that environment and if in the future you set up another python project you would then initiate another virtual environment for that project specifically so to create a virtual environment we'll first need to create a directory that will contain our project and then we'll cd into that directory and we'll use this python command to call the virtual environment module and this here will be the directory that the environment will be allocated to so i'm just going to call our project directory flask api and then change directory into that folder so once we're in our project folder we can create our virtual environment by running the command from the flask documentation and once this command has completed its execution you'll be able to see the environment folder by typing ls to list the contents of your current directory and if you change directory into this environment bolder and ls again you'll see the contents contain more subfolders but you don't actually need to worry about what all of these are currently just know that whenever we install a new library it's going to be contained within this folder and also our current version of python that we use to initialize this environment will be also contained within this folder and we can double check that if we ls this bin folder and within this folder we can see our python binaries as well as our pip binaries and pip is just going to be used to install additional libraries so we can see the back one directory and now we're back in our project directory so now that we've installed our virtual environment we now need to activate our virtual environment because currently although we've installed the environment we haven't yet activated it so to activate it as we see in the documentation here we can use this command to activate our virtual environment so we can just paste that command in here and now our virtual environment should be activated and for most of you you'll be able to see that the environment is activated because you'll see in parentheses here it'll say environment but for me my shell is configured in a way that doesn't allow the display of the environment but you can know for sure that your environment is activated if you type in this command so you'll type in environment and then you'll pipe it into grep and then you're going to grab virtual environment and if you type in this command you should see an environment variable called virtual environment that contains the path to your virtual environment and again the path is going to be this venv folder that's within our project directory so now that we've activated our virtual environment we can move on with installing flask so to install flask we just need to use pip and run this command pip install flask so we can just copy and paste that and then with our virtual environment running we can just run pip install flask and if you get this warning down here that says that your version of pip needs to be upgraded you can go ahead and run this command here so once we've installed flask and we've updated pip if necessary we can kind of get an idea of how this virtual environment is working if we ls our virtual environment folder once again and then ls this bin folder which contains the binaries that we can use within this virtual environment and now you'll see that within this bin folder we'll have a flask binary so now whenever we're running this this flask command within our virtual environment it's going to be using this flask binary to run the command as opposed to any global installation of flask that you might have on your system so everything that we install for this project is going to be contained within this environment within this environment folder it should be noted that in a real production application the structure of your code will likely be different depending on the size of the application for the purposes of this tutorial and to reduce the level of complexity of the application structure in order to focus on learning the targeted concepts we'll write the entirety of our api with the exception of our data structures in one dot pi file if you would like to later extend this api you can easily reorganize the structure of the application by splitting the single dot pi files and moving the resulting parts around according to your needs so we'll create our main file for our api and we'll call it server.pi and just a quick note throughout this tutorial i'll be using vim as my text editor but feel free to use whatever ide or text editor that you feel comfortable with it's only important that you create a server.pi file in our project directory to start we'll want to import flask request in jsonify and we'll want to create an app variable that points to a flask instance and if we take a look at what this flask object is actually doing we'll see that this flask object implements a whiskey application and acts as the central object it is passed the name of the module or package of the application once it is created it will act as a central registry for the view functions the url rules template configuration and much more you don't really need to know what's happening behind the scenes here just know that this whiskey application is a middleware that sits between our python application in the server and it's what's going to make the implementation of our api possible so we can go ahead and add comment here that just says app next we'll want to set up the database configuration to our application so we can add configurations to this app that we just created by adding them to this configuration dictionary that's already a part of our app instance so if we go to the definition here we can just see that the configuration dictionary behaves exactly like a regular dictionary which means that if we wanted to add a key for our database we could do it like we would add a value to any other dictionary and for the sake of simplicity for this project we'll just be using an sqlite database which will essentially just be a local file that will contain the data for our database and we can just name this file sqlite db.file and we'll also want to create another configuration which we will just assign the value 0. and we don't need to bother ourselves with what this configuration is for just know that if we don't add this configuration we'll get errors and that's about all of the configuration that we're going to need to use a local file as our database we'll also need to make some additional imports now that we have our local database file configured we'll need a way to access and query that database within our python application and we'll do that by using this flask sql alchemy extension now if we access this link and go to the home page you can see that sql alchemy is an object relational mapper that gives application developers the full power and flexibility of sql essentially what an object relational mapper or an orm does is it allows you to interact with an sql database in an object-oriented way behind the scenes it's converting your object-oriented code into sql statements and queries so flask sql alchemy just makes sql alchemy more compatible with flask applications and the way this essentially is going to work is we're going to create classes that represent the tables in our database so for example if we have a table for users with an orm we're going to create models for each table and a user table in class form would look something like this and each of these are going to be columns within this user table and for each column we'll have the data type for the value and in the case of strings we'll have the maximum number of characters and this last one here posts is going to be a relationship to another table that we're going to create called blog posts because this api is going to be an api for a blog website so now that we understand what an object relational mapper is and we understand what sql alchemy is we can move back up to our necessary imports and configuring sql alchemy to work with our api so we're going to need to import sql alchemy and i'll go over what these imports are going to be used for in a second and we're going to need to add one more configuration because by default sqlite doesn't enforce foreign key constraints so we're going to need to add an additional section here to configure sqlite3 to enforce foreign key constraints and you don't need to worry yourself too much about what this code means it's essentially just allowing us to configure the db connection to enforce foreign key constraints via this line here and from here we can create an instance of our database by passing our app into this sql alchemy class and if we go to the definition of this class we'll see that this class is used to control the sql alchemy integration to one or more flask applications so it's just connecting our orm with our flask application and we'll also just define a now variable for date values when updating tables in the future so now that we've got our configuration set up we can go ahead and save this file and we're going to need to install some of the imports that we added to our server.pi file so first let's check to see if our virtual environment is running by running this command and if you see that this virtual environment environment variable has the path to our projects v e and v folder then we are good to go so for those of you that are using mac sqlite is already going to be pre-installed on your system but if you're using something like linux then depending on your disk drill you can install sqlite by running apt-get install sqlite3 or uninstall sqlite3 but again you're going to have to look into installing sqlite for your particular system so we can go ahead and do python server.buy and we'll get errors so here it says that no module named sql alchemy of course because we didn't install it yet so on really quick let me just clarify something really quick so if we go back into our server.pi file you'll see that we're importing from sql alchemy and we're also importing from flask sql alchemy so the only reason we're importing from sql alchemy as opposed to flask sql alchemy here is because we need to configure sqlite to enforce foreign key constraints and we need to use this event and this engine from sql alchemy to actually make this configuration work but other than for this code here to enforce foreign key constraints throughout this application we'll be using flask sql alchemy so to install sql alchemy we can just run pip install sql alchemy and if we attempt to run our server again we no longer get the error for no module named sql alchemy but now we get the error for no module named flask sql alchemy in which case we'll do the exact same thing pip install flask sql alchemy now if we do the same thing and for some reason we're getting the error that i was telling you about when we added that additional configuration to our application so we set this sql alchemy track modifications to zero for false and it's telling us to explicitly set it to true or false to suppress this warning which i thought we did but let's go ahead and have a look and let's go ahead and see what it's saying see if we have the right name for the configuration variable and that's what i did wrong i had sql track modifications instead of sql alchemy track modification so we'll go ahead and save that we'll exit this and let's try this again and there we go all of our dependencies have been successfully installed so let's go back into our server.pi file and from here we can move on to creating our additional database model so this api is going to be a blog api so the two database models that we're going to need is this user model that we have here so we're going to create a user table and we're going to create a blog post model which is going to be a table for blog posts and we'll do that by doing class blog post and it's going to take in db.model and this db.model is coming from if we go to the definition of db we see that dv is an instance of this sql alchemy class so whenever we create a class for a table we need to take in this db model and we'll continue with adding a table name for this class and we're going to call the table blog post and this table is going to have an id column which is going to contain integer values and this is going to be a primary key and then we're going to have a title for the blog post and this is going to be a string with a maximum of 50 characters and finally we'll have the body and the body can be a maximum of 200 characters the body of the blog post and we'll take a date which is going to be db.date and last but not least we'll have a user id column which will tell us which user this blog post belongs to it's going to be an integer and it's going to be a foreign key from the user table id column and it's not going to be nullable so here you see that this user id in our blog post table is is going to have to be an id from our user table and it's not going to be able to be null and this is the reason that we have to enforce uh foreign key constraints here because if we wouldn't have implemented this portion of the configuration sqlite would just allow us to add blog posts that don't contain valid users but now that we enforce foreign key constraints the user ids that are passed to our blog post are going to have to be user ids that exist within this user table so now that we've added the classes for our database schema let's go ahead and generate and have a look at what our database looks like instead of using the command line tool for sqlite3 to view our schema and tables let's download a dv browser for sqlite which will allow us to view our database via a graphical user interface the db browser that we'll use can be found here at sqlitebrowser.org i'll add a link to the description of this video and once you've accessed this link depending on your operating system you'll download this db browser using one of the links listed below so in my case i'm using mac os so i would use this link here and once we've downloaded our db browser we can actually generate our database we can do this by running the python shell from the command line and creating our database tables based on the models that we've created so we can go ahead and save this file and exit and let's clear this and to run the python shell all we have to do is type in python and to generate our database we want to import the sql alchemy instance which we assigned to the variable database and here server is just the name of our dot pi file which is the name of our module and then db is the variable that we assigned to the instance of the sql alchemy database so once we have that imported we can now access the methods of this db instance and we can just type in db.create all which will create our database by creating the tables based on the classes that we've created in our server file and then we can exit the python shell and if we ls we'll see that our sqlite database file has been created and if we go back into our server.pi file we'll see that in our app configuration for sql alchemy database uri we set the uri to the file sqlitedb.file which is the file that was created when we generated the database so our entire db is going to be contained within this file if we delete this file we're also deleting our database and we can view our database by opening this file using the db browser that we just created so you can start by executing the db browser that we installed for sqlite and once we've opened the db browser the interface will look like this and we can just click this open database and from there we can make our way to our project directory flask api and we'll see our sqlitedb file here and we can just select it and click open and now you'll be able to see both of our tables and if we expand this we'll see all of the columns for our table and if we browse the table we can expand these and this is what our table for our blog post looks like which contains an id column a title column a body column a date column and a user id column and as we can see if we go back into our server.pi file and we go down to our blog post table we can see that this corresponds exactly with the class that we created so we have an id column we have a title column we have a body column and we have a date column and a user id column and this is what i meant when i said that an object relational mapper allows you to interact with the database in an object-oriented way we're creating a class that's representative of a table in an actual sql database so now that we've gotten everything set up for our database we can start creating the routes for the api so we can just say routes so the way that flask works is in order to create a function that corresponds to a route we need to use this app.route decorator and within this decorator we need to pass the rule and the methods and this first one will be a post and in this route we're going to define a function to create a new user and for now we'll just pass because we're just setting up the skeleton for the application so if we go to the definition of route we see that route is a decorator that is used to register a view function for a given url rule so basically what that means is the url rule in this case is going to be this forward slash user so whenever this forward slash user is appended to our url the request is going to be routed to this particular function for create user if it is a post request so what we're going to do is we're going to create a couple of these routes and they're all going to serve their own individual purpose and we're going to create the route function for each of these individual routes in future videos so for now let's just create the skeleton of the api so this rule is going to be sending id and right now you don't need to bother yourself too much with what each of these individual routes and their functions are going to do because we're going to get to them in future videos for now we're just creating the skeleton of the application and this one's going to use the kit method and the function's going to be called get all users descending and again for now we're going to pass and we can do the same thing and change this to ascending id and it will also be a get method and we'll change this to sending and again right now don't bother yourself with what each individual route is going to be used for right now so this here where we're adding in this user id this is just going to allow us to pass a user id to our path and then we'll then be able to use this user id variable within this function because we'll be able to pass it in here so we'll be taking this user id and passing it into this function get one user and the user id is just going to be whatever id we append to this url and let's continue this one will be a delete and we'll change this to delete user and here we're going to create a blog post for a specific user id so we're still going to pass user id to the function and we'll change the name of this function to create blog post this will be a git and we'll change this to user and this will be get all blog posts finally this will be a delete delete blog post and that'll be it for our routes and lastly if name equals main app.run and we want to set debug equal to true and all this is saying is if we're running this server.pi file as our main application then we're going to start our api with debug equal to true and what do i mean by if we're running this server.pi file as our main application all i mean is if we're running it as our main application on the command line we would type python and then server.pi so we're running this server.pi file as our main application then this internal variable is going to be set to equal main because that means that this is our main application because we're running this file directly as our main application when we pass it to this python command so now let's save this and let's go ahead and run this and see if we get any errors and as you can see our server is now running and debug mode is set to on and our server is running on local host port 5000. before we get into linked lists let's start by adding the functionality to our create user route so we can start by removing this pass and this first route is going to be relatively simple but it's going to tell us most of what we need to know about how we'll interact with the orm or the object relational mapper which we discussed in the previous video so we can start by creating a variable to store our request data and although it might seem like this request object is coming out of nowhere it's actually provided by flask and we don't really need to know much about the underlying implementation just know that when we're working with our routes we'll have available to us this request object and what this git json method is going to do is it's just going to parse our request payload as json allowing us to access the parameters via their key values for example if the request contains a payload that looks like this we'll be able to access this bill value the same way that we would access a dictionary value based on its key so in our case this payload is going to be data so we'd be able to access it by doing data name which is exactly what we're going to do so we're also going to create a new user variable and it's going to be an instance of our user class that we created above here so whenever we create a new user we're going to have to do it by creating an instance of the class user so in our case the user has a name which is just going to be data name and an email address and a phone number so just copy these address and with this instance of our user class adding this new user to our database is as simple as doing dv.session dot add and then the name of the instance followed by db.session.commit and this is all we'll need to do to create a new user and once all of this is completed successfully we can just return a response and we'll just do jsonify user created as well as 200 and this 200 is just going to be the status code for our response and the 200 status just means that the request was successful so we can save this and we can run our server again and see if we get any errors and we do not now the server is running and now we can actually test the route and see if it works and to do that we're going to install an app called postman to send requests to our server so to install postman what you want to do is go to postman.com forward slash downloads and i will put a link in the description of this video and you're simply going to want to click this download the app if you want you can use the browser version but i recommend using the actual application version and to download it it's pretty straightforward you're just going to click this and you're going to save this file and you'll simply unzip this file and you'll have the application available to you then and if you're using a mac you might want to move the application that's extracted from this zip file to the application folder once you have postman you can go ahead and run the application and once you have postman open you can just go here and click new and then you can create a new collection and you can just name this collection flask api or whatever you like you don't really need to do a description i'll just hit create and after you've created your collection you should see it here and then you can just expand this and hit add request and here we'll just name the request create user and again we don't need to do a description and we can just save to flask api collection and then you'll have a request within this collection called create user and you can just click that and you'll be presented with a tab that says create user that looks something like this and here it says enter request url and then now it says that we're running our server on localhost port 5000 which is our request url so we can just copy this and then paste it into this request url section and for this create user request we're going to be calling our create user route let me just open another tab here and let's just change directory to flask api and we can just go back into our server.buy again and let's go down so the route that we're working with is this route here and as you can see our rule is forward slash user so we're going to need to append this forward slash user to our url and it's going to be a post request so back in postman we can just put user here so now we have our forward slash user rule and we can change this get method to post and then what we need to do is we need to go down to this body tab and we're going to use raw and we're going to change this from text to json and now we can input our request payload it's going to be named bill it doesn't really matter email test email.com address just a random address 281 street and just a random number for the zip code and then lastly phone and let's just put some random numbers in there so this is going to be our payload and our server is running in this tab we can see that our server is still running so now we can go ahead and try and send our request by hitting this send button here and once we send the request we can see the results some of you guys might have this result section hidden so we can just expand this down here to see the results and as you can see we have a status 200 which is a success response which is okay and it even says here standard response for successful http requests which is helpful and we also have our message here that we return after we've successfully created a new user which is just message user created in json format so since we were able to successfully create this new user we should be able to see the record for this new user in our database so let's go ahead and open up the db browser that we downloaded and make sure everything is working as expected so let's just start the db browser application and once we've started the application we can just go up here and select open database and from here we'll want to traverse to the path of our database file which is flask api which is our application directory and within our application directory you should have this sqlitedb.file which is our database file this file contains the entirety of our database and we can just select this and click open and from here we can go to our user table and we can right click it and then just select browse table and you should see a row for the user that we just sent to request to create so this means that everything is working as expected with our user route so now that we've set up postman and we've created this initial route to create users we can go ahead and move on to the next route which is this route to get all users in descending order and this route is where we're going to make use of linked lists so we're going to come back to the code for this function here after we write the code for our linked list so let's go ahead and save this file and quit and if we ls here we'll see that we have our server.pi file in our database file here as well as our virtual environment and you don't really have to worry about this pi cache and throughout this series for our data structures to separate concerns we're going to create the data structures in separate files so we can just create another file in our directory and we can call it linked lists dot pi and again you don't have to use vim to create the file you can create the file in any way that you choose just make sure that it's in our project directory the same directory as our server.pi file now when we cut up these data structures i'm going to both write out the code for the data structures as well as try to explain how you can visualize the data structures by using blackboard so i'm going to switch between two different methods of teaching to kind of attempt to give you guys a better understanding of what's happening here so if you don't understand what something is after i write out the code for it just try to stick with me i will go into more detail throughout these portions of the tutorial so to start we're going to create a class called node which will initialize with three parameters self data and next node and we'll set data in next node's defaults to none and self.data will equal data which will either default to none or equal the argument passed for data at the time of instantiation and the same for next node it's going to equal next node which again will either be none or the argument passed for next node at the time of instantiation so what do i mean by at the time of instantiation so if we were to create a new instance of node like so we'll just call it node one which is a new instance of node this is us instantiating the node class so in other words we're setting this node 1 variable equal to a new instance of node so this node 1 variable will be bound to a node object in memory and if we instantiate this node without passing any arguments to it we're going to default both data and next node to none but if we were to pass in arguments for data and next node let's say for example we have another node and we can just call this one node two and we wanted this node to be the next node from node one we could instantiate this first node with some data and for our next node we could use the argument node2 and in this case both our next node and our data will no longer default to none self.data will be set equal to the data that we passed and the same for self.nextnode it will be set to the next note that we passed at the time of instantiation which brings us to the meaning of self here if you're new to python self just represents a specific instance of a class so whenever we instantiate this node class we're essentially making a copy of a node object in memory so that means when we set this node one equal to an instance of the node class we're creating one node object in memory which can be referenced by using this node one variable and then we set this node two variable equal to an instance of the node class we're creating another copy of a node object in memory which can be referenced by using this node2 variable so at this point we have two copies of the node object in memory each which can be accessed by using their corresponding variable names node 1 and node 2. so when we initialize with this self parameter it's basically representative of a particular instance of this node class so when we set self.data equal to data it's setting the data value for that copy or object in memory equal to the data that we pass when instantiating and also actually we wouldn't be able to reference this node 2 here without first instantiating it so let's move this here so now we create an instance called node 2 and then we create an instance called node 1 which has a next node that is equal to node 2. so after we create our node class we'll create a wrapper class which we'll just call linked list which will initialize with self only and for this class we'll have a head which we'll set equal to none and we'll have last node we'll set equal to none as well so let's try to visualize what's happening here so if we visualize a linked list it looks something like this and each of these rectangles within this linked list are nodes within the length list and each node has two separate compartments we have this left compartment here which contains the data and which in this case is going to be a string a and then we have this compartment here which contains the pointer that points to the next node and if you look at our linked list class you see that we also have this data compartment here and we have this next node pointer here as well but it should be noted that in python variables are just names bound to objects so this next node variable isn't actually a pointer when this next node variable is initialized it will be bound to the object that it's set equal to so when we create a new instance of node and we pass a next node to it this next node variable is going to be bound to the next node that we passed to it but for our purposes it's okay to think of this next node as a pointer because it will actually help you visualize things better when you think of this next node as a pointer for example let's say that we create an instance of our node class and we'll just call it node 1 and we'll set it equal to a new instance of node and we'll pass a string that just contains the word data as our data and we'll pass none as our next node so what this is going to look like is we'll have node 1 which is this rectangle and we'll have this compartment that contains the string data as our data and then we'll have this compartment which contains our pointer to none and if we were to go ahead and create another instance of node and we'll just call this one node two and it would just be an instance of our node class and we would pass data to this one as well but this time as our next node we would pass in node 1 which would look like this we would get another rectangle here and then this one will also just contain a string that says data but then this one's pointer is going to be pointing to our node one and we can continue to do this to build a linked list that can look something like this but what is this length list wrapper actually for well this linked list wrapper is actually going to help us keep track of the head of our linked list so if you look at this length list image here you see that this first note of the linked list is the head so the first node within a linked list is going to be the head of the linked list and here if we were to just continue to instantiate node objects just randomly throughout an application it'd be quite difficult for us to keep track of which one of these nodes that we instantiate is the head because the only way to check which one of these instances is the head of the linked list is to actually go through each instantiation and then check which nodes are being passed as next node eventually after lots of unnecessary stress we can kind of figure out what the head of the linked list is but we can solve this problem by just creating this linked list wrapper which keeps track of the head of our linked list so whenever we want to add to our linked list we can either add to the beginning of the linked list or the end of the linked list and within this linked list class we would create a method for both adding to the end of the linked list and the head of the linked list so for example if we were to define a method here called insert beginning and it took in self and data we'd basically be able to do something similar to saying node is equal to a new instance of node then we pass in the data and then we can say our next node is whatever our current head is so self dot head and what that would do is say for example this is our current head and we want to add a note to the beginning here this node is going to contain data and it's pointing to our current head so in that case this node would no longer be our head this node would now be our head because we set this node's next node to self.head which is the current head which is this one but once we've done this we need to make sure that we keep our head variable updated so we would then set self.head equal to this node so we'll go self dot head equals node and this is just pseudo code we're actually going to write this out within the application but this is just so you guys can get a grasp of what's happening here when we add to the beginning of the linked list and adding to the end would actually be a different story because we're going to have to keep checking the next node next node next node until we reach a node whose next node is null or none and we'll get to that in a little bit it's one of the reasons why we're going to be keeping track of the last node as well but for now it's only important that you understand how this node is working as well as why we're wrapping it in this linked list class okay so now that we have a general understanding of how our node and linked list classes work let's create a print method within our linked list class so that we can keep track of what's going on so we can just add a new method we can just call it print linked list and we'll start by just initializing a variable to hold the string that will print at the end of the function which we'll call ll string which we'll set equal to an empty string so we'll start by setting node equal to self.head which is going to be the head of our linked list and if node is none that means that this linked list is empty because the head of the linked list is none so if that's the case we're just going to print none otherwise we'll use a while loop to traverse the linked list so we'll just do while node which just means that while node is not equal to none we're going to append to our string ll string plus equals and we'll use an f string because we need to add in node.data and we'll cast this to a string just in case the data isn't already a string and to help us visualize we'll add a visual representation of a pointer and here if our next node is none then we'll just append that next note to the string because the while loop will never get to a note that's equal to none and once this is finished we move on to the next node so we'll set note equal to node.nextnode and after this while loop is complete then we'll just print ll string so let's take a couple of seconds to go over what's happening here so while node isn't equal to none we're going to perform this code and what this code is doing is it's just going to append the data for each node to this string that we're going to print after the while loop is complete and the string is going to look like a visual representation of a linked list actually to make things less complicated we can just remove this and we can take this and we can just put it before the print statement after the while loop and if we do that then once we've appended all the nodes with data to our string we'll always append none to the end of the string because there's always going to be an empty node at the end of the linked list and then we'll just go ahead and print our string so let's see if this is working as expected we'll just create an instance of linked list and then we'll just create some nodes and let's see have one more so this node one here is going to be the head of our linked list so we need to change this to node to point to node two and we need to change this one to point to node three and this one we need to change it to point to node four and this node four is going to be the last node of our linked list so its next node is going to be none and then once we've done that we can set our linked list head equal to node one and then we can just do ll print ll and let's see what happens type in python linked list dot pi and we get our linked lists it looks kind of strange because the data is the same for every single node so let's go in here and let's just add in their corresponding numbers so now you see that we have data 1 data 2 data 3 data 4 and then none so this is our visual representation of the linked list that's being printed using the print method that we just created so now that we have a way to print our linked lists instead of manually creating the nodes and connecting them like we just did we need to add in methods for inserting at the beginning of the linked list and inserting at the end of the linked list so first we'll start with insert beginning and it will take data and this word is wrong insert so to insert at the beginning we're going to do something similar to what we did on the blackboard with the pseudocode we're going to create a new node and it's going to contain the data that we passed and its next node is going to be our current head and then we're going to set our new head equal to this new node so self.head is now going to be equal to new node so let's just go ahead and test that out we'll create another linked list and we'll do ll dot insert at beginning and then we'll put in some data then we'll do ll.print and then let's see what happens and we get our linked list with data inserted at the beginning so let's go back in here and see if we can add to the beginning so before our beginning contain data then we'll have not data so this not data should be the new beginning let's do python and then yeah we have not data and then data and then none so we can continue to insert at the beginning and it's always going to push the current beginning towards the end so we'll just change this to just something random and now we have cow not data data none so our print function and our insert at beginning functions are working as expected so now we need to create a method for insert at the end so let's go ahead and add that and insert at end so when inserting at the end we just want to make sure the linked list is not empty first and actually if the linked list is empty we'll just call the insert at beginning function to make things simple so to check to see if the linked list is empty we'll just do if self.head is none if it is we'll just do self dot insert at beginning and we'll pass to it data which we need to add here as well sorry about that now that that's out of the way so to add to the end of a linked list it's actually going to take oven time because we're going to need to traverse through each node and check if the next node is equal to none and that's how we'll know that we've reached the end of our linked list but for our class in particular we're going to keep track of the last node so that we can reduce the time that it takes to insert a node at the end in the future but if we haven't yet started keeping track of the last node then we're still going to have to use a while loop to traverse through the linked list so we'll do if self.lastnode is none then we'll do our while loop so we'll do node is equal to self.head and we just need to do while node.nextnode node equals node.nextnode and this is going to take us all the way to the end until node.nextnode is equal to none because we're only going to go through this while loop while node.nextnode is not equal to none and for each iteration of this while loop we're going to set node equal to next node so once we get to the last node of this linked list this while loop is going to terminate and then node is going to be set equal to the last node of the linked list so now we want to set the next node of our current last node to the data so node.nextnode equals node and then our data and then none because this is going to be our new last node so the next node of this node is going to be none and now that we know what our last node is we can set self.lastnode equal to the node that we just created which is node.nextnote so now we have a last node so now if we wanted to insert at the end of this instance of our linked list it's going to first check to see if self.lastnote is none but for this instance self.lastnode is set to our currentlastnode so now we can add the code for if we do have self.lastnode set so if we do have self.lastnode we just need to set self.lastnode.nextnode equal to a new node and we no longer have to take oven time to traverse through the linked list to get to the end and insert at the end and we can't forget to set our new last node as well which is again going to be the node that we just created which is self.lastnode.nextnode so with the current way that we're doing things we're only ever going to need to iterate through this while loop the first time we call this insert at end method so for example let's say we go down here and we create a linked list and we do ll insert at beginning and we just insert some data and we do this a couple of times and then we do ll insert at end and then we'll say end when we get to this insert at end we're going to have to iterate through all of these inserts that we did and we can see what this looks like by just going to this while loop and printing say editor node.data then we can just save this and then we can go python linkedlist.pi and you'll see that when we get to the call to insert at end it has to iterate through every node that we called that insert at beginning function on but if we go back in here and we add another insert at end for this next one we're not going to have to iterate through those anymore because after calling insert at in this first time we started keeping track of the end of our linked list so you'll see when we call this again it's still only going to iterate through all of these nodes the one time and if we go ahead and print the linked list we can see that we are indeed having our end and our n2 added to the end so with that in mind this actually means that we can make the efficiency of our linked list even better because to avoid traversing this while loop all we have to do is keep track of our end whenever we insert into the length list and currently we keep track of the end when we insert at the end but we can also keep track of the end when we insert at the beginning because the first time we insert into the linked list our linked list will be empty and when we insert one node into an empty linked list at that moment the end and the beginning of the linked list is the same because there's only one node in the linked list so at that moment we have a linked list that looks like this and when we insert data at the beginning we end up with a linked list that looks like this and when we have a linked list that looks like this the end of our linked list is the head of our linked list as well so what we can do is we can say itself.head is none that means our linked list is empty and if that's the case we can just set self.head equal to a new node that will just contain data and then none for its next and we can also set self.lastnode equal to self.head so this means that from the very beginning whenever we add to our linked list we're going to start off by keeping track of the last node of the linked list therefore we will actually never need to use this while loop so this means that we should never get to this if statement so if we print here last node is none and we save and we run this again you'll see that we never get to that print statement that says last node is none and we're not doing anything different here we're still inserting all of this data at the beginning and then we're still inserting that in for this first time and then the second time and before when we insert it for this first time we have to start keeping track of the last node when we insert data for the first time we automatically start keeping track of the last node therefore we never even have to use the while loop so we'll actually never even get to this code here so we can just remove it so we'll just comment it out for now and we can comment out this as well and let's just do this and save and try this again and we still have no errors so let's take some time to visualize what's happening here so before adding this code here if we were to start with a linked list where the head was none so an empty linked list we would just create a new node with some data and we'd set the next node of that new node to our head which would in turn add a linked list to the beginning here because this new node has its next node pointing to our current head which is none and then the data would be in here and then our head we would set it to our new node so this would no longer be our head our head would now be here so that's what we were doing before we added this code we weren't keeping track of last note at all we were only keeping track of our head so in that case when we went to insert at the end of a length list let's erase this and let's say for example we did insert beginning a couple of times and remember this is prior to implementing this portion of the code so that would leave us with a linked list that looked something like this with this data being here and this data being here and if after that we went on to insert at the end let's say insert at end in that case we would skip this portion of the code because our linked list isn't empty and we're still imagining that we haven't implemented this so therefore we haven't commented out this yet as well so we would end up here if self.lastnode is none and since before implementing this we weren't keeping track of the last node it would be none and then that's when we would have to go through our while loop so we would set node equal to our head and we would just say while our node has a next node that's not equal to none so while our node has a next node that's not equal to none we would just set our node equal to node.nextnode so we would start at our head which is here so this is our head and this is our head's next node and this next node isn't equal to none so our node would then be equal to this node and then this is our next node and it is equal to none so at that point this while loop would terminate and this node value this node value let's do a different color this node value is now this node and its next node is this node so now we set this node's next node equal to this data that we want to insert so we would do node then data and then none so that would make this data replace this none so we would add a node here and then this one would now point to none and that's how we were inserting that in before and as you can see we have to traverse through each node so we have to go from this node to this node all the way until the next node is none then we can add it there because we don't know what the last node is and at that point that's when we are getting our last node and setting it equal to this node dot next node this node.nextnode that we just created and at that point we started keeping track of our last node so now let's erase this and let's say our linked list is still the same length list so at this point if we want to insert and now we know that this is our last node and this is our head so now if we want to insert at end all we need to do is insert at this node's next node so all we would have to do is last node dot next node equals a new instance of node plus our data and then none and we no longer have to traverse through each node to find out what our last node is because we already know what our last node is and this was all prior to us adding this to insert at beginning and prior to us commenting out this while loop section but let's go over what changed once we added this code and commented out this code let's erase this again so in this case if we insert at beginning just say data we'd end up at this here and currently we just have an empty linked list that looks like this it just has none and this none is our head so we end up here if self.head is none which it is self.head equals our new node and our new node's next node is just going to be none so that just means our new node would go here and its next node would be none and this would no longer be our head our head would now be our new node and this is the data so we've updated the head but now as you can see in a length list that only has one node and its next node is none the head and the tail are both going to be the same node because there's no other node after this head node so this would be our head and our tail so that's why we're setting self.last node equal to self.head because we're making the head as well as our last node equal to this node so now whenever we go to this insert at end code we can just add it straight here and then just point this to none this new node that we create we just point it to none so this data will just go right here and then we'd set last node equal to this new node that we just created so this is no longer our last node this is now our last node and even if we come in and insert at beginning we'd still just be adding a new node here and setting its next pointer to the current head then this data would be this data then this would no longer be our head because we're setting self.head to the new node so this would be our new head and at this point we still have our head that we're keeping track of and we still have our last node that we're keeping track of which is why we'll never have to use this code okay so now that we understand why we no longer need this while loop we can go ahead and just remove this portion of the code here and we can also get rid of this so now our insert at in function is a lot cleaner and inserting at the end will also now only take constant time so both our insert at beginning and insert at in methods are of one so we can just save this and let's just ls our current directory what we're going to want to do is we're going to want to open our server.pi file and we're going to want to import our list.pi file and to do that we can just do import linked list so linked list is the name of our file which is the name of our module for linked lists and now we can go down back to this route that we're trying to implement and what we want to do in this route is we want to get all of our users in descending order and to get our users in descending order we're going to start by querying our database to get all of our users and to do that we're just going to create this users variable and we're going to use user.query.all and again this user here is just the user model that we created before so once we get all of our users we can create an instance of a linked list from our module and then our linked list and then we're just going to iterate through our users from the database and for each user we're going to insert at the beginning a dictionary that contains our user data and then we're going to need to return this linked list and to return it we're actually going to need to convert the linked list into an array so we're going to return jsonify all users ll.2 array and we haven't yet added this to array method to our linked list class so let's go ahead and do that so you guys are going to need to traverse to your linked list file again and we're going to add a new method which we'll call to array and it's going to take self and we'll just set array equal to an empty array and if our linked list is empty we're just going to return the empty array and if it's not empty we're going to traverse through our linked lists using a while loop which you all should be familiar with because it's what we've been doing so we'll set node equal to self.head and then while node we'll do array.pinned node.data then node equals node.nextnode and after that while loop is finished our array will contain all of our node data so we can return array and we can save this and now when we're back in this file this return json file all users ll2 array should work and i just realized we probably shouldn't call this array because this is python so we'll just call it to list and here we'll do the same thing and we'll just call this l l and same thing here and also we're going to want to return a 200 here as well the same as the way that we did it when we created a new user we returned a 200 which is a success response and the reason this code is going to return all of our users with their ids in descending order is because this code here this query all gives us the users in ascending order by id and for each user in this ascending ordered list we're going to insert it at the beginning of our linked list so every time we add a user it's going to push back the previous user that we added so that means that if our first user id is one and we insert it at beginning and then our next user id is two and then we insert that at beginning that one gets pushed back and it's going to keep doing that all the way until we get to let's say we have 200 users so in this linked list the user with id 200 is going to be inserted at the beginning last so that means that the user with id 200 is going to be the head of our linked list and the first user user 1 is going to be the tail of our linked list and that's how we're creating a list of users in descending order by using this linked list i hope that makes sense and before we move forward i noticed that there was an error in one of the methods of our linked list so let's go ahead and have a look at that so this should be changed to l okay so now that we have everything situated we can move forward with testing our route and to do that we're going to need to add some dummy data to our database so what we can do is create a new file called generate dummy data and i've already written the script to generate this dummy data because i didn't want it to detract from the concepts that we're trying to learn so what you can do is you can go to this github repository by accessing this url which i will link in the description and here you can just select raw and you can just copy this code and paste it into the file that we just created and then we can save this file and now we have our file to generate dummy data so let's have one quick look at our database before we generate the data so you can once again open this db browser for sqlite and you can select open database and navigate to the directory of our project and within that directory you select the sqlitedb file and open it and we can just browse our table for our blog posts and as you can see we have no rows and the same thing for our users we only have this one user that we added when we were testing our create user endpoint and let's just check to make sure our virtual environment is still running by typing in environment graph virtual environment and as you can see my virtual environment is still running and yours should still be running as well so you should have a virtual environment environment variable that points to the path of our project and its venv folder and once that's done we should be able to type in python generate dummydata.pi and there's no need to panic when we run this we're going to get some errors because there's some dependencies that we still need to install to run this script but we're going to run it just so we can see what we need to install so we'll type in python generate dummydata.pi and it says that there's no module named faker so we can do pip install baker and then we can try this again and this time we get no errors and if we go and check our database now and we check browse table for our user table you'll see that we have a bunch of new users that have been added and if we go back to database structure and we go to our blog post and we select browse table we get the same thing so each blog post has a body and a title and it also contains user ids that exist within our user table so now that we have our dummy data set up we can finally test the route that we created to get users in descending order so to do that we're going to need to run our server and once our server is up and running we need to go back to using postman to send a request so you can select your postman app and what we're going to want to do is we're going to want to create a new request so this is our create user request so we don't want to do anything to change this we want to expand this flask api and hit this view more actions and then hit add request and this request will be called get users descending and of course we don't need a description and it's already going to be saved to our flask api folder so we can just hit save to flask api and now we can open a tab for this request and once again we will copy this url here and paste it here and we need to add our rule here as well so open another tab and then we can go into our server.pi file and the rule for this route is going to be forward slash user and then forward slash descending id so we can just copy this and paste it here and this is going to be a git request so we can leave this method the same and for this request we don't need a body so we can just hit syn to send this request and we got an error and it's a 500 internal server error so that means that there's an issue with our code somewhere so if we go back to our server and looking at our stack trace we can see that at the bottom here in our server.pi file on line 73 in the function get all users descending we have a line that says address is user.address and we're missing an s here in this address and the error is user object has no attribute address because we spelled address wrong so what we can do is we can control c we can go back into our server.pi file and we can go to line 73 and we'll see right here that address is spelled wrong so we just want this to be spelled correctly and then we can save that and then we can run our server again and let's try sending this request again and this time we get a success response a 200 status and as you can see we have our users in descending order by id so descending meaning that the users will be ordered from largest id to smallest id so we have id 200 here and if we keep going down all the way down eventually we get to the last user which is id 1. so now that we know that that endpoint is working we can go back into our server.pi file and we can start on the code for our get all users ascending route so this route is going to be very similar to the above route and since these routes are so similar we can just go ahead and copy this and paste it here and the only thing we're going to need to change is this to insert at end and the reason this is going to work is if this returns all of our users in ascending order and we iterate through our users in ascending order and we insert them at the end of our linked list we're basically just going to be retaining the order of this when we add it to our linked list so actually using a linked list for this route is redundant but the purpose of using it is to help you understand the differences between inserting at the end of a linked list and inserting at the beginning of a linked list so now we can take our rule here and in postman we want to create another request and this one's going to be get users ascending and we'll open another tab and this one's also going to be a get request and we'll go ahead and add in our rule and let's just take our url from here and back in our file here we can just save this and once the file is saved our server should already detect the change in the file so it will actually reload our server so we don't have to restart our server we can just leave it as it is and back in postman we can go ahead and send this request and as you can see we get a success response a 200 status and we have our users here in ascending order starting with the lowest id and ending with the highest id so we can go back into our file and move on to our next route okay so the next route that we're going to be creating is the route to get one user and the way that we're going to do that is we're going to go ahead and create another linked list users equals user.query.all and we'll do all users ll equals linkedlist. linked list and we can just take this paste it here and change this to insert at beginning and we can just go user equals all users ll dot get user by id and we'll pass in user id and we can just return jsonify user with the status 200. okay so we haven't yet created this git user by id so we're going to need to go back into our linked list file and create this method and what we're passing to this method is the user id which is going to come from our url here so we're going to have this rule appended to our url which is going to contain this user id so whenever we append an id to the end of our url when using this rule and we use a get request it's going to know to route that request to get one user and that user id that we append to the url is going to be passed to our function our get one user function which we'll have access to within this function which is what we're going to pass to this method that we are going to implement on our linked list so we can save this file and we can go back into our linked list file and within this linked list class we can go and create the method we'll just define a new method here and we're going to call it get user by id and it's going to take in self and user id and this method's going to be quite simple we're just going to use a while loop to traverse our length list until we find the node that contains the id that we're looking for within its data so we can just set a node variable equal to self.head and then as usual while node if node.data and then within that data there should be an id because if you remember from the route function the data that we added to this linked list is a dictionary and if that's not clear let's go back into that file so here we're creating an instance of a linked list and then in this for loop here we're going to iterate through every user from here and then we're going to insert the user into our linked list by using the insert beginning method and the data that we're inserting is this dictionary here and within this dictionary we have an id key a name key an email key an address key and a phone key and we're checking to see if the user id is equal to the user id that we're searching for when we're using our get user by id method so if we go back to this method we're going to check if the node's data which is a dictionary that contains the key id if that id is equal to this id that we're passing to the method so if that id is user id then we're going to return node.data so we're going to return the dictionary that's stored as the data in this node and if not we're going to keep looking so we're just going to set node equal to node.nextnode and if after the while loop completes we never return node.data it means that the user id was never found within our linked lists so we would just return none and then we can just save this and go back into our server file and go back down to our get one user function and as you can see in this get user by id method we're going to return the user dictionary and that's going to be stored in this user variable and then we're going to return the user variable convert it to json so let's go ahead and test this out so to test it out once again we're going to need to copy our rule here and in postman we can add another request and we'll call this one get one user and save then we can just go to this get one user tab and we can add in our rule so first let's add in the rest of this and this user id needs to change to the id that we want to find so maybe we want to get user with id15 and we have the method set to git and we can just send oh and i stopped my server so let's go ahead and start the server again first so python server.pi the server is now running and then here i can hit send again and in the response i got null so it's saying that the user with id 15 doesn't exist try it with one okay so clearly there's an issue with the code so let's go see what's happening so we can go to the get user by id method and maybe the issue is that we need to convert this into an int and let's save and the server should automatically detect the change in update and then we can send again and now we get the user for id one and let's try it again with 15 and we also get the user with id15 so now we can go back into our server.pi file so now that we can get one user we can quickly add the functionality here to delete a user and for this function we're not going to use the linked list we're just going to query the database to delete the user so we can remove this path and we can just do user equals user.query and now we're going to use the method filter by and we're going to filter by the id equal to user id and we want to get the first record that we find with that id and once we do that we can delete it by just doing db session dot delete and pass in the user and then we can just do db session dot commit and once it's deleted we can just return jsonify and we'll just do an empty dictionary and 200 and we can save and in flask api we can just go add request once again and this one we'll call delete user and save then we can just open a tab for delete user we can take this one and copy the whole thing because it's actually going to be the same url but we're just going to change this from git to delete and let's say we want to delete user one so if we go back into our database and we browse table we see that we have user here with id1 bill his name is bill and we can go ahead and send this request to delete oops and we got an error so let's see and the issue here is that we're trying to delete a user that has blog posts in the blog post table and what that means is if we go check our blog post table within our database you can see that we have records for blog posts that belong to the user that we're trying to delete user id 1 and since we've added a foreign key constraint to the user id column of the blog post table it means that values within the user id column cannot be values that do not actually exist within the user table this is why we're being blocked from deleting the user because we need to cascade the deletion down to the tables that reference this user's id when deleting which just means that when we delete a user any table that references that user should have the rows that reference that user deleted as well and this is actually very simple we just need to go back into our server.pi file and here where we create the relationship to blog post we can just add cascade equals all delete which just means that whenever we delete a user any item in this blog post table that references that user will also be deleted so we can just save this and just to recap we have records within our blog post table that reference user id 1 and we also have user id 1 within our user table so let's try sending this request to delete user id 1 again and now as you can see we get the expected response and if we go back into our database viewer and we refresh this page you'll see that we're now starting from user id 2 and user id 1 bill no longer exists within this table and also if we go to blog post you'll see that the user id column no longer has references to user id 1 because those were also deleted so to start within our project directory we want to create a file called hashtable.pi and within this file similarly to linked lists we're going to create a node class which will initialize with self data and nextnode and this time when we create an instance of node the data that we pass to the instance is also going to be derived from its own class which we'll call data and the data class we'll initialize with self key and value and lastly we will need to create a hash table class which will initialize with self and table size and within our hash table class we'll also implement an attribute called hash table which is essentially a fixed length list and since there's no real way to declare a fixed length list or array in python we can use our table size variable to create a list of none values of the length specified by our table size and i'm going to explain in more detail how all of this is working in just a second just try to follow along with me for now so the next thing that we need to do is we need to define a method within our hash table class which is going to generate a hash value for us which essentially just converts a key into an index in our hash table list this way we can access the value for a key in constant time because accessing an index within a list takes all of one or constant time and again if this isn't making any sense to you just bear with me i will go into more detail in just a second so for this we're going to define a method called custom hash which will take in self and key and initially our hash value will start off as zero and for each character in our key we're going to add to our hash value the integer representation of this unicode character for example the character a's integer value and unicode would be 65 and this 65 is defined by the unicode standard so the character a's integer value will always equal 65. and in python to make that conversion we can use this ord function and just pass in our character so we're adding to this hash value the integer value for each character in our key and the goal is to make this hash value as unique as possible and with only adding the integer values for each character together to create our hash value you can see how different keys can easily add up to the same value resulting in the same hash value for two separate keys so we want to try to reduce that possibility by adding some additional randomness to the creation of our hash value so we can also do hash value equals our current hash value multiplied by the integer representation of our unicode character modulo our table size and at this point we can return our hash value and now that we have our custom hash method we can add a method to add a key value pair to our hash table which will take in self key and value and to add a key value pair to our hash table first we need to create our hashed key by using the method that we just created to convert our key into a hash value and if the index of our hashed key is none we're going to add a new node to that index of our hash table by creating an instance of our node class which takes in an instance of our data class as well as next node and our data class will contain the key and the value that we pass to our add key value method and we're going to get to this else soon but first let's go over everything that we have so far okay so let's take some time to try and visualize what we have so far so we're already familiar with a way to visualize this node here from a previous video's explanation of linked lists so a node will be represented by a rectangle which contains the data and then the pointer to our next node and our data class here is going to be what is passed to our node so with both of these combined we'll essentially end up with something that looks like this we'll have a rectangle for our node and we'll have our pointer to next node and for data we'll have a key and a value so when we create an instance of this node class we're just creating a node that looks like this and when we create an instance of data we're just creating the data within the node which contains a key and a value which can be seen here self.key and self.value now for our hash table when we create an instance of a hash table we're going to initialize it with the size and the reason we're going to need to initialize it with the size is because when we call this custom hash function we want the hash that's created to stay within the bounds of this hash table list that we create for example if we create a list that only contains three items like so this list will only have indexes zero through two so zero one two and if when we create this custom hash it exceeds the indexes of the list that we have and we won't be able to add the value at this hash if it doesn't exist within our list so say for example our custom hash converts this key into index 5. index 5 would be somewhere out here which would not be within the bounds of our list so this would result in an error but when we initialize our hash table with the table size when we calculate our hash value we can be sure to use the module operator to ensure that our hash value doesn't exceed the table size and the reason why this module operator works to make sure that the hash value never exceeds the size of the table is because this modulo operator gives us the remainder of dividing this value by this value and our remainder can never be larger than the number that we're dividing by because if our remainder is equal to or greater than the number that we're dividing by that means that we can divide the number again for example if we have a hash value that is 63 and we divide it by a table size of 10 10 can go into 63 six times and we'll be left with three and if we did the same thing for 69 10 would go into 69 six times and we'd be left with nine but once we get to 70 and we divided by 10 10 now goes into 70 seven times and we're left with nothing so as you can see the remainder is never larger than the number that we're dividing by so coming back to the initialization of our hash table if we were to create an instance of hash table we would pass in the size of the table that we want as the table size and then our hash table would be created by multiplying a list that contains one element none by the table size and this here is just going to produce something that looks like this it's going to be a list that contains five none values and then when we create our hash value this portion of the code makes sure that our hash value never exceeds the table size which ensures that our hash value never equals an index that doesn't exist within our table and also for those that don't understand what this ord function is doing we can use this table here to give you a general understanding of what's happening so in general terms this table gives us the decimal value for each character so for example the character a here its decimal value is 65 so the character a is always going to be 65. so if our i is the character a in uppercase a because as you can see a lowercase a has a different value of 97. but if our character i is in uppercase a then this order is going to return the integer 65 so here 65 is going to be added to our hash value so in this case if our key is apple here we're going to iterate through every character in the key apple and we're going to add to this hash value starting with 97 and then 112 and then 112 again and so on and so forth and that's basically what's happening when we're using this ord function here so what's happening when we're adding a key value to our hash table so it'll be easier to visualize this if we change the way that we write this list out so let's say that we create a hash table with a table size of four and we'll write our list out from top to bottom so we'll have none none none and none and let's just move this so this is our list and the indexes for our list are 0 1 2 and 3. so first of all let's assign a variable to this hash table instantiation and we can just call it ht equals hash table and if we were to do add key value we would do ht dot add key value and we would pass in our key and we'll just say our key is hi and then we would pass in our value and we can just say our value is there so what's going to happen is we're going to create a custom hash out of the key high so our hash value will start off as zero and for every character in the string high we're going to use this ord function on the first character in the string high which is h and as we can see here h maps to the decimal 104 and i maps to 105. so what that means is this ord is going to return 104 for h and 104 is going to be added to our hash value which is zero so our hash value is then going to be 104 and then we're going to set our hash value equal to our hash value multiplied by what ord returns for h which is 104. so it's going to be 104 multiplied by 104 which is going to be 10 1816 and then we're going to use the module operator and we're going to get the remainder of dividing 10816 by the table size in our table size is four so 10 816 divided by four it's just going to come out to 2704 and there will be no remainder so that means this code here is going to become zero so our hash value is going to become zero once again because since when we divide this number by our table size there's no remainder the result of this expression will be zero so our hash value is zero again and then we go to the next character within our key which is i and we can erase this and we know that ord for the letter i is going to return 105 so we're going to add 105 to 0 and that's going to be our new hash value and then our hash value is going to be set equal to our current hash value multiplied by 105 because or it's going to return 105 for the character i remember so we're going to end up with 105 multiplied by 105 which is going to come out to 11025 which we will divide by our table size which is going to come out to 2 2756.25 so our remainder here is going to be one so that means our hash value is going to be one after this for loop finishes so we're going to return one as our hash value so this key value pair is going to be added to index 1 because now our hash key this custom hash is returning 1 as our hash key so our hash key is 1 and if our hashed key index of our hash table is none which it is it's currently none we're just going to set that index of our hash table equal to a new node containing this data which will look like this we can remove this none and remember we're at index one because this list here is our hash table and our index is one so we're at index one and we're going to create a new node which of course is going to be our rectangle in our pointer to the next node and our next node is none because this is going to be the first node that we add to this index so our data is going to contain a key and a value so our data will be high there our key and our value for our data and our next node is going to be none because this is the first node that we're adding to this index and the reason we're using a node here which is essentially the head of a linked list is because there's still a chance that two different keys result in the same hash which we would call a collision so say for example we have this high key which hashes to index one and we have another key that hashes to the same index one so if that collision happens what we're going to do is we're going to go to this else here so this if is if the index is none then we can just add the node right because there's nothing there but if there's something there that's when we get to this else and if there's something there we're going to have to traverse the linked list until the next node is none and we're going to have to add that node to where none is and point that node to none and in this particular case when we do have to traverse the linked list within our hash table our insertion is no longer constant so the idea here is to reduce the possibility of having collisions so that most of the time when we do an insertion it's at an index that contains none but with our hash function in particular there's a pretty high probability that we will have collisions so this isn't a very performant hash table implementation but for our purposes to learn how hash tables actually work and how they're implemented it doesn't actually matter as long as you understand the concept then i think that we're fine so next we'll move on to coding what happens in this else block okay so now it's time to move on to what we'll do if the index specified by our hashed key is not none so if it's not none that means that there's already a node in that location so therefore we have a collision and we're going to need to use a length list at that particular index to store additional values so to do that we're going to start with the head of the linked list which is the first node at the specified index so we're going to just set node equal to self.hash table and then our hashed key so this is essentially acting as the head of our linked list and then we'll traverse the linked list by using while loop as usual so while node.nextnode so as long as there's a next node for our current node we're going to set node equal to node.nextnode and we'll just keep doing this until we get to the last node of the linked list so this while loop will stop when the next node is none and that means that our current node is the last node of the linked list so we don't need to do anything else to traverse to the end of this linked list so once the while loop is complete we can then set node.nextnode which in this case when the while loop is complete the next node to our current node will be none so we'll set that empty space to a new node which will contain our data and its next node will become none so now that we're able to add a key value pair to our hash table we want to define a method to get the value for a specified key and we can just call this one git value it'll take in self and the key and again we're going to need to get our hash key by using our custom hash method and passing in our key and i'm not sure if i clarified this before but this custom hash method it will always return the same hash for a given key and that's very important for our implementation to work the same key should always produce the same hash if there's a chance that the hash produced from the same key could be different then this wouldn't work at all because in instances where we need to actually retrieve the value that we stored in the hash table we'd need a way to convert the actual key back into the hash to be able to locate the data that we stored in the first place and then we're going to check to see if that key exists within our hash table so we can do self dot hash table hashed key is not none then we can set our node equal to self dot hash table hash key and then we want to see if this particular node has data in its next node because if it does that means that there's more than one node stored at this particular index of our hash table and if that's the case we need to check to see which one is the actual key that we're searching for so if node.nextnode is none then that means that there's only one node stored at this index so we can just return the data for the current node but if that's not the case then we're going to have to traverse the linked list at the index so if the key passed to the method is equal to the key within our data we'll return the value for that key but if not we will continue to traverse our linked list and since this while loop will only iterate as long as note dot next node is not equal to none for the final node we will need to check to see if key is equal to node.data.key and if it is we'll return node.data.value but if it's not that means that the key passed to our method doesn't exist within our hash table so at that point we can return and just so we can see that everything is working as expected we can create our own print table method let's just try to make this look intuitive and let's go ahead and see what this looks like so we'll create an instance of our hash table and we'll pass it 4 for the table size and then we'll do ht dot add key value and let's just do hi there then let's do ht print table and let's save and see what happens and as expected we have a table size of 4 and at index 1 we have our key and our value let's go back in here and add a couple more values so actually let's just leave them like that and as you can see since the key high always hashes to index one if we add multiple sets of data with the key high to our hash table it will all get stored in a linked list at the same index so we can go back in here and try with a different key and save and run we see that the key dog gets hashed to index zero so yeah that is a general overview of how to implement a hash table in python again you should keep in mind that this implementation isn't very efficient but the point is to gain a general understanding of how hash tables work and how they're implemented so for starters we're going to need to import our hash table module by going back to the top of our file and doing the same thing that we did for our linked list but instead we're going to use the name of the hash table file so once we've imported our hash table module we can head down to our create blog post route and start adding the code for this create blog post function so we can remove this path and once again we're going to need to get the data from the request by using this request.getjson method and after we retrieve that data the first thing that we're going to want to do is we're going to want to make sure our user is it actually a valid user that exists within our database because if you remember if we go back up to our user model we can see that our user id column requires that user id come from our user table and if this is not the case we'll get a foreign key constraint error so in order to check if our user exists we're just going to query the database for the user that's passed in the request so we can just set id equal to user id and if you remember our user id is passed to our create blog post function via our url rule so we want to query the first user with this user id so we're going to need to add here first and then we just need to do if not user and then we'll just return jsonify message user does not exist we'll also want to return 400 and a 400 response just means that the client's into bad requests so in that case the client would need to send another request with a user that actually exists and once we've made sure our user exists within our database we can now start to create a blog post for that particular user so we'll start by creating our hash table and it's just going to be an instance of hash table from our hash table module and we'll just use the size of tin and we can start adding the values to our hash table by using our add key value method that we created in the last video so we're going to want to add all of the parameters to create a blog post so we're going to need a title and we're going to get that from the request data we'll do the same thing for our body our date and our user id and the date actually won't come from the requests we're going to get the date by using this now variable and if you're unsure of where this comes from if you remember from i think the first video we created this now variable which is just date time dot now and this date time comes from this import here where we imported from date time import date time and our user id is going to be from the user id in our url so now that we've created our hash table containing our data let's go ahead and print this hash table to see what it looks like using our print table method that we created in the last video and we can go ahead and save this and start up our server and now that we've started up our server we need to go to postman and create a request to create a blog post so once you have flask opened up you can go back to our flask folder and you can open it and you'll see all of our previous requests and we want to create a new post request for creating a blog post so we'll just duplicate this one and we'll just rename it create blog post and our rule is going to be blog post and our user id that we want to create the blog post for so we'll just do user id one and then we need to go to our body and since we duplicated the create user post request we still have this json data here for our request body so we can just change the keys and values within this request payload and all we need for this payload is the title of the blog post and we can just call this post one and then we need the body of the blog post and we can just change this to this is a blog post or something like that and we can remove these two and we also want to remove that and then we can try to send this and we get user does not exist and i think that's actually because in one of the previous videos we deleted user id 1. so let's check our database to make sure so once again you want to open the db browser for sqlite and then open database and then navigate to our project folder and then once you're in our project folder you can open this sqlite db file and let's browse our user table and yes we don't have user one it starts at user two so let's just use user two and also let's have a look at our blog post table as well and if we go all the way to the bottom here and we'll see that our latest blog post is this blog post here so when we add a new blog post there should be another blog post following this one with id 201 so let's change this to user 2 user id 2 and then send the request again and we get an error here but it's expected because we haven't yet finished the code for the route we just wanted to print our hash table to see what it looks like so we sent a request to the route to execute the function so if we go here you see that we have our error and it says that the view function did not return a valid response and that just means that the function for our route is supposed to return a response but we didn't return anything yet so that's why we're getting this error but also before the error we were still able to print out our hash table and as you can see we have a body a date and a title and actually we have title twice so there's something wrong here so let's go back into our server.pi file and see what's happening so here the key for user id is still title so that's my bad change this to user id then save then run our server again and send the request again and now we can go back up to our hash table and we see that we have user id at index 0 and it's 2. then we have our body and our date are being hashed to the same index so we have a linked list here containing two nodes and then last but not least our title got hash to index three so as you can see with our hash function for our hash table there's a high probability that keys will be hashed to the same index so this is why this hash table in particular isn't very performant because the hash function isn't very efficient but it's actually good that we're getting the opportunity to work with an inefficient hash table implementation because it really helps you to understand the most important things that need to be taken into consideration when creating your hash table implementation because whenever we have keys that get hashed to the same index in this list that means that whenever we need to access a key that's in a linked list at any given index we're going to have to traverse in nodes within being the number of keys added to that particular index so when we retrieve data that's contained within these linked lists it's still oven as opposed to when we retrieve data for these indexes that only contain one node which takes constant time so as you can see the more we can avoid this the more performant our hash table will be so ideally we want a hash function and a table size that makes instances like this very rare but i really hope this is helping you guys to understand the core concepts of what's happening behind the scenes with hash tables so let's go back into our server.pi file and finish our function so we no longer need to print our table and actually let's go ahead and test this out with printing the individual keys within our hash tables so we can do ht.getvalue and we can pass in the key that we want to get the value for and we can do this for all of our keys so we'll do body date user id let's go ahead and save this and run our server again and then we can just send this request again we're going to get an error and as you can see it printed out our title post one it printed out our body which is this is a blog post it printed out our date time and it printed out our user id so now that we know that that's working as expected we can go ahead and go back into our server.pi file and we no longer need this and now we can just move forward with creating our blog post now creating a blog post is actually pretty straightforward we can just create a variable called new blog post and we have to instantiate a blog post and again we're using our get value method to actually return the values and then we could just do db.session.add and then the new blog post instance that we just created and then we can just commit the session and sorry this should be session and then once that is done we can return jsonify we'll do message new blog post created and this is going to be a success response so we'll return 200 and let's save this and see if it works python server.buy servers running and let's send this request and we get a success response new blog post created and now let's check our database to see if our blog post is actually stored within the database so in the blog post table we can refresh and we can go back to the bottom of the table and you'll see here that we have a new blog post with id 201 with our title post one and our body this is blog post and our date and our user id now to start in our project directory we want to create a file called binarysearchtree.pi and within that file similar to our linked lists and hashtable implementations we want to create a node class and the initialization parameters for this class are going to just be self and data and we'll set self.data equal to data and within a tree structure instead of the node only pointing to a next node it's actually going to point to a left and a right node and don't worry if you're having a hard time visualizing this we'll take some time to go over what this looks like in just a second but for now just know that an individual node will point to both a left node and a right node and we're also going to want to create a wrapper class for our binary search tree and this class will just be initialize with self and our tree structure will need a root node which is the top node of the tree so our root node will have no parent nodes and again we're going to go over what this would look like in a visualization soon and next and most importantly we're going to want to define our methods for our insertion and for our insertion methods we're going to need to write some recursive code so if you're relatively unfamiliar with the way that recursion works i have some videos that can help you to visualize recursion which can be accessed by clicking the link currently displayed on your screen so to start we can just define our insert method which is going to take in self and the value that we want to insert and the first thing we'll want to do is check if our route is none and if this is the case this just means that our top node or the first node within our tree structure is none which means our tree is empty and if that's the case we'll just set our root equal to a new node containing our value and if we go back to our node we see that when we create a new node and we pass in the data the left node and the right node are both set to none so when we add this first node to our tree structure it's only going to contain a root node and the root node's going to point to none for both its left node and its right node so it will be a tree structure that only contains one node so far and that's if we're inserting a value into an empty tree structure else if our tree is not empty we will need to use a recursive function to insert into our tree and this is because we'll essentially need to find an empty node to insert our value into so we haven't yet created this method but let's just write it out we'll just call it insert recursive and the reason we're starting this method with an underscore is because this method should only be used by our insert method so basically this insert recursive method is a private method that belongs to our insert method we're going to pass in the value and the current root so now we can go ahead and write the code for this method and the way that a binary search tree works is the node's left subtree so that is the tree that expands from the node's left node should only contain values that are less than the node's value and the tree's right subtree which is the tree that expands from the node's right node should only contain values greater than the node's value which results in the nodes left and right subtrees also being binary search trees and i know that this is quite difficult to understand with just me describing the way that a binary search tree should look but just bear with me we're going to go into more details soon but with that in mind if the value passed to our insert recursive method is less than the past nodes data we're going to insert that value in the past node's left subtree so if value is less than node.data we're going to insert value into node's left subtree and if node.left is none then that means we can just insert the value into node.left so if node.left is none and node.left will just equal a new node containing our value else if node.left is not none then that means that node.left contains a node with a value and that node can also have a left and a right node so we're going to need to call our recursive function again because we would want to do the same exact thing for the left node we would want to make sure our insertion goes into the left subtree of the left node if it's less than the left node or the right subtree of the left node if it's greater than the left node so we'll just do self.insert recursive and again we'll pass in the value and this time we would pass in node.left and that's what we would do if value is less than node.data but if value is greater than node.data we would do the same thing but this time we would do it on node.write so we can do l if value is greater than node.data we'll check if node.write is none and if it is we'll just set node.right equal to a new node containing our value else once again we would call our insert recursive function passing in our value and node.right and last but not least else we would just return and this is because if the value isn't less than node.data and the value isn't greater than node.data then that means the value is equal to node.data so our else would be if the value is equal to node.data and if the value is equal to node.data that means that the value is already contained within our tree and a binary search tree shouldn't have duplicates so if that is the case we're going to do nothing here so now let's take some time to try and visualize what's happening here okay so let's start by visualizing what would happen if we create an instance of our node class so we can imagine that we create a variable node and that variable is going to be an instance of a node and we'll pass in some random data so let's just say the number 15. and this instantiation is going to look something like this we'll have a node here and it will contain 15 and then we'll have a left and a right left right and these will also be nodes which will contain none so as you can see here self.left is going to be none and self.write is going to be none as well and then our data our actual node is going to be 15. so this is how we can visualize an instance of a node so let's go ahead and erase this and see what it would look like if we create an instance of an actual binary search tree so let's say we call our binary search tree bst and we set it equal to an instance of binary search tree this is going to give us an empty binary search tree with the root set equal to none and the root is just the first node within the tree so a tree might look something like this this here is our root node and in our binary search tree if this root node is empty then that means that the entire tree is empty let's just draw this again so now that we've created an instance of binary search tree we have an empty binary search tree here now let's say we want to call our insert method and pass in the value 20. we're going to end up here at insert and the value is going to be 20. and if self.root is none which it is it's empty then self.root's going to become a new node with that value 20. so this is going to become 20 and this new nodes left and right are both none so the left is pointing to none and the right is pointing to 9 as well and for none we just won't put anything into the node and here's our root left right now let's say we insert another value and this time we'll insert one so what's going to happen is we're going to end up here again and this time our root is not none so we're going to move on to this recursive insert so we'll end up here with our value being 1 and we're going to pass in the root so our node here is going to be our root which is 20. and we're going to check if our value 1 is less than our node which is our root 20. and if it is it means that it needs to go into our node's left node because as explained before in a binary search tree a node's left node has to be less than the node and the node's right node has to be greater than the node so if value is less than node.data so if 1 is less than 20 and if node.leftnode is none which it is then we're just going to insert that one into the left node and then we'll continue with another insert and this time we'll insert two and we're going to end up here and root is not none so we're going to call the recursive function again passing in the root and our value 2 and this time we'll end up here with our node being root and our value being 2 and our value is less than our root which is 20. so 2 is less than 20 but this time our left node of our root is not none it's one so now we need to call the recursive function again this time passing in our two and our left node which is one so we end up back up here with our value being 2 and our node being our left node now which is 1. so now 2 is not less than 1. 2 is actually greater than 1. so that's going to bring us here 2 is greater than 1 our left node is 1. and this node's right node is none so we'll just add our 2 there so here we're just going to add our 2. and let's do another vst insert and let's do 30. so now we'll end up here our roots not none so once again we pass to the recursive function our value being 30 and then our root so we'll end up here again now our value is 30 and our node is our root node which is 20 and 30 is not less than 20. 30 is greater than 20. so we'll end up here and our right node of our root node is none right now so we can just add this 30 here and this would just go on and on and our root nodes write node will always contain a value that's greater than our root node and our root node's left node will always contain a value that's less than our root node and the same thing for these child nodes this left node's right node will always contain a value that's greater than our left node and this left node's left node will always contain a value that's less than our left node and it would just keep going that way so for example the value here would have to be less than 1 and the same for here the value here would have to be less than 30 and the value here would have to be greater than 30. and you're going to see why this is necessary when we're actually implementing our binary search method now really quickly i want to go over something that is important for you all to understand that is that the order in which we make insertions into the binary search tree matters and it will impact the performance of our tree currently if we were to try to search this tree for the node containing the value 30 we'd be able to leverage our root node as a midpoint and we'd be able to completely avoid traversing any node to the left of our root because we know that any node to the left of our root or within this left subtree will be less than the value 20 our root value which will therefore be less than the value 30 which would leave us with the right subtree to traverse to find the value 30 without ever needing to traverse the left subtree now if this is confusing to you i suggest you watch my video on how binary search works which you can access by clicking the link currently displayed on your screen but continuing with my point the reason that the order in which we make insertions into the binary search tree matters is because the order of insertion impacts the structure of the tree so currently with the order in which we've made our insertions we have a balanced binary search tree because the height of our roots left subtree which is 2 1 2 differs from the height of our roots right sub tree which is 1 only by 1. so that is the height of our left subtree is 2 and the height of our right subtree is 1 and 2 minus 1 is 1 so the difference between our two subtrees is only one which makes this binary search tree balanced and it's not within the scope of this series but it is something that you will need to become familiar with as you go deeper into working with binary search trees but continuing with my point the reason that the order in which we make insertions into the binary search tree matters is because the order of insertion impacts the structure of the tree so with this insertion order that we currently have we are left with a balanced binary search tree but if we were to change the order of insertion we could be left with a completely different tree structure to demonstrate that let's insert these same values into our tree but this time in order from smallest to largest so we can start by just erasing this current tree structure and we'll leave this here for your reference but this is no longer the insertion that we're using to create our tree so let's create our new insertion here so we'll do bst dot insert and this time we'll start with one and what's going to happen is our tree is null so one is going to become our root so we'll just have one as our root node and then we'll do bst dot insert and this time we'll insert 2 and we'll end up here and then we'll go down to our recursive and we'll pass in the value 2 and our root which is 1 and then we'll end up here our value two is greater than our root which is one and our roots right node is none so we would just add to our roots right node the value two then we insert again and this time we'd insert 20 and again we'd end up here insert recursive value 20 root 1 and our value 20 is greater than our root but our right node already contains a value so we would insert again this time passing our right node and our value 20 and we'd end up back at the top here and now our right node is the node and our value is 20 and our value 20 is greater than our right node which is only two and this node's right value is none so we would just insert that 20 here so we'd end up like this and then last but not least we'd insert our 30 and we do the same thing we'd end up here eventually leading us to adding our 30 here now as you can see this tree structure here is very similar to a linked list that is to find 30 we would need to traverse through every node so we would have to go to this node's right node this node's right node this node's right node and finally arrive at 30 which would make searching this structure in particular take linear or o of n time so with this example you can see how insertion order can have a substantial impact on the performance of our binary search tree now we won't be getting into it in this tutorial but this is something that we can manage by coding our binary search tree in such a way that it is self-balancing which would therefore make it an avl tree or a self-balancing binary search tree but this is out of the scope of this series for now it's only important that you understand that the tree structure will differ depending on the order in which we make insertions and that in turn will affect the performance of our tree so let's move forward with adding the rest of the methods to our binary search tree class okay so before we add our search methods into our binary search tree class let's go back into our server file and set up our route and actually this rule should be blog post and then blog post id so this route is going to be used to retrieve one blog post based on its id and we'll change this also to blog post id and we'll go ahead and remove this pass and the first thing we're going to do is we're going to query all of our blog posts by doing blog post dot and what this is going to do is it's going to return to us a list of blog posts in ascending order and we're going to insert those blog posts into our binary search tree and we're going to use the search method on our binary search tree to search for and retrieve a specific blog post and our binary search tree search and insert methods are going to be based on our blog posts id so if you remember nodes within our binary search tree have to be inserted in a particular way such that a node's left node can't be larger than the node and the node's right node must be larger than the node and the value that we're going to use to determine this is our blog post id and if you remember if we insert into our binary tree in ascending order we're essentially going to get a tree structure similar to a list and there are actually only a couple of ways for that particular linear tree structure to be produced and that is if we insert nodes in ascending order and if we insert them in descending order because as shown in our example when you insert nodes in order from smallest to greatest we're just going to keep adding nodes to the previous node's write node which will result in a list like structure and the same thing would happen if we insert nodes from largest to smallest but in that case the list like structure would be in the other direction but it would still be a list like structure so our way to solve this is we're going to attempt to create a more balanced tree structure by randomizing our inserts so basically we're going to take this ascending order by id blog post list and we're just going to shuffle it using this random module and we need to import that random module so let's go here and do import random so now our blog post list will no longer be in ascending order it'll be in a completely random order and when we iterate through it and add it to our binary search tree our tree structure will also be randomized and with this random tree structure we have a better chance of getting a balanced binary search tree which in turn will increase the overall performance of our tree so now we also need to import our binary search tree module so we can go back up here and similar to our hash table we can just do binary search tree and we can create a binary search tree instance and we can insert into our tree by doing for post in blog posts bst.insert and we're actually going to insert dictionaries as our individual blog posts so we're actually going to need to go back into our binary search tree insert method and make some changes so we will do id and that's going to be post.id and we need title body and user so let's change this to title and same here and once we've generated our binary search tree we can create a post by just doing vst.search which we have not yet implemented but we will and search is going to return the blog post of the past blog post id and the idea is for our binary search tree to be a balanced tree so that our search takes logarithmic time and lastly we're going to do if not post because our search method is going to return false if the blog post for the corresponding id is not found and if that's the case we're going to return jsonify post not found and if the post is found we'll just return jsonify post so let's go ahead and save this and go back into our binarysearchtree.5 file and here we're going to need to make changes to our insert recursive so we're going to be changing this value to data because we're no longer inserting just a single value we're inserting a dictionary and when we do these comparisons we're going to be comparing the ids within the dictionary so this would be changed to data id and this would be id as well so now we're comparing the past data's id to the nodes data's id here data same for here and also for this insert method we're going to do the same thing data data data so let's go ahead and see if this works so we'll save here we'll run our server and then we'll go and add another request to postman to get a single blog post based on its id so once you have postman open once again we can go to our flask api folder and hit add request and we'll just call it get blog post and save to flask api and we'll go to get blog post then our url and this is just going to be blog post and an id so let's just do five and let's go ahead and send this request and we get an error binary search tree has no attribute search because we haven't yet implemented our search method so let's go ahead and do that before we move forward so binary search tree so our search method is going to be fairly similar to our insert method in that it's going to be a recursive method so we'll define search and we'll take self and blog post id and let's change this and the blog post id that we get from the url is going to be a string so we're going to want to convert it into int because when we're comparing it to the blog post id within our data it's going to be compared to and we'll do blog post id as an int is our new blog post id and then self dot root is none we're just going to return false because if that's the case it means our binary search tree is empty so of course a blog post cannot exist within it but otherwise we're going to return self.underscore search recursive similar to the way we did our insert this search recursive method is going to be a private method that belongs to our search method and we're going to pass in the blog post id and self.root so now let's add this search recursive method it's going to take blog post id and node and since this is a recursive function we need a base case and our base case is going to be if the node passed in left node and right node is none then we're going to return false and first we'll check if our blog post id is equal to the current node's data's id and if that's the case then we'll just return the current node because that means that we found our node so if blog post id is equal to node.data id and just return node.data but if we're not so lucky we'll need to traverse the tree so if blog post id is less than node.data then we'll check to see if the blog post id is equal to our node's left node's data id so if blog post id is equal to node.left.data id if that's the case we can just return node.left.data but if it's not the case we're going to return self dot search cursive our blog post id and this time our left node so again this is similar to our insert and we're going to do the same thing if blog post id is greater than node.data id and if blog post id is greater than our node data's id then that means we're going to search the write subtree so if blog post id is equal to node.write.data id and we'll just return node.right.data but if not we'll recurse down our write subtree by passing in the blog id and node.write node so let's take a couple of seconds to go over what's happening here so if we can't find our blog post id within our binary search tree we will reach this base case which will just return false meaning that we couldn't find it and if our root node is in fact the data that we're searching for then we'll just return that root node but if our blog post id is less than our root note then we're going to traverse the left subtree because the right subtree will only contain values that are greater than our blog post id and then we check to see if the top node of our left sub tree is the data that we're searching for and if it is we'll just return that node but if not we're going to recurse down that left subtree and the same goes for if our blog post id is greater than our root node's data if that's the case then we're going to traverse our right subtree because the left subtree will only contain values that are less than our midpoint which is our root node so if the top node of our right subtree is the data that we're searching for then we can just return that but if not we'll need to recurse down our write subtree and that's going to be our search method so let's go ahead and save this and let's try running our server again and in postman let's try sending our requests to get blog post with id5 once again and we get post not found so let's check our database and see if we have a blog post with the id5 so again you want to open your db browser and go to open database and then open your db file and let's go to blog post browse table and we do in fact have a blog post with the id5 so there's something wrong with our code so let's go back into our server.fi file and let's see what's happening here okay let's go into our search method and have a look ah i see so unreachable code because this returned we didn't add the proper indentation so this should be here and now let's go ahead and save and let's run our server again and back in postman let's go ahead and send the request for blog post with id5 again and we get our blog post and we get our body our id our title and our user id let's try it with another blog post let's do 199 and we get a blog post for id 199 and now let's try it for a blog post that we know does not exist so we can just put in some random numbers here and we get another error so let's see what's happening let's close our server and let's go into binarysearchtree.pie sorry about that so this was a pretty big oversight on my part so we're going to remove this here and we're going to add to this portion and node.left is not none and we'll do the same thing here but we'll do if node.right is not none and then we need to return false here so what was happening was we were trying to compare the blog post id to node.data of a left node or a write node which was actually equal to none so there was no way to access the data of none so now let's save this and run our server again and in postman we can try to send a request to retrieve this blog post with this random id that we know doesn't exist once again and this time we'll get post not found and if we put an id that does exist let's say 200 we'll get the blog post and let's take this a step further and just put a really random long number and send it and we get post not found and now we've created our route to retrieve a blog post for a particular blog id and we've made use of our binary search tree to search for and retrieve that particular blog post and just really quick let's go into our server.pi file and here where we did our last route which made use of our binary search tree the definition of this function get all blog posts is actually wrong so let's go ahead and change this to get one blog post and we can save this and now we're going to create a new file for our queue implementation and we'll call it custom queue.pi and to start off our queue we're going to create a class for a node and this is going to be the same node class that we use for a linked list and actually our queue is basically just going to be a linked list where inserts and removals are done in a first in first out order and we'll go deeper into what that means in just a second so let's just go ahead and define our node so if you've been watching up to this point you should be familiar with this node class next we'll add a class for our cue and for our cue class we want to keep track of the head and the tail and the head is just going to be the head of our linked list of course and the tail is going to be the last node of our linked list and to insert data into the queue we're going to define enqueue sorry and enqueue will only ever add nodes to the end or the tail of our linked list so you can just think of it as a line of customers at starbucks or something like if you get in line like new customers can't just go to the front of the line just like a new node can't just be added to the head of this linked list a new customer would have to go to the end of the line which is what this enqueue method is going to do it's going to add a new node to the end of our linked list and to do that first if our queue is empty both self.tail and self.head are going to be none so if self.tail is none and self.head is none and if that's the case the node that we're inserting is going to be both our tail and our head because there will only be one node in our list so it'll be self.tail equals self.head which equals a new node containing our data and it's going to point to none and then we'll just return so this is what we'll do if our queue is empty but if the queue isn't empty we want to add our new node to the last node's next node so self.tail.nextnode is going to be equal to a new node which will contain our data and it will point to none because this will be our new tail so it will be set to our new tail so self.tail is going to equal self.tail.nextnode which is the one that we just created here and then we'll just return now that's how we're going to add to our queue now we need to remove from our queue as well so we need to create the method to remove from our queue so this is going to be called dq so define dq self and dq is only going to remove from the head of our linked list so keeping with the starbucks example the front of the line the person that's at the register making their order that's going to be the first person removed from the line and it's going to be the same with this queue notes can only be removed from the queue from the head of the linked list or front of the line so that means if self.head is none then that means that our queue is empty so we'll just return none and if our queue is not empty when we dequeue we're going to want to return the node so we'll just store it in this removed variable so our self.head our current head is going to be set to our remove variable and then we'll set our new head self.head is equal to our current head self.head dot next node and that's how we're removing from the queue we don't need to worry about allocating memory or anything like that because python has garbage collection so all we need to do is change what node our head is pointing to and next itself.head is none which means that if when we change where our head is pointing to it ends up pointing to a next node that is none that means that the head of our q was also the tail of our q which means that if we dequeue that last node then our length list or our q is now empty because the only node in this linked list that will have a next node pointing to none is going to be the tail right so if after completing this our head is none then that means that our linked list is now empty so we need to update our tail as well to point to none so we'll just do self.dale equals none and then lastly we want to return the node that we removed from the queue so we'll return removed and it's as simple as that a queue is just a linked list where we control insertions and removals in such a way that inserting and removing from the linked lists happens in first in first out order so let's take a couple of minutes to try and visualize what's happening here okay so let's take some time to try and visualize our cue so let's do a quick refresher on how we visualize our node we're going to visualize our node like this our data and our pointer to next node and of course this node can point to another node which can point to another node essentially creating a linked list and that's one thing that you should understand about a queue a queue is essentially just a linked list it's a linked list with certain specifications for how we insert and how we remove nodes from the linked list so let's just go over a quick example of adding nodes to our queue and then removing them so let's erase this and let's go ahead and create an instance of a queue which we'll just call q and it's always weird spelling the word q and then once we have an instance of the q we can do q dot n q some data and what that's going to look like is we're going to end up here and if self.tail is none and self.head is none then self.tail equals self.head equals our node which means that we're going to add a node here with our data it's going to point to none because as you can see it's a new node and it's going to point to none and this node is going to become both our head and our tail and i apologize for this so then we can come in and do q dot in q once again this one will do data two and what's going to happen is we're going to end up here again and we're not going to have to go through this because we don't have an empty queue so we're going to end up here self.tail.nextnote is going to equal our new node so in a queue we're always just going to add to the back of the queue it's just like a line at starbucks you can't just jump to the front of the line and buy your fancy coffee you have to wait in the line full of other starbucks coffeeers or whatever so what we're going to do is we're just going to do self.tail.nextnode equals a new node so this is our tail right so the tails next node is just going to be this new node with data 2. and it's going to point to none and let's add another one maybe somebody else wants to get some coffee we'll call this one data3 of course and we'll end up here again and we're just going to add it to the back of the line simple right oh and i'm sorry i forgot so this tail no longer points to this one because after we added it to the back of the line we set self.tail equal to self.tail.nextnode so self.tail.next is this node so this tail is now going to point here i hope that didn't confuse you because that was before doing this okay so now we're back to doing this and we'll end up here and we're going to do self.tail.nextnote equal to a new node so our tails next node is going to be equal to a new node and that one's going to be data 3 and it's gonna point to none this is none again sorry about that all right so now that we've created our starbucks line oh sorry once again i forgot to change the tail so now our tail is going to point to here so this is our last person in line and this is the person in the middle and this is the person at the front of the line the head okay so now what we want to do is see how dq works so dq works like this we're just going to do q dot dq and of course we're not going to pass anything to dq because we have no control over what gets removed from dq because it's always going to remove the head of our list so dq we're going to end up here if self.head is none we're going to return none of course because that means that there is no line there is no queue and we're going to store our head in the removed so we can return it and then our self.head is just going to be equal to self.head.nextnode so all we're going to do is we're just going to move this from pointing to that head to pointing here and we're just going to leave this here and eventually this will be garbage collected so our new head is this and here let's let's actually let's let's step through so we can get to this portion so you can see what's actually happening here so let's do q dot dq again really bad at spelling q and when we dequeue again we're going to set our head to this one because once again we do self.head as equal self.head.nextnode so it's going to be equal to this one so now our head and our tail are both the same node and let's just pretend our garbage collector came along and garbage collected these so now this is what we're left with our head and our tail are both the same node now at this point if we dq again q dot dq if we see here our next note is none and we're going to set our self.head to our next node which is none so let's erase this and let's change it to 0.2 this none so now our head is set to none but our tail is still pointing to this node here even though this guy was actually removed from the queue and as long as this tail is pointing to this node here this node will never be garbage collected either so what we need to do is once our head gets set to none if self.head is none so if if we moved our head to be set to none like we just did self.head is going to equal none right our head equals none if that's the case we need to set our tail to none as well because this tail pointing to this is no longer accurate our tail is now none as well because there's no longer anything left in the queue so at this point we're going to move this to point to none and then this guy is going to get garbage collected he's going to the trash so now both our head and our tail are pointing to none which means that our q is empty and that's how we can visualize how nodes are added and removed from our queue and how we can visualize our queue in general okay so now that we understand how we can visualize our queue let's go back into our server.pi file and make use of it for one of our endpoints and we're going to change this rule to blog post forward slash numeric body we're going to change this to get numeric post bodies and what this route is essentially going to do is it's going to convert our blog post bodies to a numeric value containing the total of each individual character within the body's ascii decimal equivalent so it sounds complicated but basically all it's going to do is it's going to iterate through each character within our body and it's going to add all the characters within our body up by their decimal value so our body is just going to be converted into one integer and we're no longer going to need to access that blog post variable and we're going to get our blog posts from our database by doing blogpost.query.all then we're going to create a queue which we'll just call q and it's going to be from custom q and instance of q and we have to import our custom q module we'll go here change that to custom cue and now we want to add every post from our blog post to our queue so for post in blog posts we want to do q dot enqueue and pass in our post as the data and we're going to return a list so let's create a return list which is just going to be an empty list for now so at this point our queue contains all of the posts from this blog post query and what we want to do is we want to dequeue and process each post until our queue no longer contains any more posts so to do that we're just going to loop through the length of our blog posts because the length of our blog posts is the number of posts that we have in our queue as well so we can just use that number for our loop to dequeue each item within our queue so we'll do post equals q dot dq and if you remember dq is going to return the value that's removed and that's going to be passed to our post variable then we want to create a variable for numeric body we'll just start it off as 0 and now we want to loop through every character in our post body and convert it into its integer equivalent from our ascii table and then we want to add that to our numeric body so for char and post data dot body numeric body plus equals then ord and then char and this ord function is just a built-in function that will convert our character into its integer ascii equivalent and now our post.data.body is going to be set equal to the numeric body instead of the actual blog post body and then our return list we're going to append our blog post dictionary containing the new body so this body is now going to just be a numeric value or an integer and lastly outside of our for loop we want to return jsonify our return list so let's take a second to go over what this is doing so at this line here we're just creating an empty queue an instance of our queue and if we go to our queue we should remember that we have two methods on our queue in queue and dq and we should also remember that a queue does insertion and removal in first in first out order so whenever we enqueue we're adding to the end of our linked list or the end of our queue or the back of the line if that's easier for you to visualize and whenever we dequeue we're removing from the head of our linked list or the front of our line so here for each blog post the blog posts are in ascending order and we're adding them to our queue in ascending order as well because we're iterating through them in its ending order so for example if we have blog post id one two and three when we enqueue the first one one it's going to become the first and last node of our queue then when we enqueue the second one two it's going to get added to the end of our queue so it's gonna get added after one and then the same for three it's going to get added after two then here when we dequeue it we're dequeuing it in ascending order first we dequeue id1 then we dq id2 and then we dq id3 and so on and so forth so essentially these posts are waiting in line to have their characters converted into integers so once one node has its body's characters converted into integers it gets appended to our return list and then we go on to the next item in the queue and eventually we get to a point where our queue is empty and at that point we'll just return the entire list so let's go ahead and test this out so let's start our server python server.pi and back in postman we'll create a new request and we'll just call it git numeric body and we'll save it to flask api open it up let's go into this blog post and take this and our rule is blog post forward slash numeric body and let's go ahead and send this and see what happens and as you can see we get our blog post back and the bodies are now converted into a single integer okay so now to implement our stack we can create a file called stack.pi and again we'll start with creating a class called node which will have the same structure as our linked list node as well and this is because a stack is also essentially just a linked list and just like our queue the only difference between a normal linked list and a stack is a stack does insertions and removals in last in first out order so let's go over what that means by creating our class for stack so for our stack we only need to keep track of the top and the top is essentially the same as the head of our linked list we're just going to call it top because when we visualize it top is going to actually make more sense and you'll see what i mean when we go to the blackboard explanation so self dot top equals none for now and we can just define a method called peak to just see what our current top is and all this is going to do is return self.top and we'll define another method called push and this is how we're going to insert nodes onto our stack and all we're going to do with our push is we're going to replace our current head with the new node and then make our current head the next node so we're basically just placing this node on top of our current head and then that node becomes our new head so we'll create a next node variable to store our current top and i'm sorry if i'm saying top and head interchangeably that's because they're the same thing so don't get confused and then our new top is going to be a new node which contains our data and next node and our next node is going to be our current top or head and then we set our new top equal to our new top and this is the only way that we can add to the stack we only can add it to the head of our stack or the top of our stack or the head of our linked list i hope this isn't getting too confusing it's actually very simple and i'll show you soon and for removing from our stack it's also very simple we'll define a method called pop and all pop is going to do is remove the head or remove the top and whichever node is next from the head is going to become our new top that's it so if self.top is none that means that we have an empty stack so we'll just return none and again we want to keep track of the removed node because we want to return it and we'll set our new top equal to self.top.nextnode very simple then we'll just return removed and that's going to be it for our stack implementation so let's go ahead and take some time to see what this code is actually doing as well and you'll find that it's very similar to the queue which is very similar to our linked lists because they're all essentially the same thing okay so let's take some time to try to visualize a stack so we're already familiar with how to visualize a node but when we visualize it in the context of a stack we're going to flip our node so what i mean by that is with linked list we visualize our node this way with our data being here and then our pointer to next node being here and then this would be our head and then there would be other nodes right and that would be a linked list well for a stack we're just going to look at it this way we're going to have it like this we'll have our data here and we'll have our pointer to the next node like this and instead of calling this head we'll call it the top of the stack and if we were to have another item in the stack it would look like this as well okay so let's erase this and let's go ahead and create an instance of the stack we'll just call it st equals a new stack instance and let's do dot push and we'll push some data and what that's going to look like is we're going to end up here and our next node is going to equal self.top and currently our self.top is none so our next node's going to be none and then our new top is going to be a new node with our data and this new node's next node is going to be this next node that we created which is none and then we'll set our self.top equal to that new top so what will that look like that's going to look like this so we're going to add a node with our data and it's going to be pointing to none and then this is going to be our self dot top and now let's go here and add another one push say data 2 and we're going to end up here again and now our next node is going to be our self.top so our next node is going to be this node and our new top is going to be a new node with its next node being this next node which is this one so all we need to do is we just need to create a new one data 2 and its next node remember its next node is going to be the current top so its next node is just going to be this node see our new top is a new node with our next node being this node and then self.top is now going to be equal to our new top which is this one so this will no longer be our top this will now be our top and we would do the same thing if we added another item we would add it here and this new node's next node would be our current top and then we would change the top to this new node and so on and so forth so what happens when we do pop so pop it will only ever remove the head it'll never remove anything below the head so if self.top is none we're just going to return none because if top is none that means that our stack is empty right but in our case it's not none so we're going to store our current top which is this one in a removed variable so we're going to store this in our remove variable and then our current top we're going to set it equal to self.top.nextnode so we're going to set it equal to our top's next node so all we're doing is we're just changing this to point to this one and we're just removing this point here and then we're just returning the removed so we're returning the removed which is this one so it's getting popped off and returned and it's this one and this is going to just sit here we don't need to do anything with this because it'll be garbage collected so eventually something's going to come along and clean this up and we're going to be left with just this top and if we push on to the stack again we're always going to push on to the top and when we remove from the stack we're always going to remove from the top and that is how we can visualize a stack okay so now that we can visualize our stack let's go back into our server.pi file and first and foremost let's just import our stack and for our very last route we're going to use our stack to delete the last 10 blog posts within our database so we'll change this to delete last 10 and we can also change this to delete last in and again we don't need that blog post to be passed in and here once again we're going to do blog posts equals blog post dot query dot all and we'll call our stack instantiation s and we'll just do stack dot stack to create a new instance of stack and similar to our blog post we're going to iterate through our blog post and then we're going to push them onto our stack so now what we want to do is we want to loop through pops of our stack so we could do four in range 10 and then we're going to do post to delete equals stop pop and if you remember pop is going to return the node that we're popping off of our stack and once we have that node we can actually delete it by doing db.session dot delete and putting in our post to delete and then this is session not sessions and then dv.session.commit and if it's successful we're going to return jsonify and we'll just say success now if you're wondering why this deletes the last 10 blog posts it's because if you remember how a stack works insertions and removals are done in last in first out order so if we go to our push method we'll see that whenever we push a node onto our stack it gets pushed to the top of our stack or to the head of our linked list and this blog posts query is a list of blog posts in ascending order so if we're pushing onto our stack blog posts in ascending order the blog post with id 1 is going to get pushed on first and then every blog post following blog post with id 1 is going to get put on top of blog post 1 eventually resulting in the top of our stack being the last blog post in our database so if the last blog post in our database is 200 the top of our stack is going to be blog post with id 200 and the bottom of our stack is going to be blog post with id1 so when we loop through 10 times we're looping through and we're popping off the stack the top node for each iteration we're just popping off 200 then 199 then 198 then 197 and so on and so forth until we pop off tin and for each one that we pop off the stack we're going to delete it from the database so it results in us removing the last 10 items in the database every time we run this loop so let's go ahead and test this out we can run our server again and we're going to want to open our database to see our data to make sure that the right blog posts are being removed so we want to open our database then we can browse table for our blog post and we can go all the way to the bottom and we'll see that our last blog post id is 201 so if we were to remove 10 blog posts from here if we refresh this after calling that endpoint we should only be left with up to id 191 so let's go into postman and create a new request so add request delete last tin blog post delete last 10 and it's going to be method delete and let's go ahead and send this and see what happens and we got an error so let's go see what happened so let's go into our server.pi file and the issue is i didn't add data to this post to delete because if we remember our pop returns a node and a node contains data as our data so we need to access the data by extending this data attribute so let's go ahead and save run our server again and let's go try this again so we'll send the request and this time we get success so now let's go and check our database and see if the proper blog posts have been removed so within our database we can go ahead and refresh and go down to the bottom once again and as you can see we only have blog posts up until id 191 so it's working as expected and that's going to be it for this tutorial congratulations for making it to the end if you enjoyed this video be sure to subscribe to my youtube channel and follow me on instagram and twitter at essie like a pro i make content like this every week so if this is something that you're interested in be sure to drop on by and of course if you haven't already please like this video and subscribe to free code camp for more exceptional content anyways i hope that you all have enjoyed this video and i hope that you've learned something and it's been a pleasure i'll see you in the next one

Channel: freeCodeCamp.org

Views: 75,016

Rating: 4.976768 out of 5

Keywords:

Id: 74NW-84BqbA

Length: 193min 20sec (11600 seconds)

Published: Thu Apr 22 2021