Data Structures in Python: Singly Linked Lists -- Insertion

all right so in this series of videos we will be considering the linked list data structures so I'm going to assume that you have some familiarity maybe you've seen these types of objects before and maybe a class you have taken from awhile ago and you just want to brush up or maybe prepare for an interview so you need to go back and revisit these types of data structures so in this series of videos will be considering the variants of linked lists so singly linked lists circular doubly these sorts of things we'll be going through each of these objects in detail and seeing what types of operations you can perform on these and then we'll also be implementing these data structures in Python and as I go through a particular operation for this list we'll take a break and move over to the terminal to see how we can actually implement that operation using this idea so just to refresh I'm going to first talk about singly linked lists worth which are the most basic type of linked list types of data structures just to give a brief overview of what a linked list looks like this is it depicted a very simple version of a linked list every linked list is consisted of nodes so these boxes here are what we call nodes and every node has two components one is called data when it's called next so the data component every node has this and it allows a node in this list to store some passed some element of data the data here is just a character ABCD but data is meant to be interpreted to be possibly more general so it could be strings it could be characters giving numbers it could be other types of objects we also have this component that every node has called next which is a pointer that points from one node to another so this node here that stores a has a next pointer that points to you the node that is next in the chain or the list which stores B so on and so forth so B this node here has a next entry that points to this node with the entry C and the start of the list is referred to as the head so the head is kind of where we are looking so it's a pointer that points to the start of the list as we if we want to traverse the list this head that's looking at each of these nodes and the list will have to move along with us to figure out where we are in the list so if we want to iterate through the list we'll see this in greater detail later the head pointer will have to traverse along the list in order to obtain or access an element of the list the last component of a singly linked list is this notion of null so the end of any linked list is terminated by this null idea so it's in Python we'll see this is just we'll call this none it's just the next pointer of the last node in a singly linked list points to this null object and that just tells you that it's the end of the list so very quickly just to give a brief overview of how arrays and linked lists are different this is probably kind of a good thing to keep in the back of your mind raised and linked list when it comes to insertion or deletion for an array the insertion deletion operation is on of the order of n operations and that is because if in the worst case if we need to insert an element in the beginning of the array this will evolve shifting all of the elements in the array to the right so we can make room for the element that we want to insert or delete all the way on the left or in the beginning of the array however for a linked list once we know where we are in the list if we just need to insert or delete an element into that list that is a constant time operation and just involves shifting the next pointers around or the previous pointers around so that way we can insert or delete the element into or delete the element out of the list accessing elements so for arrays they do better for linked lists their constant time operation if you give an array in index it's able to immediately give you the element at which the entry is stored that's because arrays are contiguous which this table goes into a little bit more detail about which we'll get to that in a bit accessing elements in a linked list is an order of operation and that is because as we traverse in this list if we want to access say this element down here we need to have the head pointer traverse the entire list before it can actually get to that that's node of the list and as I alluded to before a raise when you create an array object it is contiguous in memory which allows this access time to be constant whereas linked lists you do not have the luxury of contiguous memory so these are tables that you should probably keep in mind when it comes to trade-offs between arrays and linked lists if you're given a problem you might want to consider whether or not an array is the preferable data structure or a linked list or just be aware of these these types of pros and cons so the first thing that we're going to look at how to do in Python with a linked list is this idea of insertion so there's a few different ways we can insert two lists we can add an element to the back of the list we can add an element to the front we can add an element in between nodes so we'll take a look at each of these operations and we'll take a look at how we can actually perform them in Python the first one is adding an element to the end of the list which we'll call append or appending it to the end of the list so if you have a linked list that looks like this and you have an entry let's say another node here that's the node it's e if we want to append this to the list here the outcome of that will be the list that we have with a wedged in between this and the null component of the list and this is what append looks like so actually before we move on to the other types of insertion methods let's actually go ahead code up a linked list implementation Python and start to think about how we can actually do this operation so I've created a Python file here called linked list hi and what we're going to do is we're going to create two classes one which is a class for the node object in a linked list and one which is a class for the actual linked list itself which consists of nodes so just to go back to the figure here just to refresh ourselves a node we're going to create a class for what a node object looks like so this is something that has a data and next component and then we're going to also create a class for a linked list it's a singly linked list will call this linked list for now and this just consists of nodes so let me minimize this and let's go ahead and create our classes so we'll create a class called node in the constructor of this class well give it the argument of self and also data because this is going to be remember every node is going to consist of next and data so what we'll do is we'll say self dot data is equal to data which is what we're passing in to define an object of this class and then we'll say it self dot next is equal to none so this is something that we'll set as we make use of the node but initially we'll set it to none so that's pretty much all we need for the node class now let's go ahead and define a linked list class and here what we're going to do is in the constructor we'll have again self and then we'll have a component which if we go back to the figure again the start of the list if we want to start afresh linked list we'll give it the head pointer so the head pointer will point to the first node in the list and we'll initially just set that equal to none or to null so we'll say self dot head is equal to none so what we can do now is we can go back again to the presentation and the first thing that we want to do now that we have a linked list type of infrastructure setup with these two classes as we want to append entries into this list so let's actually before we do that let me just go to the main part of the program and let's define a linked list object so we'll say linked list is equal to linked list and then we'll eventually what we'll do is we'll say linked list dot append and then we'll give it some thing let's say a linked list dot append let's say B and then we'll also want to have some way to actually print out the elements of the list so let's go through and actually create the append function so we'll create a method which is a class method called dot append prepend rather and it's going to append in a node on to this list and this node is going to consist of some data component so we'll also need to pass in that data component so let's go back to our figure so when we have this list assuming we have some list here we need to do a few things to upend first we need to check if this is totally an empty list if the list is not empty if we're appending a node in the list for the first time we need to take care of that case separately then if we already have a list and we're appending it to the end of the list let's take this easier case where we actually just don't have anything we have no list and we just want to append the first node to that list let's minimize this so the first thing that we want to do there is we I guess in any case we want to define a new node and we'll use our node class to do that so we'll define this new node equal to a node object we'll pass it in data so this new node object that we have now is a node and it consists the data field of this node has the entry of data that we passed into this append function and we want to take this new node that we just created and append it onto the list so the first thing we want to do if we want to check if the list is empty so the way we can do that is we can check if the head of the list doesn't currently have any component so we can say if self dot head is none if this is true then this basically means that there's nothing there the head the head pointer doesn't point to anything at all and therefore there is no component in the list there's no node in the list if this is the case then what we can do is we can set the head pointer to the new node that we just created so we could say self dot head is equal to new node and if that's the case we can just return that's it so that case is relatively easy so what do we do now if the list is not empty and there's other entries in the list how do we deal with that what we can do is we can say let's go back to the figure because I think it makes it a little bit easier is what we can do is we need to actually get to this the place where the new node needs to be inserted so let's say we have a situation like this where we already have a list and we have this new node that we've created and we want to append this to the list so what we can do is we can start off here the head pointer starts off here and we can move the head pointer through each of these components in the lists each of these nodes in the list and when we get to the end when we get to null we know we've reached the end we know that's where we want to actually input the new node so first we need to figure out how do we move from one node to the other using the head pointer and once we arrive at the location that we want to insert the new node at how do we actually go about putting that new node into that location so what we can do is we can define let's say what we'll call last node and this is will initially be equal to the head so we're at the start of the list we define this variable to be called last node because that's what it will eventually point to but at the moment it just starts off at the beginning of the list and we want to do is we want to move through that list so while the head pointer doesn't point to null we want to move through start off head here this is this pointing to null no move on to the next one is this no no so on and so forth until we get to this and then when we get to that that's when we'll go ahead and input our new node into the list so what we can do is we could say while last node dot next so basically while this is not null while the next pointer of the node that we're currently on is not null we're going to continue in this loop so what we're going to do in this loop is we're just going to move the head pointer to the right so we're going to say last node is equal to last node dot next and then after this loop has concluded last node will point to the last node so again we point initially to head while we while the next pointer does not point to null we continue on this basically just moves the head pointer to the right so while it's not no the next pointer is not null is this will start off here is this next point or no no move here is this next pointing to null no it's pointing to see is this next one pointing to no no it's pointing to D is this next one pointing to null yes it is so we are at that point now so what do we do well we need to insert the node so we can say if that's no we can say last node dot next is equal to the new node that we want to insert and that will append the node to the end of the list so at this point we have an append function which is great but we want some way to verify or we want some way to print out the components of the list and the way that we're going to do that is going to be pretty similar to what we did for this append function and it will also allow us to verify that the append function is actually working as expected so let's create a function which we'll call prints lists and it's class method so it will take self as an argument and what we're going to do is we're going to print out the entries of a list so how do we do that well again if we start off here let me just go back to the general picture of a linked list if we start off here the head pointer starts at this component this node here so what we can do is we can say okay we're starting off here we're at this node print out the data component of this node and then move head to the right so check if the next is not null if it's not move head over there and print out the data field of this node and then just keep doing that until you've hit this null terminating component of the list once you do that you know you've reached the end of the list so that's pretty much all we need to do so what we'll do is we'll say let's say current node is equal to the head of the list and then while that current node isn't null so while current node is not none or while current node it's just a shorthand for the same thing we're going to say current node is equal to current node dot next and before we do that we'll actually print out the data so we'll say prints current node dot data and so as we do that we'll print out the data field of each of the nodes and we'll iterate through the list by just going to the next node in the list from this line here and that should be all that we need there so if we go ahead and write this let's go down here so we've appended both of these things to the list and if that actually did work hopefully we can say list dot print list as well and this should print out I guess in Reverse be an a so let's write that and let's give this a run so Python linked list op I let's see so it looks like so it looks like I forgot to add parentheses here and if I write that and now run it then I'll see here that we have a and B so it does indeed append to the list we have this a which is now the first element that we appended from the first line that said append a then we append B and then print list was able to go through starting off at the first node in the list and print off all of the elements in that list so it's able to do both of those things appear to be functioning as they should be so the next thing that we're going to do is go back to the slides and we're going to look at another method of insertion which is prepend so instead of adding a node to the end of the list this case we want to add it to the beginning of the list so again we have this linked list let's say here and we will have this new node what we want to do is we want to prepend it which basically will just look like this so we've taken this new node that we have here and then we just move it to the beginning of the list so we prepend it to the beginning so what is going on here how do we go ahead and do this well what we can do is the first step just like we did for a pen is we create a new node based on the data that is passed in so in this case that data field is e and then what we can do is we can set the we can consider this head of the list so what we want to do is we want to say that this new node this next component should point to this guy so we need to change the next component of this to point to the head of the list and then we want to move the head because the head is still at a we want to say that now that we've prepended the head should move to this element of the list so that's really kind of a two-step process maybe a three-step process because we're creating this node as well so let's go ahead and step through that so we'll create a function which will call prepend this will also take self since the class method and data since we need to tell it what to prepend to the list and then what we're going to do is we're going to as we did for append will say new node is equal to node of data so we're creating a node here and then what's the first step so going back to this picture what we need to do is we need to say here's our new node that we've just created we want the next field of this node to point to the head of the list so how do we do that we can say new node new node dot next is equal to head so basically what we're doing is we're saying draw a line draw an arrow if you like from this new node that we've created draw a line or an arrow to this thing so make it point to the head the current head of the list we'll have to change the head that's the next step so now now that we've pointed this to the current head of the list head is over here right now above the a and we need to move the head we need to say now that we've prepended head of the list is now this component here so the way we can do that is we can say self dot head is equal to new node and that's pretty much it so we've gone ahead and prepended to the list so let's go ahead and see if this works let's say ll list let's actually just make this very similar to the picture so we'll say append to see append D so if we go ahead and print this list out we haven't prepended anything we have a list that looks like very similar to the one that we have in the figure now let's try it to do what we did in the figure which is what we we prepended the component e to the list so if we go ahead and do that we now have not ABC and D but E is now prepended to the beginning of this linked list the last insertion method that I want to consider in this video is inserting after a given node so we have a linked list just like we have before we have this node and we want to insert after a given node in the list so basically what we want is we want something that looks like this where we'll have a list now where we've taken this new node we've created and let's say we wanted to insert after this node B so we've kind of wedged this new node in between B and C so that's one example of what we want the outcome of the list to be in this case so let's break down exactly the steps required for us to do this operation the first thing as always is we need to create the new node given the data that we're given and then we need to check if the node that we need to insert after is even in the list so it's not the list we'll just return because it's not there can't insert it after I know that's not present in the list if it is there say the note is B then what we need to do is we need to do a few things so the first thing that we need to do is we'll have something that looks like let's say like this so we have this new node we created and then we do this where we have had the next pointer of this new node point to the next pointer of the node that we were given so we were given B the next pointer points to C and we want this guy to point to that C so we say new node dot next is equal to this node next so now they're both pointing through this thing here but B is still pointing to C so we need to change this arrow to point over here so what we can do is we can now change the next pointer from here to point to this thing here and then what we want to do is we want to make sure that this thing goes away so if we have that we have all the ingredients needed to insert after a given node so let's go ahead and let me just undo that so we have that for reference and let's see let me go back to minimize to go to the code so we'll create a new function called insert after node it'll take self since this is a class method and it will also take the let's say the previous node to insert after and then data which is what the new node should consist of so the first thing does I mentioned is we want to check if the node the previous node that we're given is even in the list so if not previous node if this note is not there we must say that the node previous node is not in the list therefore we can't insert after it will just return otherwise if it's there we'll create a new node as we've always done for all the other insertion methods and then what we'll do is we'll say let's break this down again let's go back to the picture we'll say we're going to do this thing so we're going to say the new node the next pointer of the new node should point to this guy here which is previous pointer next so we want this picture to be a thing the way we do that was we say new node the one we just created dot next is equal to previous node dot next if we do that that's essentially going to give us this picture here so new node next points to previous node next again in this case previous node is B the next thing is the C note here right so let's go back to the code so we have that and now the final thing we want to do is we want to say the previous node so let's go back to the picture again the previous node this thing needs to now point to this guy so what we want to do is we want this thing to to happen so we want the next pointer of this guy want to get rid of that as well we want the next pointer of this guy to point to the new node so we can say previous node dot next is equal to new node and if we do that that should be all we need to insert a node after another one so let's go ahead and try that out so let's try to get rid of this and what we want to do is we want to have a list that looks exactly like the one that we've created here so let's say that we give it the previous node of B and we want to insert E in between just like we've done in the picture so what we'll do we have the list there ABCD we'll say list dot insert after node we'll give it so the way we're gonna actually feed in the previous node is like this let me before I actually print out the list let me just do this so if we want to refer to that node B the way we're gonna send that information into the insert after node function is like this first of all let's just observe what happens if we say list dot head dot data so if we print this thing out here let's go ahead and give this a print so we've created the list up above ABC and D and what I'm doing now is I'm printing the data component of the head of the linked list so what should we get we should hopefully get a a is the head of the linked list so as we can see here this is the head of the linked list this is the data component of the head of the linked list and that's what was printed out so what I want to do is I actually want to give the previous node of B so the head is a I want to give it dot next so essentially what I want to do is switch this around so the next node after the head if I print out the data of that thing I should get B and I indeed I do so I get B which is printed out there at the bottom so this I'm not going to show the I'm not going to pass the data field but I will print or I will pass this thing over as an argument into the previous node into the insert after node function so I'm going to do is I'm going to say insert after node the previous node as I mentioned is that right there that refers to the node consisting of data element B and then I'm going to give it the data of E which coincides with the picture and I also need to make sure that I say ll lists dots to make sure that because it's a class method so okay so if I do that go ahead and run this and actually before I run it let's print out the list after so we should see something similar to what we saw in the picture so now if I save it run it what we see here is we see a B EE C D so E is wedged in between B and C just like we had in the picture here and that is pretty much it so in the next series of videos on linked lists we'll be continuing to build on this code we'll be running some other methods in this class that we'll be writing for manipulating this linked list singly linked list data structure so all all the code that I'll be writing and everyone these videos will always be up on my github link and I'll provide a link to that in the description below this video was helpful to you please let me know by liking and subscribing or commenting if you have any questions or concerns please don't hesitate to ask as well in the comments or contact me directly thanks again for watching I hope this was helpful and have a great day

Channel: LucidProgramming

Views: 85,892

Keywords: python linked list, singly linked list, linked list python, python tutorial linked list, python lesson linked list, python tutorial singly linked list, linked list data structure, python data structure, google interview, facebook interview, microsoft interview, twitter interview, youtube interview, technical interview, apple interview, lucidprogramming

Id: FSsriWQ0qYE

Length: 27min 1sec (1621 seconds)

Published: Sat Jan 20 2018