Linked List - Data Structures in Python #1

Key Takeaways

what is going on guys welcome back today we're going to start a new tutorial series here on neural 9 about data structures in Python the goal here is to implement the various data structures that we know linked lists and stacks and heaps and binary search trees and so on and to also discuss the runtime complexities of the various operations that we can perform on these data structures today in this first episode we're going to get started with linked lists and W link lists so let us get right into it not AED all right so we're going to start off this tutorial series by implementing a linked list and a w linked list in Python today now as I already mentioned the goal of this tutorial series is to understand the data structures and also the runtime complexities of the operations that we perform on these data structures by implementing them from scratch so we're not going to use any packages we're not going to import any data structures we're going to build them from scratch in Python using classes now I'm going to always briefly explain the data structure so that you know what it is about in theory before we implement it but if you want to have a more detailed explanation I have a tutorial series or a course you could say on algorithms and data structures there you can find more details about them but I'm going to give you a brief sketch of the basic data structure every time before we start coding it so let us get started briefly here with the linked list I'm going to sketch it out it's quite simple the basic idea of a linked list is that we have so-called notes so we have for example let's say this is a note and this Noe has a value for example the number 10 now this node also has a pointer or a reference to another note to the next note so to say and this note then again also could have a value 20 and it points to another note and so on and so forth they can have different values and at some point some note will have a pointer to none in Python it is none in other languages it's a null pointer whatever ever it's basically the end of the list so a linked list works like this you have notes and one note points to the next Noe this note points to another note and so on until we get to the end of the chain until we get to the end of the linked list and this structure of course means that we have to perform different operations in different ways for example if I want to see if a certain value is part of the list I cannot just jump to that value I have to uh go through all the values so in order to see if 30 is part of the list I cannot just look at the list and see it I have to say okay let's go to the first note is it 30 no jump to the next note is it 30 no jump to the next note is it 30 yes I have 30 in the list um and because of that of course this is going to have a runtime complexity which is in o n Linear by the way if you don't know anything about runtime complexity I would recommend that you watch some video you can watch my video or another video that explains the basic idea of runtime complexity because I don't want to go into too much detail here on the theory uh in in this tutorial series but the basic idea is how many steps you need to perform how the complexity of your uh of your algorithm increases when you increase the input size so in this case the list has n elements so three elements and in the worst case I have to go through all three elements to find the element I'm looking for because of that we have a runtime complexity of O ofn uh a worst case complexity uh that's the basic idea um so that's a linked list a doubly linked list is the same thing just that we have two pointers so every note also points to the previous note so it's basically like this and then here we have a nonp pointer uh or non reference again so it's just um it's just in both directions and this of course makes it easier to prepend or or to uh to do certain things um and uh and that's that's just a difference here so we have two references we have going it into both directions that's a doubly link list and if it's if it's just going into a single direction we have a normal uh linked list and this is what we're going to implement in Python and we're going to also Implement a bunch of different operations so for example I have my code prepared here we're going to um Traverse it we're going to display it we're going to see if it contains some values we're going to calculate the length or we're going to to get the length we're going to append we're going to prepend we're going to insert at a specific position we're going to delete we're going to pop a specific index so remove move an element not by value but by position we're going to get and um yeah that's actually it for the link list so let us get started now with a new uh python file I'm going to call this linked list py and we're going to start with the most important class here which is the node itself so we're going to create a class node and this class node is very simple it's just a simple Constructor and a nit method where we say we want to have a Val and every note is going to be initialized with a value and a reference to another note so we're going to say here self. Val is going to be equal to the value and self. next in the beginning is going to be none so every note when we create it is not going to have a next note that's all a Noe is a value and a pointer to a next note but by default this is going to be empty it's going to be none now that is the note the linked list is then another class which utilizes the note class so we going to say now class linked list and we're going to say that when we initialize a linked list for the first time we're going to set um we're going to initialize the head note so a link list has a head note which is the uh beginning note we're going to just take this and uh set it to none in the beginning because if the list is empty we we don't have any any notes in there so we have none but once we add a note to the list the head note is going to be that first note and every other Noe is going to come afterwards unless of course we prepend or insert um so we're going to say here self head equals none and that is actually all we need we need the head of the list and then we can perform everything uh from the head onwards now um what we're going to do now first here before I go into the other functions even though you know I'm going to implement a couple of functions maybe before we start with the implementation a good idea would be to list the functions that we're going to implement uh without any code yet so one function that I'm going to implement is the dunder repper function this is just a representation this is going to be traversing the list and printing the values displaying the values that are part of the list so here we're going to just say pass for now uh we're also going to implement the contains Dunder which is of course going to check if a value exists in the list this is what I showed you in my paint here um a minute ago and then we also are going to implement the length Dunder or the Len Dunder which is going to give us the size of the list and then we're going to implement a couple of methods uh that are not Dunder so one is going to be the append method obviously this is going to add a value to the list it's going to add it at the end of the list um so for that we're going to do pass as well we're going to also have prepend which is the opposite we're going to insert it in the beginning and this is what I meant when you have um when you have a doubly linked list uh actually I I messed it up it's not a preent the preent is easy with the uh normal link list as well because you just have to create a new note and let it point to the uh to the Head node and then make it the head node but if you want to append in the end then a dou link list is useful because you all also have a tail so you can do that in constant time as well but we're going to take a look at that here in a second uh so preent is the opposite you insert it as the first element and then we have also the method insert the insert method um is adding a value to a specific index to a specific position um and then we're also going to have delete pop get so delete is going to be delete by value so we provide a value and this value has to be deleted from uh from the linked list then pop is going to do that with an index and get is going to give us the value of a specific index of a specific position and then we're also going to have a simple uh print function which is going to be quite similar to the representation function if not the same and then finally we're going to have a section down here if name equals Main and here we're going to then create our class and use it so these are the methods that we're going to implement now if you want to take it easy you can also drop some of them you don't need prepend you don't need insert necessarily whatever you want want to do it's going to be quite a lot of code here now but um you can also choose to just Implement a couple of them I would like to start with the append function because that's the most um the first thing that you want to do with a list you have an empty list you want to add some elements to them uh to the list so how can we append a new element to a link list now obviously if the head is none I just have to set the head to the new notes so I can already have a case if self. head is none so if I don't have anything in list all I have to do is I have to create a new note and make it the head of the list so I can say self. head is equal to note value that's quite easy now what happens if I already do have a head well then I just have to go uh to the next element as long as there is a next element and at the end when I see that now there is no longer a next element I just have to create a new note and put it there so this means I can say something like last equal self. head so I start with a head and I say while my last element that I looked at has a next element so in the beginning it's the head does the head have a next element if yes go to it um otherwise append it already so if there is a next element I said last equal to this NE uh next element so I go further and further into the list until there is no next element and what I do then is I say last. next since last or next at this point will be none is going to be equal to a note uh given a value so maybe um maybe I will do this here now with a graphical explanation just to give you the basic intuition we have an empty list so what do I do I create a new note and give it a value that's my append if the list is empty now here my next pointer points to nothing so what I do if I want to append 20 for example is I go to this I say while this has a next oh it doesn't have one so what I do is I create a new note here now let's say I want to append five as a value what I do is I go into the list I see okay it does have a next element so I set last equal to the next one okay 20 does this have a next Element no okay perfect then create a new note and give it five now this here definitely has a runtime complexity of O of n so we have to go through all the elements here necessarily to be able to append it we don't have a we don't have a reference to the last element we don't have a tail element so because of that we cannot just um append it in constant time we have to go through all the elements to get to the end until we can then append a new element so this is going to definitely have a runtime or actually I'm not going to say runtime complexity just o of n linear time and this has a worst case complexity which is linear but also has an average and best case complexity which is linear because you will have to go through all the elements it doesn't matter it's not a matter of chance or uh how well the data is structured or aligned it's just you will have to go through all the data so this is a linear runtime complexity here now the Preen function is quite simple when we're talking about a linked list because all we have to do is we have to create a new note we have to make this new Noe point to the head and then we have to make the head uh or we have to make this note the new head so all I have to do is I have to say first note is going to be equal to a note that has the value that I want to prepend and then what I want to do is I want to say this first note then should point to the current head and then the current head should be set to be equal to this first Noe that's it this also works if we have none uh think about it here again visually let's go to my paint if I have a list like this what do I have to do to prepend an element well I just create a new note let's say I want to give it the value uh 25 for example and all I have to do is I have to make it point to the current head and then I have to say Okay this is now my head and if I have none what do I do I create a new element and I point to the current head which is none still works so that's quite simple and this can be done in constant time the list can be huge and it's still going to happen in the same amount of time because it's the same operation so this has o of one o of one constant time so linear time constant time and this also this is worst case this is best case this is average case because every single time when I prepend a node I will have to do this one operation create a node let it point to the head make it the head that's it every time the same um yeah the insert is now a little bit more interesting because now we're going for a specific index now I want to say um I want to put it at a specific position now we have one special case here if this position if the index that I'm trying to insert it um into is zero then I can just preent so I can say if the index that I'm passing here is zero I can just say self. preent value because then I'm just doing the same thing that I just explained otherwise we're going to um to do the following we're going to say first of all if I don't have a head and I not trying so if if the list is empty and I'm trying to insert it an index that is not zero then this should produce a value error because I'm obviously trying to access a position that doesn't exist so we're going to also raise an exception here we're going to say if self. head is none and since we're not trying to use index zero I'm going to erase a value error and this value error will say uh index out on of Bounce I'm not sure if the value error here is the correct exception type or error type but let's just do it like this so self head is none raise value error and otherwise if the head is not none what we do is we say again last equals self. head and uh we basically iterate using a full loop for I in range and now we use the index minus one because we don't want to go to the element we want to go before that element um and we're going to say if last. next is none at some point here before I get to the index that I'm trying to get to I do the same thing as above I just copy this and I paste it down here because this is also a problem I'm trying to go so if I want to insert at index 5 I have to go to one position before that because I don't want to go after the point where I want to insert so I have to go minus one but if I at this point it's somewhere somewhere during this process if I realize that there is no next element this means that I don't have enough positions to get to the index that I'm trying to get to so again index out of Bounce and if that doesn't happen then I just say last equals last do next and if the whole Loop runs without raising an error then I have the correct position so what I do is I create a new note I say this note has the value that I'm trying to insert and then I say the new note do next is going to be what this node is currently pointing to as next I'm going to show you why that is visually here in a second again and then I let this note here the last note point to the new note so the idea here is if I have um let me just take my drawing tablet here if I'm trying to insert something at this position here what do I have to do to do that well I create the note let's say the value is 30 here I create this new note what I need to do now is I need to ask okay what is the note before me pointing to before myself pointing to so the note that comes before where I want to insert this is 10 10 is pointing to 20 so I just copy that now I point to 20 and now I say okay 10 no longer points to 20 10 now points to me this is exactly what we're doing in the code here this is this here we create a new note we point this new note to the note that the last uh note was pointing to and we'll let let the last note point to ourselves to the new note that is it this of course has linear runtime complexity in the worst case I have to go um in the worst case I have to go through all the elements because I'm providing an index that's you know n or n minus one so that's linear runtime complexity all right so now we have the various methods to add elements to um to the linked list now let us talk about the I mean we're going to do the representation in the end but let us talk about contains how can I find out if something uh is part of the list so this is a true false uh function or method this is going to give us either yes or no um and obviously we do the same thing that we do when we do the appending just that we can stop um before that we look for a value and we can terminate so I think the average case runtime complexi is divided by two so and half because on average you will have to go through half of the list to find a value uh but in the worst case you will have to go through all of the list and you're still not going to find a value so this has obviously before we even implement this this has um linear runtime complexity oh my God what's Happening Here There you go okay so what we do here is obviously same same concept last is equal to self. head and then we say while last is not none so while the thing that I'm looking at actually has um is a note is not empty I check if the value of this is equal to oh actually we need to pass we need to pass a value here so if last value equals that value we're going to say return true and and um then we're going to otherwise say that we want to go to the next element so last equals last. next and in the end if I never return true I have to return false it's as simple as that so we just do the exact same thing that I talked about we start here I'm looking for let's say 40 which is not part of the list so I look at this element no next look at this no next look at this no next look no look no okay end of the list um at some point I don't have any um any values anymore I get to this none and then I have to go I have to terminate the loop and I return false and if I find the correct value in between I just return true and the function or the method uh terminates all right uh now for the length it depends on how you implement the linked list this is something that you can Implement differently now if you just implement the way that we have implemented it right now calculating the length of the list has linear time and it has actually also in the best case linear time because what you have to do in order to count how many elements you have is you have to go through all the elements and increase in count a counter so for example with the current implementation what we could do is we could say last equals self. head counter equals 0 while last is not none we say counter plus equal 1 last equals last. next and in the end we return the counter that is obviously in linear runtime because of course we have to go through all the elements until we get to the last one every single time so it's not even average or best case in any other it doesn't even have a different uh complexity when we look at the best case or the average case we always have to go through all the elements similar to a pend however you can make this constant if you change something about the class if you for example also keep track of a size so if you say self. size is zero uh and every time you perform an operation you update the size which is not going to change your runtime complexity um you can make this constant so for example every time when I append I can say self. size equals 1 and I can say here when I append this self. size plus equals 1 and so on and so forth and I do that every time I do that everywhere so here I ALS o increase here I increase and with all the delete methods we're going to implement I decrease um in this way all I would have to do is I would have to say return self. size and that would make it a constant runtime complexity you can do it like that I'm going to now keep it uh like this it depends on what you want to do but this is not a bad thing you know if you're going to access the length uh frequently it makes sense to have a single integer that represents the size it doesn't really change the runtime complexity of any function of any method so that is definitely something that you could be doing but I want to keep the code simple now so I'm not going to mess with the size uh just to focus on the operation itself but again you can make this constant by just updating the number every time the size changes um all right so let us move on to the delete method now the delete method what it does is obviously it tries to find the element if it finds it it updates the pointers accordingly uh in other languages like C you would have to free the memory in Python you just ignore it you just let the uh notes point to a different note now but what we do here is basically we say again last equals self. head we start at the beginning and we say if last is not none already now if it's none I'm not going to do anything so I don't even have to have an else Branch here I just say okay if it is none do nothing uh I mean you could raise an exception of course if you want to or an error uh but I'm just going to ignore it so if you try to delete a value that's not part of the list I don't care we're not going to do anything uh what we're going to do is we're going to say if last value is equal to the value we're going to say uh self. head is equal to uh last. next so this is basically if we're finding the value already in the head otherwise if it's not part of the head we're going to run a while Loop while last. next I'm not sure right now if this is even an efficient implementation I don't even know if we need this if else statement but yeah let's keep it like this now I prepared the code already um so while we have a next element what we're going to do is we're going to say if the value of this next element so we're already looking at the next element of its value if that is equal to Value we have to look ahead because we need to perform the operation now because if the next element has the value that we're trying to remove we have to skip it so we need to say last. next I change this now to the next next element I'm going to show you that visually here again in a second and then we break out of the loop what's the logic behind this um let let me just again uh make this a little bit uh better here so let's remove this here let's say we have I don't know doesn't really matter what kind of values we have here uh pointing to none uh if I want to delete the five for example what do I do here is I look at the next element so here at 25 I look at 10 is 10 five no obviously not so what I do is I go next at 10 I look at the next element I see it's five okay I want to remove five how do I do that all I have to do do now in in Python at least if I don't have to free memory is I have to take the pointer that points to five and make it point to what five is pointing to so I just have to skip the connection here I just have to say 10 is now pointing to what five is pointing to and it cuts the connection here this connection theoretically still exists so again in other programming languages you would have to free this memory but now the list is 25 10 30 40 so you just cut the connection here and you redirect it to be uh pointing to what five is pointing to already that's uh that's the idea here um yeah this is what we implemented and of course this is going to be in linear time why because in the worst case you have to go through all the elements to find it now this is not the average case this is not the best case but the worst case is linear time because chances are you're not going to find a value chances are you're going to find a value at the very last position which means you have to Traverse an element uh for pop it's different for pop we have to do it with the index so again we have to raise a couple of Errors first of all if self head is none we're going to raise an an error right away we're going to say index out of Bounce um otherwise if the head is not none we need to go through our iteration again we need to say self or we need to say last equals self. head um and we're going to say then that um for I in range again index minus one we going to we want to go one element before that remember so that we can skip the connection we don't want to be at the element we want to remove we want to be one before that so we can redirect the next pointer um here we're going to say if last next is none which means that if I encounter none before I should encounter none it means I don't have enough uh elements in the link list which means I will raise a value error index out of Bounce and um otherwise I'm going to just go to the next element um and what I do then is I say if last next is none which means that if the next element is exactly the one that I'm trying to um to remove so basically the Edge case that it's the last element that is none that shouldn't be none I still raise a value error and otherwise if that's not the case what I do is I say last. next is equal to last. next next which is again the exact same thing that we did here only difference is I go index wise so nothing changes here I have the same logic but I just go okay uh jump one forward so if I have a certain index I just go next next next um index times or index minus one times and then then I'm at the element that is one before the one that I want to delete if that one that I want to delete is not none then I just cut the connection to the next one that's the same idea and of course depending on the index that I provide this has linear runtime you can see with linked list we have a lot of linear runtime complexity um yeah forget obviously quite simple if you want to get a certain value at a certain index what you do is you say if self head is none guess what we raise a value error same principle the concept here is the same the only difference is we don't do anything we just return the value um so actually we have the same kind of iteration we say last equals self. head we say for I in range uh now we can use index because we don't need to stop one element before that since we are not trying to perform any operation we're not trying to change any connection so we can just say um go to the element to the exact element and then say if last next is none at some point here then we're going to say raise value [Music] error index out of balance and otherwise go to the next ele element so last equals last. next and if we can do that without any errors the value I'm looking for is going to be the value of the last note I end up at all right and of course guess what depending on the index that I provide this is going to have layer runtime complexity perfect um so now we only have the print and the represent presentation and actually it's not really complicated it's just a styling thing but it's the same kind of thing we just iterate over the whole list and we print the elements so we're going to say here if self head is none return an empty list or actually a string of an empty list otherwise I do have some issue with my keyboard here when I press e sometimes it sends the key twice and sometimes it doesn't send the key I don't know why that is I mean it's it's a cheap keyboard but maybe if you know the solution let me know in the comment section down below um what we do here now is we say last equals self head if it's not none and then we iterate again we say we craft a return string this return string will start with um with a square bracket and the first value in here let's make this an F string the first value in here will obviously be the uh self dot or last last. value um no not return sorry return is not so good return string now we're going to just iterate again we're going to say while last has a next element what we're going to do is we're going to say last equals last. next and then we're going to just say return string plus equals uh F string and we're going to say comma last do value uh and in the end we're going to close this off we're going to say now it's send it three times did you see that return string I need to get a new keyboard I think uh is just a closing square bracket and in the end we'll return the return string that's it and obviously this is always in linear time even in the best case because you have to go through all the elements to display all the elements linear time even in the best case now actually for the print I don't even we're not going to use print actually we're not going to do it we're going to just say representation is enough so these are the different methods now let's see if I made some mistakes while implementing them so let's go ahead and create a new length list LL is equal to length list and now let's append some values let's append a value 10 now let's say we want to have five and we want to have 18 and we want to have 22 and we want to have 29 and then maybe we want to prepend we want to say preent uh 100 for example and then I want to print LL for example let's see what this looks like we have 100 10 5 18 22 29 looks perfect now let's say I want to insert an element so let's say I want to say LL insert and I want to insert the value 200 at position one so after 100 now this also works perfect um now let's say I want to delete the value 18 from the list now I get a problem okay there is an issue with a delete function what is that or with the delete method okay I think it's quite a stupid mistake I think here when we're checking if the value is the correct value to remove we say that it should be removed otherwise however uh we're not progressing so we're not saying last next equals or actually last equals last next I think this is what it BS down to there you go so now 18 is deleted wasn't that big of a mistake um now let's go ahead and say LL pop now let's pop index one which means the 200 should be gone now there you go and uh did we have anything else we have prepend insert delete Pop I mean we can do get so if I say print LL get index one and if I say for example print 29 in LL and print I don't know 800 in l L there you go I get index one is 10 I get 29 is in LL yes 800 is an LL no so that is how we can Implement a simple single link list now how would we change this to a doubly link list well we would have to change first of all how the note works so we would have to say every note now doesn't have just a next pointer every note now also has a previous pointer so self. prev is is none by default and then we also have for each linked list a tail so self tail equals none now this gets tricky now especially because you have to sometimes or the first time you add something you have to make it the head and the tail but then you have to always keep adjusting um both values so now let's call this doubly link list um now for the representation function it does doesn't really matter because to represent this we have to go from beginning to end the tail is not important so we can keep this function exactly the same same for the contains function if we just iterate over the list to get a certain position it doesn't really matter I think the same is true for the get function the get function doesn't change at all and the length function doesn't change so this doesn't change this doesn't change this doesn't change and this doesn't change because we don't change anything about the list we don't have to adjust anything but we will have to change the way the append function works or method works and all the other methods that actually manipulate the content of the linked list now what we need to do here is if we append a value to an empty list we have to set the head equal to the note but we also have to say that the tail is equal to the head so we have to basically say now since we just have a single element The Head and the tail of the list is the same this is obviously the case however if we append something to an existing list um this is easier now because we just have to append it to the end so we can actually instead of iterating here we can say now uh the last note we we do basically the same thing that we do here with the prepend we say the last node is now a new node with a value the last note says that it points or has to point now to the previous note which is the actual tail right now so self. tail I'm going to show this here visually in a second again um safe self. tail next is going to be equal to the last note and self. tail is now the last note so think about it that way let me get my fancy drawing tablet again let's say we have a w link list I have this structure here now of course in both directions and of course we have a null pointer here and a null pointer here now we do have some values it doesn't really matter if I want to now append an element so add an element to the end of the list and let's say we have a uh in the list here we have head and we have uh tail um if I want to pend an element all I have to do is I have to create this new element I have to make it point to the tail as a previous element the default for the next is null anyways or none uh and now I have to just say that this element here instead of pointing to nothing points to this new note so maybe to to illustrate this better I have a new element down here I I let I let it point to the previous element which is the current tail I redirect the pointer of the previous element for the next element to this new element this points to none obviously and I then say that the new tail of my link list is now this that's exactly what we did here and this can be done in now we change the rum complexity this can be done in constant time similar to the preent constant time now the same is true for prepend but we need to adjust it so this is now basically the same um idea but we need to say again if self. head is none uh we need to set head and tail to the same thing so self head is going to be note value self tail is going to be self head and otherwise we do the same thing as before uh so we create first no is node last Noe or first note next is the head the head um is set to the first note but before that we need to say self head next is going to be equal uh or actually no self head previous is going to be equal to the first note yeah that's how we do it and again this remains uh in constant time now for the insert we don't don't really change much the whole structure is the same the only thing is uh I mean all of this stays the same the iteration but in the end we need to also adjust the previous pointer so we say new node equals node value new note next equals last next but now we also need to say new node previous is equal to last and then last next is new note so this just means that when you insert a new note you need to make sure that when you insert it here it doesn't just point to the next element it also points to the previous one and then you adjust these pointers accordingly as well uh let me just think about this again do we do this here we say new note new note next is equal to last next new note previous is equal to last no actually we need to also set the previous we're not doing this here my prepared code is not that prepared it seems so let me think about this here on the Fly while I'm um doing this I think we need to say before we said last next equal to La uh to new note we need to say last next previous is equal to new note I'm not sure about this we're going to see if we run into problems but I think this is what we need to do because as I said uh let's look at the uh graph here when I insert an element what I want to do is I want to cut these connections or actually before I cut them I want to create a new note I want to say Okay I want to point as the next element to this not note that this is pointing to I want to point to this as the previous element but then I also want the next element here to be pointing at me and the previous element here to be pointing at me and then I want to cut these connections I think we're doing this now if not we're going to notice and fix this I hope so um delete now here we actually do it properly here we actually progress so uh let me see do we have to change much well when I delete an element I have to delete the next reference but I also have to delete the previous references um so yeah so I also don't have this prepared in my prepared code okay so we have to do some things here on the Fly seems like I didn't invest a lot of thought into my w link list here okay but if I'm not mistaken the only thing that we should have to do here is we need to say last next next previous is equal to last next yeah and then last next is equal to last next next does this make sense not sure we're going to find out if not we're going to fix this this is also a nice experience here uh for pop we do probably the same thing so we just say iterate that's fine and then here we say last next is equal to last next next but before that we do last next next previous is equal to last actually I think this is what we need to do here as well we need to say last next next previous is equal to last not to last next I think and for the get we don't change anything so let's see now this is a doubly linked list we're going to still call it LL let's see if all of this still works first of all Yes it produces the same results which is good uh now how could we get is to fail um by inserting and deleting so by inserting all these values actually for the insert I should also have the case oh no actually I don't have the length so if I keep track of the size I can save index a size just append uh but that doesn't make a lot of sense here so let's say instead of appending we're going to insert we're gonna always insert uh actually I'm gonna append the first one but then I'm gonna insert at position one for example or actually I'm going to always insert at position one 10 or actually let's use different numbers 20 18 22 88 97 that's a zero not a nine then prepend and then insert again and then try to delete 18 and try to delete 22 and try to delete five and then pop one let's see if this makes sense okay you see there's a problem non type object has no attribute previous yeah of course because we need to also make sure this is now not relevant if we have the um if we have a none we need to make sure that actually we don't try to set previous so where did I do that I did that with delete so here we need to say um if last next next is not none then we want to do this and here as well if last next next is not none this was actually not the problem last next previous oh this is an insert okay so new note previous that is the thing if last next is not none okay let's double check this to see if this is what we would expect we append 10 so the first element is 10 five comes after that so five should be after 10 20 should be after 10 18 should be after 10 no actually not let me let me uh let me try to see what I would do manually here to see if this actually works so it would say 10 then I would say five and then I would insert everything before that so it would be 20 so it would be actually 97 88 22 18 25 uh then I prent prepend 100 and then what I do is I delete 18 I delete 22 I delete five and I pop one so I should have 97 88 20 okay 10 is not removed why is 10 not removed or did I make a mistake here let me see again does pop not work what happens if I don't do cop oh I forgot to insert 200s so this actually should work yeah okay actually it works because now I would just pop again I insert all these values then I prend 100 but I also insert 200 so I delete 18 uh 22 and 5 then I pop 200 yeah and then I end up with this so I hope they're not any more mistakes in my implementation but that is exactly what you would expect here so yeah this is how you implement a link list and a w link list in Python I hope you were also able to understand why the runtime complexities are what they are uh when we talk about runtime runtime complexity we always talk about worst case unless we specifically say we talk about best case and average case but yeah so let me know if you like this in a comment section down below so that's it for today's video I hope you enjoyed it and hope you learned something if so let me know by hitting a like button and leaving a comment in the comment section down below and of course don't forget to subscribe to this Channel and hit the notification Bell to not miss a single future video for free other than that thank you much for watching see you in the next video and bye