Linked Lists for Absolute Beginners | Sergiu Muresan | Skillshare

Linked Lists for Absolute Beginners

Sergiu Muresan, Knowledgeable developer

Linked Lists for Absolute Beginners

Sergiu Muresan, Knowledgeable developer

Play Speed
  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x
21 Lessons (3h 27m)
    • 1. Welcome!

    • 2. Introduction to linked lists

    • 3. Iterating a linked list

    • 4. Inserting at the end

    • 5. Deallocating (or deleting) a linked list

    • 6. Inserting at the beginning

    • 7. Inserting after a node

    • 8. Inserting in a sorted list

    • 9. Removing an element

    • 10. Reversing a linked list

    • 11. Detecting cycles/loops

    • 12. Recursive functions (counting elements)

    • 13. Introduction to doubly linked lists

    • 14. Iterating a doubly linked list

    • 15. Deallocating (or deleting) a doubly linked list

    • 16. Inserting at the beginning of a doubly linked list

    • 17. Inserting at the end of a doubly linked list

    • 18. Inserting after a node of a doubly linked list

    • 19. Removing a node

    • 20. Finding a node

    • 21. Reversing a doubly linked list

  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels
  • Beg/Int level
  • Int/Adv level

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.





About This Class

Learn the basics of linked lists in C programming language. This course treats the student as a complete beginner to linked lists that has a basic understanding of arrays/pointers and other similar concepts of the C language. What we want is, at the end of this course, to be able to use a linked list exactly like a plain old array.

After finishing the course you will be able to

  • Create the data structure for a singly and doubly linked list

  • Insert any element wherever in the linked list

  • Remove an element from the linked list

  • Understand how the linked list is allocated in memory

  • Properly deallocate the linked list

  • And to code other useful algorithms

Meet Your Teacher

Teacher Profile Image

Sergiu Muresan

Knowledgeable developer


Top graduate at one of the best Universities in Romania. Having noticed the struggle fellow colleagues have been going through to learn new topics, I started pursuing teaching as my main profession.

I have worked on many projects in many of the popular languages and frameworks out there. Having such broad experience from all over the IT field and knowing how to make people understand and learn, I decided to become the go-to person for people that are struggling to learn a new subject.

Life goal: change the education system for the better.

See full profile

Class Ratings

Expectations Met?
  • Exceeded!
  • Yes
  • Somewhat
  • Not really
Reviews Archive

In October 2018, we updated our review system to improve the way we collect feedback. Below are the reviews written before that update.

Your creative journey starts here.

  • Unlimited access to every class
  • Supportive online creative community
  • Learn offline with Skillshare’s app

Why Join Skillshare?

Take award-winning Skillshare Original Classes

Each class has short lessons, hands-on projects

Your membership supports Skillshare teachers

Learn From Anywhere

Take classes on the go with the Skillshare app. Stream or download to watch on the plane, the subway, or wherever you learn best.



1. Welcome!: Have you ever been taught Ling lists either at school or at university and couldn't quite understand them? Pointers to next Notes, roots and recursive functions all kind of foggy concepts. Well, don't worry. This course was made so that students can easy, understand, linked lists and start using them. Really Just like plain old raise. We explain in detail each and every operation that came down link list. Either be insertion, deletion on or just iteration with clear problems. Toe raise. By the end of the course, you will be able to not only just implement algorithms and easily use linked lists, but also figure out at a glance what is wrong with a piece off code related to them. Hope to see you on the last lesson of discourse. 2. Introduction to linked lists: into this. You don't want to talk about a way to store many elements off the same type in a very interesting manner. So you probably know about race by now, right? A razor? Just what if I have, for example, on array or five into girls? Well, what's that inside? The memory is just a block. Pretty big, continuous block off memory, right? Spit into five smaller blocks. One, 234 and five. Right, And each of these boxes are four bytes long, right? So we know that by now, and every single one represents a single integral, and we also have a way to refer to this array through its name. Let's say it's called a R R in this case, and it basically points to the beginning off the first element inside Ari. So it's just a It's basically a narrow toe, this point inside Ali. Nice. So we've dead in mind by knowing that. Okay, here's where this race starts and every single boxes four bytes long we can eat right? Wait. We can do whatever we want with it, but there's a different way to do all these. So, using this idea of having a pointer toe the start off on element and expanding that toe Every single element we can create a notion off linked lists. A link list is first of all, it has a route point or so let's call it the route. This is similar to our array point. Alright, this guy points to a box that has actually two or more elements, but at least two in most cases. One of them is our integral here. All right, so it's again. Four bites it could be, Could be a character. It could be a double. It could be anything else. But I'm just trying to make a parlor with this up top. And then the second box here is field with another pointed another arrow exactly the same as this guy which again points to another box that looks exactly the same as this one, such as this. And here again you have one into God right again for bites. And this guy again pointed points to another box and so on and so forth. So these are what are called linked lists. They're not a contiguous block off memories. You can notice they could be literally anywhere in memory just scattered around. Not like this guy. Work needs a really large and continues block off memory, and you might see it. Okay, well, nice. But we are kind of wasting a lot off space, right, Because we have to store these sort off arrows, but you'll see some interesting advantages when it comes to using linked lists over a race . Now, how do we actually implement this linked least sort of concept inside. See? Well, first things first, we have to make use off that structure, right that block off two elements. That has to be a destructive side. See? So we first have toe create that. That's sort of the building block for our link list. So I'm going to start with type death struck, and I'm gonna call it, call it note because it certainly seems like a node and also timed after the same name. And in between here, well, I have the information first, like the the the element from the Lory. Whereas, for example, refinery, we had an integral ready here we can We can have just a integral element can say here in with the X. Why not? And then the second the second part of our building block is that Pointer. So that point there has to be What? Well, it's a it's a pointer toe the same type off element that we are into the same building block. So it's a note point and we're called this. We're gonna call this next just because it is really the next element inside our link list . Okay, so that's nice. That's right, Mr. Building this If I try to build it, you notice I get on a roll that doesn't quite okay. I d doesn't want detectives, but the issue here is that noticed that I define here note and inside it's the finish. I'm using note again. Basically, this guy is too Instructions, First word if we're defining the struck the user data type er called note and then we're typed effing it toe this guy to load. But this operation, this last operation, is ah, like it can be done before actually finding this truck. So this is the thing that actually done first. Thus, we don't have this time death in here when we're trying to find that's why we have to perfect this week construct, just like in any old, like, just like if we were not using type death. Basically, I hope that's clear. It's kind of it's kind of interesting quirk. But now that we have this, we basically have everything we need to create a linked list. Try to build it. It's going to be successful, and we all we have to do it seem to start defining our list. They stopped. You're just saying there's a note? No, I'm gonna call it route. As I said in the in the beginning on this guy, I'm gonna say Route docked X equals a 15 and then want. And what what is our route dot Next? Well, let's define a little, But next, Why not? Let's say, uh, no, they say elemental or element to really cause the root is element one, and then you have the next ones right. The root is the first element, and it has the better 15 in it. And it has also the pointer to the next element, which is element to so don't next equals three address off element to and gets a here element to dot X equals iron ality. Negative, too. Let's and well, let's say we don't want any other elements inside are linked list, right? Like, let's say element L M two is the end of our link list. All we have to do is say, alum to dot Next equals no. But that's basically saying OK, well, you can stop here. There's nothing else beyond this element. NOS. Don't try to print this likeness. This doesn't seem to useful so far, right? This is just me. Just defining a striking has sort off weird pointers to each other. And really, you could do read out These pointers doesn't really make much sense, but we'll get there. So now let's try to print them on the screen, right? We have two blocks that construct are linked list we can simply print done with open. So are forced. Element is route the tax. And in our second element is 11 total tax. Simple enough. And now if I try to run this, I'm gonna get 15 and negative, too. That's fine, but it doesn't really like that. Doesn't really makes sense, right? I mean, all I did was create this point, or for what reason? Because I have them both here. Well, you remember with a raise. You just had one identify. When I said, for example, in array of five, we only had already toe work with a R R in the linked list world. That should be exactly the same. So what we have to do is get rid off our l m two because it doesn't really make much sense . Even though, yes, we needed toe allocate memory. But we can use one key difference, and that is dynamically allocated memory for linked lists. So how do we remove this element? Well, first things first I take a look at the print APs we here we have route one route. The first element is rude attacks the second element. Well, sure, we have a lamb to draw text, but we can actually access it well through route. We can say route dot next this time, because next is a pointer toe 11 to because I said it here next. And then I'm going to use the adult operator toe acts to just, uh, the reference this point or and get actual bad. But you could also d reference it and then say, Don't acts for example concerning just don't act like that. Sure, that also works is the same thing. Okay, so we don't We know I'm gonna have a limp to here. We can remove it from here, but we're gonna get Arabs. Of course we're gonna get out. So what should we do first? Well, first, we have to allocate the dynamical allocated memory to this new element. So he starts saying the other. So for them to How about you? You use Emma Lord to allocate memory for it Size off. Uh, note. But we need exactly this much space for our new element. And it's a point, and we don't have to cost anything. This works already, but here we can no longer access its value. Right? So we have to say, instead of alum doodle acts, we have to say root dot next adul ax equals negative too, right? And fruit Don't Next arrow next equals no. Right. So this is basically we have route which represented struck a building block. And then we say, don't next. So that represented the second building block. We d reference it through the air operator, so we get the value of it, and then we take a look at the well at it's information. It's X value. We set it too negative too. And we also take a look at its next point. Or since we know that this has to be the last element is inside our link list. We put it to be No. So now if you try to run this after removing that alarm to guy, you'll notice we still get the same exact values. 15. Negative too. And we only have just one wait tracks is our link list. Don't forget to add STD Leap to your includes here because we're using a Matlock. And don't forget to free our memories are gonna have to do here is free fruit not next. Because this guy has bean allocated dynamical these it's not gonna be automatically delegated and is goingto be basically a memory leak in our program. We don't want that. So, as you can see, we have the power off dynamically allocated memory. We can have sort off a raise that are distributed all over the memory wherever, and they don't have to be in a continue contiguous block off memory. You just have the element and a reference to the next and so on. and so forth until you hit. No. So this is the gist off a linked list. In the next episode, we're gonna take a look at how you can iterated through a link least and what are the advantages off a linked list over an array and so on and so forth. I hope you get, like, a general idea by now. 3. Iterating a linked list: In a previous video, we looked at linked lists. What are they and how we can initialize them in our program and sort of fused. Um, now, don't take a look at how you can eat rate over a linguist, since I did say that a linked list is an alternative toe raise. So there are three parts to iterating over ordinary. Similarly, there are three parts to iterating over a link, please. So we can actually make a sort of table to take a look at the similarities between those two. All right, so here's a simple table we have always on the left side and linked list on the right side . The first part toe iterating an array is what is in his initialization off that counter. But you start, for example, a four loop starts before in I course zero or a while loop before a while loop. You actually do. I equals int I equals zero, something like that. So we can note here for the authorization for the immunization part off Iterating Honore, we have equals 20 just like that. Nice. The second part for for an array is the exit condition, like some point, you have to get out off that loop. What's exit condition? While next condition is usually I less than And so if I is higher recall than end and being the number of elements inside that array, well, we can shoot out off that loop. Simple enough. And lastly, is the step. How do you actually go from the zero element to the first element from the first element of the second element that simply by iterating this I are incriminating this? I So if I go here and type in I plus Plus, that's what we're doing. Basically, those are the three parts for four. Similarly, for linked lists, we have these three parts. Now this int I equals zero desensitization part basically says Okay, start at the person positions years when I say array off I the first time I take a look at the first element of that. All right. Similarly, with link with linked lists, we have to have an element, and that should point the first element off our link lists. What is the first element off our link list? That's the root element so we can see here something equals to the address off route or just root itself. It's dynamically allocated that something is gonna have to be a note pointed forcing, I say no pointer and gonna call it current from the current element. Just like so. So that's the initialization part. Simple enough. If route is defined on the stack, you have it like that. If fruit is actually a pointer, you don't have to do the ampersand. So next up, I want to go over the actual step off iterating the linked list and we're gonna come back to the exit condition because that's a bit easier to understand that way. So here we say I plus Plus basically, we assign I to be higher with one than the previous value. Right from there we go toe one that denotes sort off that we went from the from the current elements to the next one. Right when we say our A off I Similarly we want to do the same here. But we aren't this current to change, not just I know just a number but the point of itself. So we have to assign current to be a different value and that value should be what current Adul next. Because that's the only the only thing that it can be. Really right. You have current is an arrow to this building block. But he said he's been building block. There is also narrow to another building block. Right? So what? What current can do is say OK, well, I'm gonna take the value from inside this building block and actually points to the next building block, which is here. This is what we're basically doing. So coming back to the exit condition since we're assigning it the next, Remember when I said that in a previous video that the last element off linked list is always going to be No, that's basically saying OK, well, you're here. You're at the end. There's nothing more from here on. What's so you can stop iterating the, uh, linked list. Right. Okay, So what's the condition for that? Well, since we are so since we are actually, um, reassigning current to be current up next at one point curtain Don't next or current adul next in this case will actually be no right since we have to have an end of this array. So if current is no because its previous one dot next was no. Then we can exit the loop. We have nothing else to do. We can just go home and we're done. So what we can say is current doesn't equal to knows. So do these step until current is No. Basically, this says if this sentence is force at any point, just exit the loop in order. So let's get toe implementing all that. So in the periods video, we had this simple link list with two elements 15 and negative too, right? So if I tried to run this, we're still going to get 15 indicative to under screen. Now what I want is to change these print F So instead of having to print up so I just have one inside a loop, we're gonna use a while loop simply because it's easier to understand. But then we're gonna go over a four room so that you can implement it however you want. So to start off, we need that means situation parts. So that same publishers, they know pointer current is well, what route is just not in Africa, because route is actually on the stack, right, So we have to get the address off that because current is actually a point or two. A note, right? Nice. Now we have the exit condition, which were in a place in the loop in the wild condition statement. It's a while. While what? While current is not know, do something and we're gonna do something. But the step, the step is what the step is over writing this current pointer, Toby, The next blocks where we refer to the next block up, we can say here current equals current hold. And this is a simple loop that will go over every single element inside our link list. And lastly, of course, we should use this current element toe print, every single element inside our linguist. So you can say here print deaf percent the back and say this current Atal X. So you want to get the information for the current element and then go to the next one? And what do you know? Current? That X is actually different this time because we have assigned it a different value, which is in fact, the next value, he said, are linked list. If I remove this lines and launch it, your your notice. I get both 15 and negative, too. And in fact, we can add as many elements as we want inside our link list. So So I have here changed the code a little bit so that we have free elements now. So right route don't Next is the second element which is allocated here, and it's very negative, too. And then route dot next arrow. Next is the toward element, and it's allocated here. Its value is 22 it's next point. Or is notes on that This kind now became the last element inside our linguist. So if I tried to run this, you'll notice I get these free values on the screen. Also, don't forget to three the memory after you have used it, so dot next adult next and here, as can see. Actually, it matters the order in which you freedom memory, because if I want to free this one first, then this guy would be basically invalid, right? And you would get the nettle if it ran this again. I get all three elements on the screen, so this is really nice. And lastly, like a promised, that's changes to afford group. So what's a four for Lopez. Simple for group has monetization part, which is what which is our note. Current equals data is off. Wrote my then it has on exit condition, which is this guy, right? And then it has an increment, which is this guy so just kind of places everything inside one place. It's a bit more ugly because while it has a lot of things here going on But if you understand, if you did understand the wild hope you will understand also the for loop as well. And if I tried to move this year and delete everything, they should work exactly the same as you notice here. So now you can see that it getting over a linked list really looks like urinating over an array. Just these are a bit more sophisticated ways you have to use toe go through the linked list , but it has the same basic, uh, parts to reiterating it, right. And then once you're done with that, can use this as just any other part of the ray. Except you're gonna have to usually use the or operator because current is actually a point . That is not just an element that you can do a friends with square brackets In the next videos, we're gonna talk about where you can insert inside the linked list or delete elements from the link list. Because, as you can notice, this is no the greatest way to add elements to the linguistic. For what you want to add, For example, 17 elements. It would be kind of tedious, because why would have root dot next arrow next arrow next, 17 times inside one single line of code, and that just doesn't look great at all, right, so we're going to create a function that does that in a future video. 4. Inserting at the end: So in the previous video about a link, least we added some elements to the linked list and we traded over every single one of them . Now, as you can see, the part where we add elemental Englishness kind off. Not great, because you keep on having ah, next Adul next arrow for every single image want to add. And that's just they're just bad, right? So what I want in this video is toe create a function that inserts elements inside our linguist. So we're gonna start with we can decide where to insert those elements, right? So as a start point, we're gonna simply try to add an element at the end off the list. So right after the elements has it's next pointer equal to know instead, off setting it terribly, it be Noel, we're gonna actually ah had a pointer to the next know that we're gonna add All right, so we're still by creating the function itself. We want a function that doesn't return anything. Let's call it insert at the end, right? And it should taking the route as a parameter because that's how we're gonna know what the linked list is. And I'm actually going to take a double pointer to the route. You're going to see why in a moment and say your node double point a route and well, I just want the value that I want to add right, just simply the X value off the notes that want not the noted serve because that we can create ourselves without any issues. Okay, so how do we actually add it? Well, the process is very simple. All you have to do is really get to the last note and change the next pointer Toby A pointer to your newly created note. That's all. So let's not first by creating or new note, but we can say here note point or new nodes. It's a new node equals and allocates. I remember using in my look sighs off node that I'm gonna say New node adul next equals note because that's going to be our. Since we're adding at the end, the new note is going to be the end off our list, right? So that's what I'm stating. It. I'm setting it to know. Then you have new notes. Adul Ax equals well our new value for adding to the list. So this is our you know, there's concern getting gonna actual warning cure. It says that the referencing Newell Point or New note. That's because Melo can return. No. So whenever you're using Emma, local Cielo or whatever else, you should check if this guy is no or not. Because, for example, there might not be enough memory in your computer to allocate the size of giving here. All right, so just do it. Simple. Check If you notice no, then I'm going to simply exit with the adult code one. Right? So this is basically a return from the whole problem, right? So he's just gonna basically stop its execution there and return with basic code one right ? It's as if I returned one inside the main function, but since we're not in the main fund, changed its exit. All right, so now we have our new note. It's properly created. It's nice, but right now is just a block, just a node, and it's They are and doesn't. It's not linked to anything just up in the air, so we have to use our route here. Now. Don't worry about the syntax off double pointers. What's a no double pointer, No double pointer is a note pointer toe another point off. So we have a narrow that if you d reference, it basically points to another adult, right? And then this arrow points to our node itself. Our route. Right. So when your dear friends, this guy, you get to this guy. But when you dear friends, them both you actually get to the note Was the next step what the next step is to use our our loop to it right over the whole list and get to the end note because we don't have the end note anywhere in our program. As you can see, we just have the root. The first note, Sultan notice. We're just gonna use our our little ation algorithm that we previously talked about. So something like this. As you can see, current is still a note pointer. But because route is a double pointer, I have to 1st 2 difference it once so that I get to that addle because I get to that arrow that points to our node itself. And I'm also changing the exit condition of the while loop because I don't want to actually end up with this guy being? No, because if these guys know I cannot really change anything I really want toe end up with after the loop. I want to end up with this guy being the last notes. When I did a friend's it, I can actually use it, not just because I can't dear friends in no value, another pointer. That's why Carlin Dalton next is different than no, that's what the exit condition is and not just current different than normal. So once would at the last node, we should have it inside our current variable. Now we can simply modify it. So now we know that current Adul next is no change it to be not know to be our new note or the address to our new note right is this is still a point, or that points to our new node. We just make this arrow. We just put this out of inside our ah, last block from the linguist. And then, well, we don't need to change the value. So that's basically older, is to it because we have the value in our new node here set. The next point is no. So that's correct on this guy has a value. Probably said from before it just that the next pointer wasn't was settled. Also, we had to change it so that it now the whole link least instead of just pointing to the current which was the previous last loud now points toe also Ah, upto actually, our newly created note, right? So now what I can do is deal it much of this so that we only have, um our route created. So I'm gonna just did it all days to say dot Next equals no, because right, I want just a single note. Is that our list? And that note is the root. And it's also the last note off our list that that's just how it is right now. And I also want to change the way the route is stored this and memory right now. And I said, This guy's stack this guy is, um, located on the stack, right? Because I saying your node route not just a point of not just a Matlock. I want to change that to be dynamically allocated this time due to the fact that I need a double pointer here. That's why Uh, and I cannot do. Add a survivor South route. I'm gonna changes to a note pointer route. That's going to be equal toe. Emma, lock off. Sighs off. No, And I'm just going to change these two arrows. That dear Frances, the actual route Why does the difference between adult and addle is that Adel's also d reference the pointer, whereas don't you don't have a pointer. You just get up. Ah, Struck member off that valuable, which is not the point. Right? So now we have our new route. We should change all these here, but these freeze are no longer values. I'm gonna simply remove them for now. For now, keep in mind we still have some memory leaks because we have Emma looks without freeze. We'll get to that. And we should also change the four groups so that instead, off the address off route is just actually pulled here. Because now it's a point of right and currencies. Appointer route is a pointer weaken. Just assign one to another and again the i. D. S warning me about that. So I have to change the code here so that it checks if it's no or not getting an exit with Let's say to this time doesn't really matter. This usually doesn't happen. But in production code you really want to check for this because otherwise it's very, very difficult to track down, right? So once this guy's no on, if there's any coat in between when you do Emma lock and, uh, actually using it Ah, many things could go wrong in between, right? And it's kind of hard to figure that out. This exact variable didn't allocate properly. All right, so route no exit to. And now we're assigning. And well, if I try to run this now, while much is gonna happen, we're just gonna get 15 right? Because we didn't use our insert and function. So we're gonna try to use it. Say, here he served at the end. Well, I want a double pointer toe note, which is our route. So it's going to take the address off this point. Or remember this point itself. Its value is on the stack. Right? You have. What do you have here? You have on arrow? Do a note. This note here is dying. It's nice, is no longer on the stack is on the heap. It's dynamically allocated using a Matlock. That's but this point or itself. This arrow, its value is on the step. Right? But what I want to send to the actually to the function is the place in memory where this arrow is stored. So you can do that. Adams off route. And then I'm gonna add the value. Let's say honestly, negative, too. And let's call it again with 11. Now, if you tried to run this, you notice I get 15 negative two and 11 in order in order that I've basically added them because first was just 15. And then the next note God created and it was the one that had the value Negative two and so on and so forth. Now we know that our insertion algorithm works For the most part. One thing that it doesn't really take into consideration is if the link least is empty. If we have no elements, right, Honore can also have no elements in the sense that doesn't have any initialize elements, right? Same thing with a blink list can have nothing. How do you denote that? Like, how do you say that? Ok, this guy's has nothing in it. Well, that there are some different ways you can do this. One that I really like is just simply saying that route is no. Is this a pointer we can set it to null and that he knows that there's nothing there. So I'm gonna comment all this and we're gonna do here no point of route because no. So we have no element and we have no elements, and we're adding negative two and 11 um, without insertion, without inserting anything. By the way, if we just run this, you'll notice that the problem doesn't crash. It works. The four loop reiteration works because why? Because current equals route since wrote is Nool? Well, exit condition has already bean achieved. So which is gonna check the exit condition we don't have current is no. So this is false. So it's going Just a quick follow up is not gonna print anything. So this works. Uh, no inserting any elements. If you try to run this, it's going to break. It's gonna break the program off course because we didn't take into consideration anything related to our route. We just ah, I take the point or and as you notice we passed in here. What did we pass when we said a true we passed a a Nadal Teoh Bonetto that says points to the other zero, which is it's a narrow that's basically lets its red. It's invalid. So there, if anything, it once. It's fine because this arrow itself is valued, so that's OK, but right, so doing this is fine. We get this addle, which is a no point, are basically it looks at some invalid memory right at the beginning of our memory, not invalid memory. But you don't have read access for it. Probably. And he are. You're trying to deal reference it, but because adults says the reference current and but the ref in its current and take the next pointer, his current is our This guy is at all that points to the beginning of our memory, which you cannot difference. It's going to break, so we have to take that into consideration how that's actually very simple. All you have to do is check if our if our current before route is not so. I'm gonna say here if Route de reference once right, because we have two adults we don't care about this guy if this guy should be valued right . But this guy might or might not be valid, depending on if there's any elements on the list or if there's no right, it does not gestational. So if did a fencing route gets us? No. Then what we want to do is tow place, something that's valid instead off. No, right. We can simply say he are defense. Root equals to our new no. And make that the beginning, the end and our new know that we add, Why does that work again? A double pointer to note is a narrow toe, a narrow right. It's this arrow pointing to this arrow, pointing to our note, which is this guy is invalid sort of points nothing. But this guy points to something points to that place in memory where our address for the route is stored so we can using this point. Or we can point to that memory and change it right. So by changing it now, it points to a valid place in memory, which represents a note. So once we've added it, we know that we don't have to add it again, so I can just say retard here. And of course it's if it's not know it can continue on as before. So if I insert this guy and so it executed, you'll notice I get negative too. So I just get that one element added in here. I hope you understood what's going on with, um, adding elements toe a linked list that does have no elements, right? This is why we passed in here a double pointed to know. Um, now, for example, if I add more elements, that should be fine. And then the if I tried to run this them. So this video is already quite long. So in the next videos, we're going take a look at first how to de allocate this memory because remember, we removed two calls to our free function which the allocate our memory. We currently have the M a lot here without any free calls, which is that which is really, really, really bad. Ah, so we have to fix that first. And then in another video, we're going to take a look at way how, toe insert at the beginning, off released or in the middle of it, or even have it all sorted out. Right? Let's say you're standing or descending. However you want to 5. Deallocating (or deleting) a linked list: So in a previously we looked at how you can insert elements at the end of the least, even even if the least has no elements, right? So there was our insert and function here. Now I did remove some free calls at the end of our program. Lastly, and now we have to add them back. Basically, we have toe de allocate the memory that we dynamically allocated using Emma. Look, we cannot let that be. But how do you do it with a linked list and you have pointers to point us to point us can be quite difficult to do that, so this is basically the simplest way you can do it. But it's a bit more difficult to understand whatever. Start with its greatly simple function, void the allocate and this guy takes in again. A dollar pointed to root, and that's it. That's all we need for the allocation process. I'm thinking again, double pointed to it because once we're done with everything, I want to set the the route to be the newer pointers so that we know that the list doesn't exist anymore. So now how do you start with that? The allocation process. I mean, we have pointers to pointers to pointers, to pointers to pointers. Can't we just the allocate everything in one go like, Can I just say free off? It's a D reference route once. So basically saying free off this guy within that work, like we're going to the allocate the first note, Wouldn't that be allocate all the other notes because they are linked together? That's what he's No, you're going to d allocate the first note with this, but the other notes are still going to be allocated, but they are no longer gonna be accessible, right? You basically the allocated that adul that adult, the doors, for example, to the second note. And now that that arrow is gone, you still have that memory. But it's up in the air. There's no longer a way to access it. So you really don't want to do that. You have to go to every single pointer and allocate them one by one and to the arcade them . You have to think about, um, the direction off alteration off a linked list. It always from left to right, right? So these free algorithm should free every single note from left to right in order. But we have to de allocate in such a way that we don't destroy our own memory. You'll see what I'll talk about. What I'm talking about in just a bit. So to start off, we're gonna eatery the whole list. So you probably know about this coat since I This is probably the third time I wrote this. Ah, in this ah video series. Basically, we have the route as the first element and then I'm going toe, have the exit condition be calling different the Newell. So basically, I want to go past the linked list because I want to eradicate it as a whole, not just stop at the end element. And of course, I want to go from one to another. Now, how do we How do we freedom mot inside this wild? You might say that. OK, why not? Why not just call free for every single current? That sounds like a decent. That's all right. So if I do for a simple free off current and I know let's do it like, let's do it before stepping for the next element. Hmm. There's something fishy about this code if you If you think about it for a second, what's fish about it? Well, you're freeing current. That means that the block the block that is referenced by the current point or is no longer available it's been destroyed. But then we are de referencing it here. But because Adam means the reference and you want to take the next pointer from a block that we've already destroyed, it makes no sense. So that's invalid. We cannot do that. Okay, so then how about moving it after we after we go to the next crime pointer? Wait. If we do that, then, um, the same thing will happen. So we step. We stepped to the second, for example, here's the force we go to. The second elements of current is going to be the second element because we went toe were signed in the current out Next, which is rooted out next. So this is going to be the second element. We freed the second element and then again when we returned to the Wild Hope we're gonna try to de reference it here because this is going to be the second Adam. And the second time we entered the while loop and that's again invented because we've already destroyed that block. So that's again Not not an answer. What we have to do instead is we surely have to have an arrow to the note that we want a free which is which is already kind of their or its current. Right? But we also need another adul the value inside this note that points to the next note. Right? So that we know what two assigned to current once we are Ah, getting to the next iteration. So what we can do is have two variables to animals, one off them points to They know that we want free and the other one is all current pointer and at one point is going to be the same. But we're going to go with the current point, or we're gonna go forwards to the next node. And with this exit, Daddy appointer, we're gonna de allocate the node that we just ah bypassed. How do we do that? Well, we can seem to declare here another variable. Call it folks from all Geneti and be equal toe our current right. So now picture this. We have We have the first note off our list right in the first note off our list. Uh, up until here, current and auxiliary are both at the first are both pointing at the same place and the same note, right? But then the next line after it says current equals current up next. Oh, so so current is gonna go one step further. That also, daddy. And then we're in this situation where we can't say simply. How about after we moved forward, they locate this block, and that's what we're gonna do dark in this book. And then this guy's valid because it's pointing to a no, that hasn't bean the allocated yet. And this guy has the allocated the place. Remember that we wanted I'm just gonna say here free. I love you, Daddy, after we have taken care of this part off memory. So now if I even if I enter with one element inside our least well, auxiliary is going toe point to the same first element to the least, this guy's going to become null because there's only one element. So ah, the forced them And don't next is no. And this guy still going to be the first element is still going toe point to the first note . So it's going to allocate that one note and since current is no, we're actually going get out off the while loop. So lastly, Well, we have to do is to change this to know. Did you know that? Ok, well, we're done. We have nothing else to do. We can just go home and really do our, uh least if you want you can see here de referencing root equals No, because, uh, this guy still still has that value in it, but it's no longer like it's no longer I located the memory that it points to that. I'm saying this because tunnel also of course, don't denote that our list is empty. So now if I tried to de allocate it off well, I'm gonna take the Anderson fruit. Well, running this we're gonna see any difference. But if we actually try toe, add our the bag function that takes a look at the memory and says if whether or not it's a memory leak, right, So you just have to add this code here at the end and, uh, these to an STD Leib So you're including defines by the way, that's in visual studio. If you're using, just see, that's a bit off a different process. But anyway, if I run this like that, I don't get any messages in the output saying that we have any memory leaks. If I comment this and red round again, you'll notice. I know it's a bit small, but I do get here free blocks off 16 bytes that have not bean the allocated. And those are our note, actually, because our note our 16 bytes long And of course, this delicate function also works. If the list is empty because if the list is empty, that means that did a fencing route once is gonna give us no. All right, so this is gonna be no. One. This is gonna be known. So not gonna enter the while loop. So what we're doing is just while overriding roots to be no, while already it is no. So it doesn't really matter. So if I tried to run this, you're not. If this doesn't crash and no issues, I don't hear. So this is how you d allocate a linked at least inside. See, it's a very simple algorithm. You're just gonna that I have to realize why we need on our jihadi variable here and why we cannot do it straight away. A bit off a homework for you is to try and de allocate this list in a recursive manner. Another record stiffness is not that useful in rial world applications, but it's going to make sure you understand this algorithm as well, right and why you have to do the allocated in such a manner. 6. Inserting at the beginning: in today's video will take a look at how toe insert at the beginning off a linked list. In a previous video, we looked at the insertion at the end off a linguist, and I suggest you look at that video before this one because I'm gonna try to keep it short . So our our list is empty, denoted by the route, being no right. And here we have a for loop iterating over every single element of the results. When we run it, we're going to get all the elements here. So to start off, we have to create a function. Let's call it insert at the beginning, and it's gonna take in the same parameters as the previous in social function. So just know, double point of route and on value. So the process off, actually adding at the beginning, Well, the first element, as you might notice in a linked list, is always the route. Soto ad at the beginning off a linked list is quite simply replacing the root the root note with the added node, and from they are from that other node link, the whole other notes basically link the previous route to it. that's what we're gonna do. So forces created node. Start with a pointer again. You know, I'm gonna allocated using em, Alok Size off, of course. No, here. Simple enough new node dot for adult acts is going to be our value and new note. Adul X is going to be What? Well, as I said, we have to link the new nearly added now toe the previous route. So we just can't say the reference route once, right? So this is going to be either null or, um actual note or an actual pointer to a note. So if it's not that, Mr the route is empty. But that's that's fine. That that just means that our newly created note is, ah, going to be also our last note inside all English, right? Because the new note at our next is going to be know as well. And also let's provide here of simple check so that we don't get any warnings return. That's a three. So now we have the new no. Do we have to think about well, what do we do with it? So we have a note that now links to the rest of the list, but inside our main here route. If we simply call insert beginning with this. It's not gonna change when we're still be stuck with that route, whatever that might be. So we have to replace the route, Uh, every single time. So I'm gonna have to do route. He calls to our new note so that in he or whatever code is using our link list is going to be using the new route as well. Right that that that has to be done every time. Okay, so now if you try toe actually call this functions will say insert at the beginning, let's say the Dodgers, so fruit is the 1st 1 that we pass. And then the value Let's say we want to pass the number 30. If we try to run this and take out the break point you noticed I get 13 Understand? So that works fine for one element. Let's see what it does if I call it multiple times with different elements or say dr in 14 and 15. But if I add them, you notice that the first element is the last one I typed. So that means that we have added So we have added 1st 13 So the Lord with 13 was the route and this new note got created with the number the number 14 and it became the road while also having its next value be the previous route which waas the note with 13. Right? So I got the linked list 14 or 14 13 and then when weather 15 again 14 with the route and the new root became 15. While that note with 15 got linked to the previous route, which was which is 14. That's why we got 15 14 13. So now we know how to add and add at the end and at the beginning, over a link. This that's no problem. And your notice with inserting at the beginning. Awful English. You don't have any four loops. So this is kind of an interesting property off relinquished whenever they tried toe ad at the beginning of it. Well, you have complexity one. You have no four groups, whereas we've inserting at the end. You do have a while loop here, right? 44 group if you want. So this is a pretty big advantage compared toa a race where if you want to add an element at the beginning off Honore. Well, you have to make space for it. So you're gonna have to probably either reallocate the whole array or just simply move every single element to the right. So every single one from the zero to index and one, uh, one index over to the right so that you have space at index zero toe adds the newly and any element in here you don't have to do anything. You just kind of create a node and link it and just change the route and that it you don't have to do an operation that depends on the size off the list. 7. Inserting after a node: So we looked at how to insert an elementary beginning at the linked list. We looked at how to in certain elements at the end of telling police. Now we're gonna take a look at how to in certain element in between two other note right or more explicitly after a certain note. So suppose we have this link list, which has elements to four and five. What we want to do is add the element, Let's say seven in between two and four, but so are the elements. Seven. The value seven. We first create a note here. That's nice and all. Then what do we have to do? Take a moment and try to figure out yourself what is the very to have to set inside this next point? Or and what else do you have to change inside the linked list? Right, So you might have figured it out at first. You have to basically copied this Ah, this point or onto here so that it also points to this element. So these two pointers are gonna be the same. And next you're gonna have to change this pointer so that it doesn't point to this guy anymore. It points to this guy. So if we remove this arrow here and we actually move it two over here now, this would really look like a proper link list where we have inserted the value seven or the note with the value seven after the Notre Value to which is our root note. But it's all you have to do is to create a new node that has the same next point on as the previous one. Right, So this guy copied it over, and then you change the previous next point or 2.2 itself. So let's stop. We have here avoid insert after After, what? After a node. So here we, instead of passing the route, we simply pass in the node that we want to abandon this new value to. So I'm just gonna go here a simple notes. So not double point or just a simple pointer to know because I don't really need to change the actual point are in there. So this is no note we want to insert after and then it's the next is the value that we want to insert after the note. So what do we do First we have to create our new note. Right. So we're gonna do something like this, you note again equals I'm gonna use em. A look size note. Not much different, then. New notes. Adul X is going to be our new value. Right? And new nodes. Adul next is going to be What is? I said we have those tube. We have the new node, right? Then you know that we want toe ad, and then we have the previous one that it was ah, that we want opened it too. So you first have to copy its next pointer. So we first have to say the new note. Adult next equals no adult. Next, Right? So now these new node points to the rest. Like to the next point or after the know that has been passed, right? Same as this note. So they both sort off point to the same note. But we're going to change that by overriding the value inside. No dot Next, which we're gonna make that be our new note. All right, so now we make the previous note no points to our newly created node, which points to the rest off the list as if nothing else happened. Right? So this guy is still the rest of the list is not affected. We only are changing this single note, which is pretty nice, I think, because if you think about it, if you only need to add a note at a specific point inside a linked list, that operation doesn't require any Ah, any loops, which is again a pretty big win in certain situations. So again, I should also check if what we got here is no that is, know that I should return some value. It's a Ford. This time we created the note. No, that'll next equals new node. And, well, that's basically the whole function. If we try to, for example, let's make what we had in the example. So we had, ah, least off free element. It was 24 and five. So I'm just going to simply add at the end the value too than the Value four and then the value five right? And then what I'm gonna do is call insert after well, after what I want to insert after the value, too. But I also know that the root has to be two because that's the first element. So I can just say insert after route the Element seven. And now if I tried to run this, you're not just I get to 74 and five and same thing happens. If you try to insert after, let's say the toward element from the told them and they're gonna do Route Arrow Next arrow . Next. So that's basically going toe the root adult. Next is the second element and Route Arrow Next arrow. Next is 1/3 element. If that makes any sense, because ah Adul next off, the previous element gives you the next element. Now if I tried to run this, you notice I get seven Indian. So with dysfunction can also add at the end off a linked list. Because what happens if you try to add at the end? Well, let's say we want to add the value eight here idea and right Well, the first great a note. That's simple enough. You first copy the value from this point are toe here. But the values No. So he was gonna be also know nothing. It doesn't point to anything and then all you do is make this previous pointer point to our newly created note, and that's why you get to 45 Well, in that case for seven. So if you want to, for example, add forced the Element seven after the number two year and say, Add after the node that is the root, the Value seven. And then insert after the adul next battle next at our next three times because the first element is to the second element is seven because we've already added it. The third element is four and only. The fourth element is five, which is the last one, and that's where and we want to add it after or five year, and then you have your the number eight. So if you try to run this, you notice I get to 745 and eight. So this makes sense now. This will serve as a building block when it comes to making sorted linked lists 8. Inserting in a sorted list: So we looked at many in social functions for our linked list. Now we can use most of them toe actually insert a new element inside a link list in such a way that it keeps the linked list sorted so that we always have a sorted linguist. So suppose we start with this link list. We have to seven and 92 is our Route nine is the end of Village Smith. And we want to add the element. Let's say eight. So you want to add elements? Eight. How should we proceed with this? How do we actually figure out? Where do we need to actually place it inside our link list? Well, we first have the node as usual. We just have to figure out where we need to link link it to. So we probably have to enter it over the list, right. We have to have an on it aeration. It goes over and provide some checks for us. Um, no checks are going kind of interesting. Let's think for a second. If we want to add this note inside our link list, we first need to do what we first need to change this note the know that has the value. Seven. Right. So we need to change this guy, and we need to change the actual, uh, next point or off the new know that we have created to link to them. Next, uh, the last note off the list. Right. So we have to change the stool. So how do we figure out where we have to place this now decide our link list? Well, if you take a look at a comparison for every single element, you'll see a pattern. So if I compare eight with two, that's it is hired into so I can say taken place in here, the higher then sign right Then if I take a look at seven eighties again hardened seven, so that's fine. And if I compare it with nine, it is actually less than nine less or equal than nine, actually. So you're noticed that if I eat a rate delink list from left to right, we have to stop at the point where we find a note at which this comparison is through at which the number that we want to add is less than or equal to the next nodes value and this is going to be in in a sorted link list. Suppose the linked list is already sorted. There's only going to be one change off the truth value off these comparisons, right? At only one point, we're gonna change from this number being higher than all the rest and being less than or equal to than the one after it. After all these numbers, right. So suppose in our iteration current is currently the first node on our linguist. Well, at dedication, we have toe ask if seven is higher or equal than eight or eight is less or equal than seven , which is false. It's force. We can continue moving forward before current value. So you can say OK now is eight less or equal than nine? The that Did that change in comparison occur? Well, yes, yes, it did. So if it did, then we stop. What? We stop the alteration and we modify whatever we have to modify, which is actually just changing this guy two point toe our two points to our new node healer. And then this guy point to current arrow Next, which is the rest of our list. But in fact, we have done that already, right? Remember with the insert after hey, start a node function? Yeah, we have done that so we can simply call Insert. After for this note, my second conserved this note after this note, there's one single issue with all that, and that is when you have a number that is less than the first element, less than or equal than the first element inside our link list we have here, for example, one well, at that point, we have to treat it as a special case because we cannot look at a note that is before our route. The route is the first note off our linguists remember, So all we have to do in that situation we have to treat it as a special case and just simply insert this value at the beginning off the list and saving happens if the list is empty. But we are going just insult at the beginning, because if the list is empty, there's no point in any comparisons. So this is this would be the end result if we want to add one. But this will be a special case now, before we get to the code. I have made a simple mistake in previous videos, where instead of saying Exit four here, I did say return for But you might notice that, uh, dysfunction itself only doesn't return anything. It's returning void. The complainant let me do that due to the fact that void behind the scenes is actually going to return integral either way, but that you shouldn't really do that in 99.99% of the cases your relation with that. And that's just mistake I have made. I meant to just exit out of the program with the arrow code four here and same thing with insert beginning I I changed it to be exit three. So let's get started with our function. So no say here, avoid insert sorted. I'm going to still get a double pointer toe our route and the vendor that you want to pass . All right, so we're gonna first street. Those two special cases The 1st 1 is if the list is empty, right? So if our root a root note forced the value, no, Then I want you to just insert the insult, our value at the beginning, and that's it. That's all we have to do at a point. Because if the list is empty, you can insult that as the first element inside the list that no provided. I can just return out off this function and also inserted the beginning. If the first element is, um, higher or equal than our value, right? So if we have that, we want to insult, for example, if you are released, starts with it too, and we want to start the value one, we're gonna treat a case here. Imagine and say here, four. The reference to root ones that's going to give us a what a a pointer to know, not a double point or just appointed because we have already referenced it. Remember that double everything? Yeah. So if you dear friends, that double arrow once you're only going to get a sink, a simple average just appointed to note, and then you can just simply say adul acts and that's gonna actually access the value off the first element off the linked list. You can also say if this is too complicated, it is kind of weird. You can also say double D reference and you can say dot acts if you think that makes more sense to you, since this is a double pointer, if you do that, if you do dear friends it twice. You should get to the actual notes. And you can didn't say get the ex, uh, member from that note, right? Look into that. And then we have to check if this guy is higher or equal, then our value, but because if you want to insert, um, one and the first element has the value, too, that that should be true. We should actually start at the beginning. Same thing if the value is too and we want and are beginning has the value to as well. It doesn't matter if you started after the first note or before, because they're the same thing and in terms off whether or not they're sorted are gonna be sorted. Right. Okay, so those are the special cases relating to the first element off the list. Now we have to get to the actual algorithm, which is going to either it over all our no so simple iteration as we did before. Just we get a current pointer, which is gonna be the first note a pointed toe, the first note, a single pointer. And while our current Excellency current at all next is not know I'm gonna get out this wild group with current being a being the last note off our list, right? Since if this centers is force, that means that current arrow next is no. That means that that current is our last element or not, linguist. Nice. And of course, we want to have the step be Colin, because current battle next as before. Now what do we do here? Well, as I said in this little drumming, we have to take a look. But we have to take a look. This is our current, for example is here. We have to actually take a look at the value off. Nine. How do we do that? Well, you can access the value of nine. You can say see or current dot or arrow next. All right, current Adul next is going to be a pointer toe our next note. And if you say colon Adul next Adul Axe, you're going to get the actual nine here. So if I do current Adul next, right? This is our next point and we know this guy's not know because off our wild condition, this guy's not know. So it's fine. We can de referenced again and get its value. So if the next notes value is what is higher or equal than our value that we want toe ad that stop right there, we want to add it right there, right at that position. So if this happens, if this happens, we can use our insert after function, right? So he's sort after is simply going to insert after a central node the value that we give it and what we want to do is insert After what? Well, since we have this situation, he are you want to simply sort after our CR, after all, know that has the value. Seven we don't want to insult after our know that has the value nine in the situation, right? So I say here, after the current value just adds just inside the value that house that has been given to us by the collar and after you have inserted a value in here, you can simply return because there's nothing else to do. All right, so let's try actually using this function. Let's see if I just want to add first. I want to add just one element. Just passing the address off route, which is. And also it's an empty list and let's say one and a verify. If I try to run this, I'm gonna get five on the screen. That's nice. Now what if I want to add the value four after I have five here. Well, if I tried to run this, we get four and five, right? So even though we have added them in reverse five and four, we got four and five inside our lists. What happened is first, the list was empty, right and value was five. So it got added at the beginning, and then the the least had only one element in that element. Happened to be five here, and the value was four. So it also entered inside this if state month and inserted that value at the beginning. Nice. Now what if we want to add another number? Let's say we want to add the value, um, one again at the beginning. So if I tried to run this, I'm going to get one for five. Nice. Now, as the last test. What if we want to add a value that is higher than all the other free here? If you do, copy this, say, seven. If we try to run this no, you'll notice that we don't get any value. We get just one for five or 17 and get added anywhere. Well, why? Why did that not work? That's what it is, actually very simple. So we iterated through the whole list and we've never encountered this if condition to be true, right? Because what does that? What does this say? Basically, there should be a value inside our least that is higher or equal than the very that we want to add. But seven, it's never gonna be higher than any of these previous ones. So what do we do if such value? We have to add it at the end off our link lists, which we haven't done. So right after our y loop, we shoud we should adhere his cert after our current value, the value because we know that after the while loop current at all next is equal to know which means is the is the last element, and to add at the end of the least or we have to do is call days in sort after function to add it after our current, which is our last element, the better that we want. Right? So now if I try to run this your notice that we get seven right at the end, there's now that the algorithm is completed works we can add as many number that we want, and we're gonna continue having a proper link list that is always sorted. This is why the example that I showed at the beginning, uh, had a sorted linked list. This algorithm is not gonna work if you have a if you don't have a sorted linguist because you notice that I iterated until all this until this condition flips. But if the if the link list is not sorted, that condition keeps flipping many, many times, so we don't know exactly where we have toe place it now. One quick sort of improvement toe. Our code here is Well, you might notice that this train of cold is the same as this line of code, right? We're still adding current and the values still divided you actually got from here So can we make it so that we just have one of these instead of two? Well, yes. Instead of having the function called and the return, we can simply break out of the while loop so you can see here break. And if we break out off, this current stays the same, right? So then we get to this runoff code, which simply adds the element on the current positions of the current position at which this guy was true. We have the proper value because current doesn't change after we break out of the while loop. So now if I tried to run this you notice nothing has changed. We still get the same sorted linked list. But of course, these are ordered in ascending order. You can have them in descending order if you want to just have to change the sign. The comparisons here So I can change this to a less than or equal and less than or equal to try to run this. I'm gonna get 7541 And really, this condition can be generalized for anything. You can't even compare strings If you want. Your notes can have not only just integrates can have very complicated structures. And you can order them with this simple condition that you have here. Over here. These are the only places where you actually check something related to the information off the linked list. Everything else everything else is basically applique about old, uh, link list with any sort off data type in them. 9. Removing an element: So in the previous videos, we looked at how to insert an element inside the linked list, right? Beat at the beginning, at the end, or somewhere in between. Right Today we'll take a look at how toe remove such an element so that you know how to manipulate the linked list on your own. So here we have an example off a blink list with just three elements has one free and six. And what I want to do is to remove the element free from the linguist. Take a moment and think for a bit about what we need to change inside a linked list inside the link list itself so that this element doesn't have does not exist anymore. You might have realized that actually, toe remove the element from the link list is very simple, since we have one that is linked toe free and unfree that is linked to six or we have to do is to change, uh, toe what node one is linked to. So instead off pointing to free, we can simply skip over free and point directed to six. All right, so basically copying the pointer from over here onto this position, right? So if you do that, the link list is going to simply look like it has two elements, right? It has the element one that is directly linked to the elements. Six. And that's it. Now, one more thing you have to do if you dynamically allocate the linked list elements are gonna have to freedom memory from inside this note previously, because to doing all these modifications, right, because this memory is still going to be allocated because we used m A lock to is sort of these elements might remember. And if we don't the allocate, we simply lose the only connection, which is really this guy, this little pointer here toe our dynamically allocated note, right? If we get rid of this, there's no there's no connection to it. And we can no longer uh, the allocated. So you start by implementing it. What we want is a function called say, remove element. And this function should take, as usual, the route a double pointer to root because, well, if there's just one element and we happen to remove that one element, well, we have to do is simply override the route toe being no That's why we want a double pointed here and then the value that we want to remove Now that freedom that I'm gonna present here is going to remove the first occurrence off that value. So if you want, for example, something more specific that for simple removes the last element or old elements that have this value are gonna have to actually tinker with it yourself. All right, So how do we start here? Well, the first thing is to check if we have any elements. If we don't, we don't have to do anything is I don't our little function. So we can simply say if yes, for the defense ing route once gives us a new one point, are. So basically that point of the trip point toe a node is no, it doesn't point to anything that means that are least is empty, right, as we said before, so we can simply return out of it because there's nothing else to be done here. We cannot remove any elements from a from an empty linked list. Now, going back to this little drumming your notice that when we are searching for the value free, we are actually modifying the node with the value one. So the previous node behind free. Therefore, we have to sort off, look ahead off the current know that we're working with. So if we are, if the current is here, we're gonna have to check if the next note has the value that we are searching for. If it does, we are going to change the current note. This guy, this is the only ah pointer that we have to change for deleting in an element in a linguist . Therefore, we should forced literate over the link list. I'm going to use a four of this time as previously we used while loops. And this is going to be basically equivalent to that to those wiretaps. So how do we start? Fourth, we have to initialize something years they're gonna say node point. All current equals the first point are no or the first note off our link list. So dear friends wrote once And what's the exit condition? What? Since we are looking ahead, right, since every single time we are checking if we if countries one for example, we are checking if freeze the value if current is free we are checking if six is the value were searching for. Well, that doesn't make sense toe for current Toby to ever be our last note. If current is here, there's nothing ahead of it to check. So there's no point in executing what's in the loop if current is the last element. So we're gonna exit. So our exit condition is going to be current. Arrow next is different than no, not just current is different than all right. If current is the last element we can exit out of the four, there's nothing else to be done, right? The current note has been checked previously. Okay? And then the step is current equals current arrow. Next. Of course, I know this is it is quite a long line of code. I don't really recommend using it, but if you know what they're doing, this is This is fine. I think it can be very readable. And it's very compact. Nothing. Okay, because we for a while, if you still have toe, use three lines of code for all this thing. Okay, So what, we're checking? Well, if current is one, as I said, we have to check if current Adul Next Adul Value or Arrow X, is the value that we're searching for, right? So I have to say here, Eve current, Adul Next, right, that's the free they are Adul Axe. He's our value that we're searching for to actually deal it. That's why we're so we're basically looking. I had one note. So if that is the case, if this guy is the one that we have to remove well, let's store it in a variable first and I say no point or to remove equals What current arrow next current auto Next is the know that we want to remove. Then what we're gonna do is change current Adul next. Because remember current Adul Next is this point all right? And we want to call free on this point of That's fine, But we also need to modify it, right so that instead of pointing to three points to this six here, So what we have to do is first say, current Adul next equals what? Well, what's what's Ah pointed to six. While the pointer to six is actually this guy, right? This guy and this guy are the same and how can we refer to this. Well, we have current here. We can say current. I don't next that gets us to he r toe the note of developed free and then current arrow next arrow. Next, get us to this point, right. Basically get us toe here, but we have the pointer to it. So we have the address to that note. So what I can say just current, I don't next equals current at our next arrow. Next, basically is keeping over one off the notes. And now I just kept over the note. I didn't actually freedom memory because I know it's dynamically allocated, so I have to call free on it. That's this is why I use here on auxiliary valuable to store this current. I don't next, but this is the one that we if we had just over it and this value, we would have lost the point out to our note. So we have to store it somewhere here, for example, to then call free on it. So it can. Then all three are so here in the main function. We have our link list, which is initially empty, and we add the's free numbers are sorted, but I'm adding them in a sorted order. It doesn't really matter. So if you are honest, I get one free and six on the screen. Those are the elements on our linguist now. If they tried toe, call our remove element flunk, son. And, of course, passing the route. And I want the value. What? Free to be removed. If I tried to run this notice, we get now one and six on the screen because, well, we had the list 136 And then we removed element free and it automatically linked one to six . So it skipped over free and all story also freed the memory. Now there's one edge cases we haven't treated here yet. So what if I remove one here? What if I remove the route itself? If I try to remove route and run this, you notice that we still get 136 or nothing got removed, do toe, even even though we did call remove element off one. That's because we are always looking ahead. But, uh, when it comes to the root element, there's nothing to look ahead from because there's the first element off a linked list so we have to have a special case for that which should be somewhere around here. So I should say here if, uh the reference route take its value and check is route the value that we are trying to remove. If it is well, simply do the same thing as we did before. Note to remove equals what equals route. The referenced ones then route to the referenced. Once overwrite that Toby root beer first, once at all. Next. So basically make the root be the next element. It's and a linguist. That makes sense, right? If we remove the first element off our ling list, we should really have the route point to the next element. And that's going toe are allow all the other operations to work properly inside our linguist. And then, of course, three. That memory. Never forget to free the memory. And, of course, we can also return here and return here because there's nothing else to be done inside these after, after all this has been executed. So now if I tried toe run this, you notice I get free and six. So just keep in mind about that special case when the route is the one noted that we want to remove, and that's about it. We've removing just one single element from a linked list. As you can see, remember this. This guy just removes the first element that it finds with value given. So if I have here, for example, to once at the beginning, off the least, if I try to run days, you notice I get only the 1st 1 being removed, and only if I call this function twice. Is it going toe? Actually change and remove both once, right? So if you want to remove all the elements with such value, it's a little bit more work, right, and I suggest to tinker with it a little and take a look at how you can actually do it. But as you can see, it's fairly trivial to actually remove element. All we have to do is treat the special case, then a simple loop that stops at the last element because we have to look ahead due to the fact that we have toe changed the note before it. And we have to freedom memory because it was a chemical allocated 10. Reversing a linked list: interested. It will take a look at how to reverse a linked list. So basically, if I have a linked list that is one free and six I want at the end instead of the roots being one to be six, right? So that the route has changed. And then six to be linked to free and unfree Ling Tau one and one gonna be the end off our list. How can we achieve this? So we're gonna have to have an alteration, right? For every single. Now we're gonna have toe basically reverse the arrow. What's that? What does that even mean? Well, that means that, for example, for our general case, you know that is not the first or the last note. Three. In this example, we have to change the next pointer from pointing to six to instead points toe one, right? Just excellent. Um, well, this is the oppression. It we have to do every single interational. Now, before we get too into implementing it, let's think about what information we actually need to set this point. Toby, The previous one. Well, first we'd a pointed toe our current notes. Soto, our free here. Definitely. Then we need a pointer to our previous knows. Because remember, with linked lists with this type of linked lists, you cannot actually go back. So you have this? No. Would you cannot actually go back toe one, right? You only have four more that owes. So we're gonna have to have another variable to store the previous pointers. That's at second. But also, after finishing this operation where your overriding this value this little pointer here, you're gonna have a problem because this point or is no longer going to exist. So we need free valuables to basically reverse the arrow off old the note inside our linked list. So therefore, I'm gonna call them previous, current and next These are gonna be our three variables current you probably have seen before. So that's no surprise. And you're not. Is that at the beginning off our link list we have to set? Well, we have to change this guy. So here we have toe change this arrow from pointing to three to actually no point to anything so that it will be No. So we can simply if one is current and previous can be no, and then we can set it to current Arrow next equals previous and again here when six is current, then next is going to be no. So we can check that for our end condition for exit condition in our wild loop. So let's get to implanting. So is before we have here our functions for adding inside a linked list. I have called insert and three times here. So basically we should get the link list 13 and six that we had an example. If around is I'm off course going to get 136 understand? We want the results to be six free one after just calling our function. So no more, no other modifications. Let's create a spectrum fold, avoid, uh, reverse. And it's going to take again a double pointer to root due to the fact that you are going to change the route. So we need a double pointed toe where the root is and how do you start? Well, first, let's define our free variable. So first we have the previous so no point of previous which I, as I said, since we're starting at the root before the route, there's nothing so we can just say no. Simple enough that node current You've seen this before. We just pointed Toe is just the referencing route once, basically, we get the first note and I said we need the next pointer but this kind gonna actually initialize and declare inside the loop four star with the loop So in the while loop inside the while up What's the exit condition? Well based condition is when what I say when current is six that find So it can be the last note Because if countries six we still need to move its arrow from being Noto actually pointing to free So we have to have a change something like this. Therefore we still need toe it over it. Therefore our exit condition is not when current Adul next is no But when current is no When we went past the linked list and we're done so if current is not know then we want to execute Even if it's the last note in here, I'm actually going toe declare and set the next point. Also note Next is goingto be equal to Cordant Adul next. That's simple enough because current is not know that means current I don't next will be something beat Noel or another note that sounded good. So now we have that situation where we have those three pointers all pointing to the right thing. Right? So, uh, current is our route, then Previ ous is actually no, because there's nothing they are. And next is the next node the second note from the link list. So here we can say current arrow next. That's roots next point, or Toby equal toe previous. So basically, that's where we're reversing that addle. So now we have these three pointers. We basically have to step forward. Now we know that next is going to step for because we have already set it to do so. So just need to set previous and current current is very simple. As you've seen before. We just have to say current equals next or basically current equals current Adam next as before. But again, this is kind. I don't exchanges in between. Ah, these sentences we have to sort off say current equals next because current I don't act is previous and then we have to change previous as well. So previous is going to be equal to current, but you'll notice that current already changed here. So we cannot really do that because previous is going to be next at that point and they're just going toe cause a lot of issues. So what we have to do is set previous before actually setting current and then setting current toe the next pope. We have these three pointers. We first move with the previous toe, the current, and then we will move with the current to the next, and the next automatically moves to the next next point or over here. And that's that's almost everything. If we try to call this function, so here, reverse off route and try to run this. Do you notice we only get one on the screen. We get one due to the fact that one was the previous route. But now one is no longer the Route one is the end off our link list. We have to also change the route inside our program. So here, after the while is done, we have to set the route. Toby, The last note inside the A linked list. So and say here root equals What exactly is root equal to current? Well, no because it can't. We can't sit in tow current because we know that if we are done with this while loop current is equal to know right, because that's why we exited. So definitely not current. It has to be the previous No, because previous toe the after the least is the end of the list. So previous would be our new fruit after the wild appear. If you know Rhonda is, you'll notice I get the reversed length list properly. So get yourself 136 we get 631 So that works nicely. And what is nice about this solution is that even if root is now, well, what if the linguist is empty? Well, nothing really is going to happen. We're going Just be calling this current is going to be no. So the while loop never executes, and then the route gets set of previous. But previous, since the while never executed previous is no here. So we just kind of set the route to know all over again. So you don't even need to check if the list is empty before executing the algorithm that freedom automatically checks That which, in my opinion, is very nice and clean, and you don't have to have any sort off were the edge cases. You can see this is a pretty fast solution because it doesn't require you to reallocate the notes or any sort of thing. I want you to try out to actually do the reverse algorithm only using these functions that we've created here it It's going to be probably much quicker to design the algorithm. You just realized that it's much more inefficient, so that's why we're doing it like so. 11. Detecting cycles/loops: so suppose we have this situation where we have a link list with five elements or 11367 But at the end, instead of having a no point or this guy actually points toe a note from inside the least this is what we call a cycle Inside are linked lists. As you can see, this guy just kind off cycles around, around and around. And if you were to eat rate this type off link lists you were, you will never get to the end of it, right? It would just continue to move forward and forward. Now what we want is before iterating such a linked list is too. Check check if there such a loop. And if there's a loop like this, do not integrate it off course. Because if we do, we're going to stand in any fit. Look, So there's an algorithm for that. It is very, very, very simple. And it works all the time. And that is to first get yourself two pointers, right? I'm going toe, actually get a green and the red marker here to denote those pointers right, and then first initialize them to be at the root you're gonna have here. The green pointer and the red pointer. Nice. No, they're going toe it right over the link list. But they're gonna iterated at different speeds while the red pointer is going to go one step at a time. My simple just Redpoint r equals Redpoint or Adam next. So that's the usual. The green pointer is going toe iterated at double the speed. So it's going to say Greenpoint r equals Greenpoint or Anil. Next, Anil Next, my So it's gonna go from 1 to 3 to seven and someone and so forth What we have to check every single time the eat a rate is if they are the same if they are pointing to the same node at any point in time, Well, besides the beginning, that means that we have a loop because, well, the logic is simple. Here, if the least doesn't have any loops than the Greenpoint is going to eat it over the least very, very, very fast. And the right point is going to be, well, basically and 1/2 half off the list and there should never meet. Makes sense. I hope so. Okay, so if you have. Ah, Cycle eight. This just right toe to toe used algorithm here. So first the green pointer is goingto go two steps is gonna go. Not to hear about two. Here's is gonna point to this guy nice. Then the red pointer is going toe point to the next note. That simple. Then the green pointer is going to go over to notes, is gonna 0.27 Then the red note is gonna go to three. Now. Now they are here and here, so they're pointing to different note. It's fine. We can still it right. The green note is gonna go from seven to what's the next month or the next one is one. And the next after, let it freeze. There's gonna 10.23 and red note is also going toe literate. Over. Freeze are gonna go to six. Okay, so now the green point is that three and the red pointer is at six, respectively. Okay, that's fine. Then the green Poynter comes along and jumps over six or goes to seven. Okay, so that's fine. But after the red Poynter comes along and jumps to seven, they're both in the same place after on exact number off moves moves for every single one of them. Right? So if we encounter such a situation where they're both in the same place, we can just say that the least has at least a cycle, so we cannot really iterated. So I have here the linked list in the example, So Ah, 11367 And now seven doesn't point to anything. So if around this it's fine, right? But if I said it to point to something just like so, if I try to run this, you notice this keeps on going forever and ever and ever, and it never stops what I did here. Well, if you count the number off next, you're gonna figure it out. But basically you have wrote right, which is one. So Ryutaro. Next is one again. The 2nd 1 then Ryutaro next is three. The Route Arrow next three times is six. And I wrote our next four times is seven and we want to set the next pointer for seven, which was newly before Toby. The 2nd 1 And the 2nd 1 is route. That'll next. So there's no logic behind this. All right? So Now we need to detect this before Iterating because it's going to see we're just ending in an infinite loop and we never get out. So let's create here. A function called int has looked. Life has loops, and I want Since we're not changing anything, I don't want a double point of what we just need a simple point or two. That's fine, right? And if that's no, that's no, that's so be it. So that I said we first going to start with the two pointers that are both gonna 20.2 routes we have here. Note point. I'm gonna call it Slow the red guy because the guy was the slowest one, just iterating over every single element of the list. So the guy that snow is going to be again loot and the green guy I'm gonna call it fast because that guy, it rates double the speed as a slow, uh, pointed. And it's also going to start the truth now. We should have a while, I hope. Of course, we've on exit condition that I'm gonna get to after we get to the alteration. What's the duration for the while? Well, as I said, first the slow guy moves one. Ah, one note forward. So slow, equal. Slow arrow. Next Nice. Okay, let's find. Then the fast guy moves to note forward so fast equals fast. That'll next. That's just one note for one. And that's two notes Forward. So you get this guy? No. After all this, what we do have to check is if they are the same. So after we moved both of them once we have to check every single time if they are the same . So if slow is pointing to the same address as fast there, pointing to the same note, we know we have an way. No, we have a loop inside our linguist. So we can simply say return one meaning return. True. Now for the while condition. What should be say here? Well, we don't want to eat straight forward if we don't have where to eater it too. So if slow is no, that we can t take it anymore. Same happens with fast very fast is no. We cannot go any further so and fast is not know But there's a simple catch. If the linked list looked like this, we don't a cycle itself. We would have a problem if the fast point, it would be a seven. And since it's not no, we can't have fled it literate. But, ah, what does the line that it rates do? Actually, it goes to the next note and also skips over it. But after seven, there's no more notes so fast, Carol, next is no. And if you do arrow next off, no, you're going to get a a narrow and it's just going to crash. So you're gonna have to check if fast Adul next is not know, just axle. So if we did get at a new point or somewhere in the path or either the slower the faster pointer, probably the fast pointed because that it reached double the speed, then we can simply return zero. And that is all there is to these algorithms now. If I, for example, say if has loops off route equals one, nothing and if that is true, what I want to do is print f linked least as a loop on the backs of Shania, and they returned one because I don't want to get to eat oration because there's no point we're just never going to get out of it so that if I ran this, you'll notice we get linked. List has a loop. So our algorithm did work. 12. Recursive functions (counting elements): so Suppose we have this link list? 11367 And if run this. Yep. Prints off screen 90. I want it. Also bring the number of elements on the screen. Right. Let's say right after the link list has been printed, how can I do that? Well, we can create a function just for that, and it's going to be very simple. If you know how to eat it over a linked list, you will know how to do any operation. That is poor note in this case, adding one to a variable. So as a demonstration, if I make this count, no point. But I don't need a double pointer again because I am not modifying the route itself. I'm just getting some information off of it and I'm gonna use a for loop. You're so four. No point our current equals route. Start that route. Do that until current is no and current equals current. I don't next to step. We have seen this before. So what do we do inside a foretell? Well, we, for every single element inside the linked list or we do, is simply increments a variable. So you first have to have the variables. Ain't that's equality. Let's call it C equals zero and we're going to C plus plus inside the ah, inside the for loop. That's actually kind of nice. And then we don't see at the end of the never tried to print this on the screams of say, bring deaf linked least has percent the elements Hey, lemons right on back. If I type in here and call the function count off route, remember, just route because it's already a known another point that we don't need the reference to that route because we're not changing it. And if I tried to run this, I get a linked list has five elements. That's very simple. Now what they want to do is introduce you to recourse iveness inside, uh, basically linked least related functions. So how do we make this function recursive Well, at one point, we forced have to call it Call itself. That's That's the main principle about recursive nous. Let's create another function called again in count, and this guy is going to take in a note, right? So node no. And what we want to do is well, if the note is No. First the noticed know that we know it zeroes off. The linked list is empty. That's nice. So we can say here if no equals no. Then return zero. There's nothing to come. But if no does not know, that means that there are elements. But we want to call this function forward. So what we can do? So, for example, this link list. We have five elements here, but we also have one element from here, plus the a number of elements inside this link list, which has four elements. So if the route was to be here so we can sort off make this into a recursive call so we can return one Blas Count Adul next. So if you passing count at all next, it's as if we just cut one element from the link list, but only for the functions that we didn't really changed the the route itself. So if you say here are one plus count off no adult next, then if, for example, the linguist is just one element along what's gonna happen? Well, we first get into this guy. We get the root root is not know. So we get one one. Plus, this is what? Well, this guy we know that is going to pass. No to come. So then, the second time we enter, this guy's going to be knows there's going to return zero to get one plus zero. Of course we returned it. So we just returned one for for leading police. That has one element for two elements. Again, we're just going toe Enter this bath. First there's gonna be one plus the next known the second node. Now, the second note is not know because the linguist has two elements. So it's gonna go one plus something else, which is no, because it's the told element in the totem and doesn't exist. So the second called is going to return one plus zero and the first cold is going to return one plus one. I hope this makes sense. So every night recursive function, you always need to have a, uh, an exit condition. Basically, if you don't have this this case just gonna go forever an evident. But you have to have some place where this ends. Assuming the link list is created correctly. Remember, with the loops with the linguist that have loops in them. This is not gonna end ever. But that's not really a problem. So also is called this different name because these guys now have the same names count could save. And he had as well. And let's try to call it and see if it works. Opportunities to count recursive and run this your notice, like still get link list has five elements. That's because off the technique that you that we used here So what that did is basically used this algorithm where said Okay, well, the account of the whole list is the count off one plus the count off the least the starts at the next element where the root is the second element, actually. So you do that again? One plus this guy the rest of the list. And then again, it's the count off. This guy is one plus. Well, these two elements, and then the count of this guide is to element is one plus just seven short of the note seven, which is just one note, which is just one, because ah, here we have no. So says we have no, Remember, we're returning our function. Zero. I hope this was useful and a nice introduction to recursive functions related to link lists . Now I'm not against learning recursive functions and how they were. But in production you shouldn't usually work with recourse iveness because, as you can see, it's kind of difficult to understand the way it's doing things. And most of the languages are not really optimized for such function calls. If you're using something like lisp, for example, which is all about cussedness, then sure, by all means use re coarseness. But this is not optimized for car sickness. And if you're going and see, you're better off just using the iterative functions like these, all right? 13. Introduction to doubly linked lists: Today, we're going to look at a different type off linked lists. So far, we've looked at these types of linguists. They're called singly linked links. Why? Because they only have each note. Only has, at most one point, are pointing to another note. Right, So you have the route point are pointing to the second, the 2nd 1 pointing to 1/3 and so on and so forth, and they will take a look at a doubly linked, linked lists. What's what's the difference between those two? Well, the difference is in there notes. So this guy only has basically on information field where it can stop really anything, and it has a point or two. The next note, a doubling linked lists has to point. It's so the no look, something like this. Let me joy here. So it has the information for simple here, free. But aside from having a forward arrow but having a reference to the next node, it also has a reference to the previous note. Just think so. And the note before it also has a reference to the previous node. If I have here the node Juan, this guy can point to three. And here, since one is actually still the root off, are doubling Klink list. Its previous is going to be no. All right. And of course, the next notes are gonna be looking exactly the same story. For if I draw here seven is gonna be like that. We've a previous pointer that points to the previous element and the next point of the points toe eight here, which is our last element. And of course, the last element has a reference back to our previous one. And also the last element doesn't have a next pointer similar to a singling league list. So this is similar to having basically two linked lists put on top of each other. They are the same, but one of them is the reverse of the other. So here you start from one and go toe free and seven and eight, and then you can start from eight as well and move previously to seven free and one. But so this is in doubling linguists. But I think it's very simple. And, uh, we're gonna take a look at the advantages off and a few details about the implementation off each operation. We're going to take a look at each operation in much detail because they are more or less the same. I So let's get implementing it. First, we should create a note, but they struck node. So I'm gonna say here, type death struck node, and similarly to what we had before. I'm gonna start on end, but you can start anything you want storing end, and I'm gonna have. As I said, I need a no point are next, like before. But I also need a previous notes. I'm gonna just copy this and say previous And of course, I want to type that this note the name gold my size before we have to use destruct keyword in here for the same reason that we did before also has tried to actually create a linked list. Uh, where, as we've single into English, where he had one route, right? But we've doubling linked lists. You can have two routes. Really? Because as I said, you can start from one goto aid, but you can also start from eight and go to one in the other in the opposite direction. So what we should do is differentiate between those two in the naming. So I'm gonna call this guy the tail and this guy, the head off our linguist. All right, I'm gonna start here by defending that stale. So no point of sale is going to be dynamically allocated. 7 a.m. A lock size off note again does the same thing. And also, let's check if, um, I look failed to allocate. That should be a good idea. So you'll if there is no more than just basically every time, one or exit with one. It doesn't really matter. I don't want toe execute any further. If the they all felt it failed toe lock it so that we have that they'll let store some values is and say they'll arrow X equals. What did you have in the example? We had one, right. I'm gonna start warning it just like we did with normal English. And then we have to decide. Okay, So since this is a tale its previous pointer, this guy should be no. So I'm going toe actually say that Tail adul previous equals No. Okay. And then we need to sort off create a next point. So what I'm gonna do is, um allocate the next point up to it. And ST Tail Arrow next equals a Matlock size off. So now we should have the second point of allocated for the second node allocated. And like before I'm going toe, actually check if this guy allocated some memory. So if you did nice, we can store some values that store the next one, which is I think it was free. Yes. So now since we actually have, uh, Tail Adul, next be a new node. If we say tail Adul next, Havel X equals free, then we also have evaluated. And also we have to set the previous pointer toe our second. Now that this is something that we didn't have to do if singling link lists. So I'm gonna say Tail Arrow Next. This is a pointer to our second node. So we want to set the previous store second note to be the first known. So the previous to our second node, this is what this region equals. Our first note, which is the tail. I hope this makes sense. And then, of course, let's set the next pointer to be a new node and I'm gonna actually stop at Ah, seven here because otherwise just gonna get re complicated. Consider this link list that we're gonna actually create inside our problem. OK, so tail Arrow next. That's the pointer to our second node and want its next pointer to be a new note. I want to create your Matlock side note again and again. Off course check if it's no and returned a different value this time, all right? And what we want to do is, well, we have the third node which is still out of next out of next and just said its value to seven. Because stale as you remember, tail his disguise. Tell adult next is a pointer to this guy and tell arrow next and the next is appointed to this guy. So now that we have the toad elements there, Adul next battle next that said, it's, um, its value so that I don't next at our next title X, he is going to be seven, and it's we have also set its previous remember, So this can be quite complicated, but don't don't worry. We're gonna go to actually an implement an insert function in a later video, and that's gonna be much, much, much more readable. But right now, just as an example, this is what you would do to actually create a linked list without having any sort off additional functions. So this is what this is the previous point or off our third element. So it's basically these value is the previous pointer or for third node. Right? And we have to set it. Toby. What toe? The to be the second note, while the second don't happens to be tail at all. Next. Right, Tisdale is just our first note, and we only need a reference to it. And see, that's a seven year or last note off the linked list. We're gonna meet here. Eight. All we have to do is to set its next pointer I saw toward elements next point or to be No. So that says that. Okay, here the linked list sort off ends. But really it's the other route off our link. This Where's me? Here. We have tail. We can actually store this. Uh, this pointed to be our heads, so you can see here. Note. Pointer had equal stale Adul Next battle. Next, Right. This is our third element. So That's all I wanted to talk about in this video. Very short. And I hope you got something. I hope you understood what the double linked linguist is. Uh, what I want you to do is to think about the advantages this sort of gives you in the next video. We're going to talk about these advantages and, uh, how it plays, how these player role in operations themselves. When you delete another, when you add a note or we want to, for example, reverse it. What? How can you reverse a doubling increased? 14. Iterating a doubly linked list: So we left off at having a double interest with free notes, right? We had the value one, the very three and the value seven right? And this doubly linked laced. Basically, it has two pointers. It has a pointer to the previous note and appointment to the next node. Now the question comes, how do we traits such a list? So right, if you go meet the previous point are I don't have are the members from a singling list like we had before, so we can eat a rate as if this was a singling list. How would you do that? Well, your four start by declaring a, uh, according to point door, you initialize it to the root in our case is going to be our tail right to say equal stale . Remember, the tail is the first known off are released. The head is the last note off this and then we have a while local it saying and exist condition is what is the condition is if current is no. So while current is not know, we should print his values print F percent, the broadened adult X right, and, of course, the step Because we have to move forward is just current equals current Adul next refuse. So if I try to round is now you noticed I get 137 and those are the notes or the values off each note that we have added in the linked list. Now what does the doubling least have in special? Because Yeah, sure, this is fine, but I could do that. We've seen that increased. We don't having both next and previous pointers, right? Mm. Well, you might have noticed that we have here the head. So what if What if we start from the head years instead of think things that you say head, which is our last note and we trade until off course, current is not know And if it's not know, we can get its value. But what's going, Toby? The step. So if we are at the last note Well, remember we don't have a pointer toe the next value right from there. We also have a point of to the previous one. So what we can do is step backwards using the previous point. We can say current equals current arrow previous So the first station is going to be our head and then the next situation is going to be our head Arrow previous What? Had no previous Well, we can take a look here. Head is this guy right? So it's basically here and had arrow Previ ous is Dale Adul next, which is our second element. Right? And tell arrow next. Hello Previous. So our second elements Previ ous has our tails, so we get back to the tail and once we get back to the tail, if you recall, uh, tell Arrow previous is no. So the exit condition is going to be met and we're gonna exit properly. So if you try to run this, you notice I'm gonna get 731 in this case. So we have iterated it the other way around. And, of course, like before, we can have this as a four loop incident for wild loops. We can say here four and copy the initialization right days it commission stay the same. And then the step is going to be this guy which looks a little bit longer than unusual for Luke. But it's fine. It does the job, and if you understand the code, that's fine. or rather, if you and the whole team understands this coat is fine, I think because it only requires one line of code instead of free, as we had before, there's a four loop it raise the doubly linked list from its head. So from the end off the list, really to the beginning. So it was Brandis. You notice I get the same results 73 and one. So it is sort of the power off doubling list. They can be actually accessed from the end or from the beginning. Either way, And they can, you can, either it from whichever direction you want. And even if you're like in the middle off the link list, you could actually still it right over all of its notes. Not like I'm like a, uh, singling list where you can only reiterate over, well, one direction. So if you're at the middle office tingly, linked least I don't have access to the previous members. Right, Because you don't have a previous point. I don't have next my second only in that direction. So in the next videos, we're gonna take a look at de allocation. Because remember, we're using Emma. Look, here, but we don't have any three calls. So we have what it's called memory leaks, right? Where else? Take a look at adding elements to the beginning to the end in the middle as before for doubling list and also removing such elements. 15. Deallocating (or deleting) a doubly linked list: in today's video, we're gonna take a look at how to de allocate the doubling. At least remember, here we have Emma locks, um, al calls everywhere, and we have no free call. So we have memory leaks everywhere for every single note here. And what we'd like to do is have a function that deok is the whole list for us, right? Called free on every single note. If we give it, for example, the head and the tail. So I start here with a functional avoid the allocate. So the allocate I didn't know Double pointer first or tail right at the beginning off are doubling least. And then I know the double pointer to our head as well, right? Why? No doubt Double pointer. Well, remember, we have these pointers inside our main function or our the function it is gonna be using these doubling, please. Since they are pointers, they have addresses, right? They have values inside of them. But if we d allocate the whole list, I wouldn't like to have this be still on Anders to that place in memory because that placing memory have been delegated. It's we don't have access to it. anymore. So I'd like to set it to know once we're done and to set a pointers value to know while we're a pointed toe that rights, that means we need double pointer toe note here and here. So basically the same, the same things, that argument as we've had before for every single link list function that changes either the tail or head. So in memory, this how our doubling least would look like right. We have one. That's its next point is free, and we have free where its next point of the seven. But its previous pointer is one and then seven, where its previous pointer is free. And next point of is no. And, of course, once previous pointer is also no. How would you go about the allocating dis list? Right? Because just the allocate the head or tail, because if you delegate the head or tail something like this, it would only delicate this node itself, and just that it wouldn't automatically see that Oh, there's a pointer and then seeing the allocate these ones. So this nice. If we if we delicate the tail off our list, we are left with the rest off the notes, not being the allocated, so we have to delegate them as well. How should we go about doing this? We, for doubling least this stuff is much easier and can be done without any ordinary pointers during iteration. What we can do is first things first start at the second note. All right, so if we start here, we can say we want to de allocate from here. Where are reiteration is we want to reallocate the previous node, right? This is basically what we were doing of single English, but back then we didn't have appointed there. But now guess what. We have this guy, but we have this little point on that actually have so don't right now. So in here we d allocate this guy. And then what can we do? We can move forward, moving forward at seven. We can delegate again the previous guy so delegating free and well, since we cannot move any four door, we get out of the loop and outside the loop, we simply de allocate seven, which is our current note that we have iterated with right, So we still have that inside memory. And as you can see this doesn't require any more auxiliary pointers. We don't have to have both the current and the previous pointer, right? We just have to have the current. And that current already has a pointer to the previous note, right? So we can make use of it. And this way we're going to allocate the whole list without having any auxiliary pointers. So let's get implementing it. First, we're gonna need a current pointers free trade over the Holy See node. Current equals. I'm going to initialize it as being the tail. I saw the reference tail once, Um, but they're going to see why I would be doing that in just a moment. Because I did say in here that we're going to start from the second point from the second note. Just a second. Next up. We need a while. Apps are going to stay a while. And what's our exit condition this time? Well, or exit condition is, as I said, I want to get out off the wild loop with our current pointer being the last note. How or what is the condition for that? Well, that's basically went current. Adul Next is no. It can't. I don't. Next is no. We know that's the last point or okay, so we can do current. Adul next is not know why. That's not know. We can do whatever we want. You all right? So that's the There's exit 20 son. And I'm gonna actually start by iterating forward because if I said I want to start freeing from the second notes I'm gonna say he are current equals current arrow. Next. Since we know current adult next is not know we can move forward, we don't checking anymore. If our note is nothing at this step, we are like after this line of code, we are at the second. No, we started the second note. So at the second note, what we want to do is the allocate the first note. It's our third node. We want to reallocate the second note and so on and so forth. So simple enough or we have to do is three corn and adult previous right. This is what we've thrown in here. This is current or a previous. This is our pointer and we are on the second ah note when they don't know. So once we've done that we can see the check if we still have, knows, to move forward, to move forward to them and free those pointers. And someone is. So far, we don't need any more auxiliary pointers, which is amazing. And we don't have to actually do any more checks aside from the wild loops check and now and the end here. As I said, we have to free the current pointer because if we're out off this wild hope, that means that this expression is force. So that means that current arrow next is no. Let me that we are on the last note. So we want to free that. Members say three off current. And lastly, what we want to do is set both tail and had to be No. So I say here their friends still wants and set it to be no. And also the reference had once and city Toby, No, but we have this point of somewhere in memory and we want to set them 20 toe. You know that we don't have anything in that doubly linked list, But what if our Double Inc list is already empty? Well, that means that our code is not gonna work due to the fact that we're already trying to de reference it right here. So I'm gonna have to provide a check here. So if tail is no, then you can probably just picked up. We don't really have to check if had is No, because if tale is no 100% hand is also no. So this is everything that we have to have in order to actually allocate the ah memory. Now we can call the function right here. You can see the allocate off our well, not just a tale here because that's just a pointer to know what we want the address off that pointer so that we can set it to know once with delicate, right. So we want the under Softail. And of course, the others had exactly the same thing. And that's all there is to be allocating our doubling list. So if we adhere the memory leak detection program, if we try to run it with the delicate function commented, you notice that inside the output I'm getting here Ah, detective memory leaks and it prints out free blocks off 24 bites. And those 24 bites are basically our notes, right? We have eight by tear. We have eight fights here and we have four bites here and then four more bites for petting zoo have 24 in total and then we have free notes, of course, because we have one free and seven as the notes. But if we un commented is and run it, you noticed no more issues here and everything works nicely. 16. Inserting at the beginning of a doubly linked list: Now let's take a look at how toe clean up the code so that we don't have so many arrow next . Not in our initialization where we create the list. So let's take a look at functions to insert inside a doubling list. We'll start with inserting at the beginning off the W linked list. How did that work with a single in place? Remember, we had the route right. We had a root, and what we had to do is create a pointer before the route. I was linked to it and then make that node Donald itself. That was how we would add at the beginning off a single English similarly here. So we have to do avoid insert beginning. It's, um, we want the beginning off our link list and a value that we want to add first in choses create our node marching to say, here node new node equals M. A lock off sighs off node check if we had enough memory to allocated just in case. If new note is no, I want you to just exit and return nothing else to do there and then that's it. It's bad. So new node adult acts is going to be our value. Of course, you know, Otto Previ ous is going to be where sees this guy's going to become our new tail. We just set it to know, okay, and then, you know, arrow next he's going to be equal to what? To our previous tales in and say different, stale once and get me the point or right. But that's not all. Because remember that there here its previous pointer is no, But we don't want that. We want it to be the new note. So we're gonna have to say they all handle Previ ous equals new node. It also points to the new tail, right? And then we can set the tail here so we can say arrow tail equals new note here. So I hope this doesn't look too much different from inserting at the beginning off a single link list. All we have to do is to first initialize our new note right? Has has its value. Its previous pointer is null that we didn't have in the sing living list, but that's fine. And then we've seen the linked list we didn't have Toe said this thing right we don't have to modify the rest off our linguist. In this case, we can have because we have to set that previous pointer toe point back to our new tale. Of course, because this this guy was actually know before, okay? And then, of course, setting the tail to our new they'll, you know, that has been created to point to the rest off the list and others a crucial difference here. You might have noticed that beforehand if the list was empty. Basically, the the referencing off route or tail once would lead us to know we wouldn't have any issues. But in our case, you notice that we actually use this guy. So if this guy's no and we say arrow previous off No, well, the problem the problem is just gonna crash. So we have to check if we actually have a list here. And I'll say here, if arrow tale is not know, then you should actually modified it. Sort of makes sense, because if it's if there's no, we don't have anything to modify, right? There's an empty least We just kind of plopped down the, uh uh, no. Then that's it, but and both previous and next is going to be No. So now let's create our least from that lets let's stop with just having a node s. So we have a node and since we're gonna add at the beginning, right, we have rather the beginning here if we keep on adding at the beginning, while the first element that we are going to initiate it is going to be our last. So I just set it to seven from the beginning, right? So setting this to seven means that I'm gonna first ad ah three and then I'm gonna add one . All right, so next we can see here, Tail Arrow next equals no. So that it doesn't have any sort off other pointers because it's just the only note inside are linked list. And instead of saying m Alok and tail at all next, everything. When did this whole thing and just call insert beginning? Who said at the beginning, off our course, Dale, or for doubling least the value free right and saving. After all this, we don't have toe do anything else. Just gonna have to say insert at the beginning for link list and we want to insert one. So that one is the first element now. So if we try to run this you notice I get seven free and one because this guy was iterating it from the end off our list we had here currently. Course head. And then we went Previ ous as a step. So now we have destructor. Let's try toe, remove this. Ah, this manual intimidation off this blast note and inserted using our function right as to that. So if we say here, insert at the beginning or power tail the number seven right around seven. Sure. So we don't need all days. We don't need this either. We don't need to em a lot. Anything. We just need to declare them as being equal toe. No, Right. So tales going to be new and head is going to be our tail. So if you try to run this, let's see what happens. As you can see, nothing Got printing dollars scream. That's kind of old, right? What? White? Why would that be? Remember why we set double pointers right? We did. We did that because we wanted to modify our tails. So when we insert here the first time, for example, we get this to be the new note, right? So that's going to get mortified. But here we're iterating with the head or starting with the head Ardo. Our head is never modified. What we're doing here is tell equal snow and then had equal stale Well, which is No. So we're just basically setting this guy to know, and we're never touching it again. Therefore, this case never said this. There's no forever. So instead of having our insert functions, have empty lists passed to them, we should have unease. You need function for the length list with one single note. Okay, so let's let's do that so that we can actually initialize them properly. So if I have here the simple function, just a void in need and this they will take both the tail. So no double pointer, tall tale and no double point of your head because we are going toe, modify them both. If we just have what? Here? We're gonna pass in basically on empty, doubly linked lists. So what's that gonna be? Well, it's going to be our tail, which is no and are headed, which is no, but we're gonna have pointers to those. So this guy is not No, But this guy, that should point or note is no before and were unchangeable from from instead of pointing to know, toe point toe the same note because it's gonna be one simple note, and we're also gonna initialize them with a bad value to initialize them with. So that's the first notes value. And then what? Well, we just have to, uh, create that notes I'm gonna say, Here, node, you node equals m Alok off size off. No. And then if new node, he's no, I want again directed with one to this time, let's say and return. That's if we don't have memory or something like that. If something goes wrong while advocating that place memory right, that's usually not gonna happen. So we don't really have to think about this too much. Um, then we have to set their values are new notes. That'll X we have the value here, So that's simple. Previ ous Well, this is the one note inside our list. New node at all Previous will be no. And then, of course, this is our It's our only note inside the least also, you know, that'll next is going to be no amazing. That's that's fine. And now all we have to do is just set tail and had toe point to this note. So I can say you different still once remember, that's actually new right now and set it to be our new no and same thing with our head. And that's older through it. And they should be in addition, actually initialized our list So we can say here, OK, do this. But then you need tail and head and give it Ah Vander seven for the first to note and then you can simply insulted the beginning off our link list. So now if I try to finally run this, you'll notice I get seven free and one. That's because off what the first node was instance hated here, which was seven. Right? So it is seven is here at the end of the list and we kept on adding free and then one but seven stayed a same address and it stayed to be the head while the tail kept on changing. So both both Taylor had started at seven. But then what happened is Ah, the tail kept changing, so it changed to three months rate free, and then it changed to one once rated one. So Tell was here and had was at stay. Stayed here. Really? So when we said current equals had that was the the node seven. And then when he said current adult previous that was free and one and so forth pencil and selling this before. 17. Inserting at the end of a doubly linked list: into the future will take a look at how toe add at the end off a doubling list. So you ever for simulating place, we had to do what we had toe start at the root off the list and iterated through all the nodes. Get the last note and append to it, right link link to it. They know that we want to add right, but basically it's a fairly costly operation because you have to take all the notes and those can be hundreds or thousands or note, and that would take away. But with doubling policed, what you can do is if you have both the tail and the head, well, you can just take the head and simply append a note after it. But so if the head is here when upend and after it, and make that note the head now and as you can see, this operation doesn't, um, get affected by the number off notes you have in the doubling list. And this is a pretty big advantage when it comes to doubly linked lists. But you can add in both and both the head, as we've seen in previous video and the tail in just ah 01 Complexity. So right, this is from what we had previously. We have the 13 and seven and the tail is one. And our head disseminate if you want to add at the end off the linked list, let's say let's say we want to add the number. I don't know five, right? Don't either. Number five at the end off our linked lists and just make the known itself, right? This is represents our node and what we have to do when we have the head. So we can say had Adul next equals five would make sense for us because it is going to be our new head. So we have to have ah next note after this guy. So I just link it just like so. And of course, we also have to say that uh, five arrow Previ ous is the previous head. Right? So we have to get on Adam from here, going all the way back to our note here. So these two, these two links have to be made. And after all that happened, Well, what we have to do is just change the head. So we can say Remove this guy and make this guy be our new head. So we have to change the head, of course, if want to add at the end for Liberal Inc list and that's it, that's all you have to do. You don't have to. You don't have to care about, uh, old elements before the previous head. So it against you, we didn't actually talk about 13 and seven or any of those events they don't matter to. A double increased to a single English where we had to start from here and it rate over each of them and then got get the last note and then actually do the operations. Sure, with a single interest, you could actually retain the last note if you really wanted to. But it's not as useful as in doubling this, because remember, if you just have one note in a single English, which is the last well, note, adult acts is a value. It's number, but no arrow. Next is no. So you're kind of stop. You just have that note and that's all right. Let's create your a function. It does all these say here, insert at the end, right? We want if want to insert at the end. We want first our head and I'm taking double pointer toe head because remember, we might change it again, and that's important. And then we want our value that you want to have. So, as usual, s first created a node that has the new value. So I can see here. No, you note equals m a lock off size off note again. Again. A simple check to see that. Okay, this guy's not if it's no, I just wanted to exit with I know it's a free and everything simple enough. And if once we created this, we have to set a few things right, we have to set new node arrow acts is going to be our new value. That simple. Since you want to add at the beginning, this guy's going to be our new head and every single head it's next point door is no. So we're gonna say, you know, no adult next equals No. So we don't care about that. And of course, new node arrow Previ ous is goingto be. As I said, the previous head was the previous head. Well, we have had here but we have to deal offensive ones. And of course, at the end here we want to also Well, remember we said that we have to set five adult previous to be our previous had, but also have to set seven Adul next to be our new head. But we have to make to Ling's here. So this was only one of them. And the next one is well, the reference had once right arrow Next does this guy is actually no, because it's a head off our double English so far. And we said it too Well, two point or you know, of course. And lastly, we just have to change the head off the linked list because truly, once we've added a note after the head, the head is no longer or hell. It's just a simple note off our doubling list. Right, So this new note is going become our hands we just have to say had equals new note, right? That's olders here. We don't have to touch on the tail or any other notes in between the tail and the head. This is the nice thing about a doubling Klis. So no less tested. First, let's change the iterations so that it actually dates from the beginning this time. So I say here instead of had to start from the tail and instead of moving with previous to move to the next. Right now, if I run this without calling that function you noticed, I get 137 So that's the expected result. But if I actually call here in, start at the end at the end and give it the head and ah, five year, if I tried to run this, you'll notice I get five. And here and head is going to be actually our newly added node. And that's it's simple enough rented. It looks very much similar toe starting at the beginning because, well, it is a skin See, we create forced on you knowed that we make We said the value property and as the same thing except the previous Now here is no. Whereas with inserting in the end, the next is no right. It makes sense because we're at ah, tow opposite opposite ends off our double Inc list. But then we have to set here the tail and here we set the head that it's about all rested. And now we don't even need this, by the way, but actually moved his check Due to the fact that we have created that initial unit functions that sort off has to be called before any off the insert methods are cold. 18. Inserting after a node of a doubly linked list: So now we know how to, while basically insult at the end of for double Inc least sort of the beginning. And let's take a look at how you can insert after or before a note into it. I was just gonna take a look at how you can you start after. So you started less creepy function again. Insert after that scene and after what? After a note. So I'm gonna passing here, Not a not a tale nor the head. I'm actually gonna pass in the note and a simple pointer to note we don't need a double pointer because, well, we don't really need to change the reference from it. But we just have a We just have a node and we sort of want toe add, like right next to it. Our new node. Right? So we're going to stay here? No. And we want the value that we want to add such incidents manual. So again, this example, we have one free and seven that are doubling placed. And let's say we want to insert this five Not not after the end off a list, but after the note. Three. The northern and old with the value free. How do we do that? What what exactly do should we do? Well, take a moment and think about it and see if you can figure it out by yourself. It's actually very similar to what we did with the adding at the end, at or at the beginning. So let's start we thinking about where should this guy point to, right? So first, the previous point or off five. Well, if want to insult after free, we know that the previous point or five is going to be three. So that's simple. We just kind off link this guy here and then the next pointer off five onesies since one thing start after free. It was the previous load that free had after it. Right. So sees now. Five is after free. Seven is no longer after 37 is after five. So it makes sense to actually link it to this. Let's say like this, Okay, but this is no finished because right now would we didn't change the link list, right? If we eat a right over it, go 13 and Eriko free ourselves. Pharaoh next is going to give us seven, which is on. So we need to change free arrow. Next. Right? So since five is going to be after free, we need free Arrow, next to be five. So that's simple enough. We just have to change this guy 2.25 I've said just next. Okay. And next. Well, if we eat right over it, right. Difficult. 13 Free arrow. Next is five, which is nice. 500 next to seven. So that's amazing. And then seven, our next is no, it's all ahead. But if you go the other way around seven. Well, seven arrow previous is still free, so that's not correct. We have to change that. Toby five. Right? We want seven out of previous to be five and then five. IRA prefers to be free. Not five, not seven arrow previous to be freaked. So this guy should point back to our node with the value five. So now if you go Previ ous right. If you go from head to tail, you start with seven. You go. 700 previous is well, five. That's nice. Now 50 previous is three and and free out of previous is one. So that works nicely both ways. So that's what we have to change. We have to change the the next off our I know that we want to add after right the previous , the previous off our what? Well, this guy is free arrow Next. So Free Arrow Next arrow Previ ous that what we have to change to point to our new note And then, of course, set our new notes previous and next to be proper. So to start off, we first have to. Well, instead, she ate the note. You've seen this quite a few times. I'm gonna just fast forward. Okay, so what do we have to set here? Well, first new node had a acts is going to be on the value. Of course. That's simple. Then we said that new note at a previous right. So this guy has to point toe the node we want toe to add after, which is the node that has been passed to us, right? Using the functional. So you can see here new node at a previous equals known seen, but enough, you know. But then you know the Adul next is going to be what? Well, if we take a look here. It's this guy, right? We have new note cattle. Next is this seven. But what seven? Well, since we haven't modified this part yet, seven is our node arrow. Next. But it's our previous No, After, uh, the note we want to add after, if that makes sense tonight. So you have created node. Now we have to change those two links. So first we have to do what? Well, we have to change this guy so that from seven to free 2.25 Stan, how do we do that? Well, seven is again No Darryl next. And then this pointer is Adul Previ ous off whatever we have. So it's no Adul next adult previous. So we want to change Note Adul next arrow Previous. Now this is okay. We want to change it to point or new note. Of course. And there's a new note here. Only problem is that new? No, that'll next could be known, right? We might have passed for somewhat of a reason. This note could be actually our hand. So if it's all ahead, this is no remember and no adult something. It's going just crash. So we should check if knowed Adul next is not know. But if it's not know we want to change that value. If it's know we simply don't care, it's just no. And remember, this doesn't affect this thing because, well, which is that it just means that our next No, it is going to be no right. We're not de referencing no here, which is important. And lastly, we have to change the next pointer off our No, did it we want to add after simple enough, This is This is the most logical one. We just have to say no what Adul next equals, you know, And that's really everything you can see. It's similar to singling list, right? We have just basically a few modifications to the neighboring notes before we've just a single English. We had to just change the previous that they know we want to add after That's all right. And the new note, Of course, you might want to try to actually reorder these operations so that because I did pick the easiest ordering off these assignments. But remember, if I worked, for example, move this up here like so well, then no datil next would be our new notes. So you would have to change this of it, maybe figure it out. If What if this assignment would be here? What? What do you have to change below it? So now let's get to checking this function. So you say Here, insert a send off concert and I want to be sort after. Well, not our head. I want to insert. After what? After free. What's free? Well, we know that one is stay also free. East A little. Next makes us. Yes, it doesn't access. Or you could say we don't have had its seven, so had no previous is free saving. So I want to insert after Tail Arrow. Next, the number five. If we try to run this, you notice I get one free five and seven. So five indeed was inserted after the note with the value free. I hope you understand these operations. And now you should be able to actually create these functions on your own without much issue, right? I think they are pretty simple once you get the gist of it, 19. Removing a node: do. They were going to go get how to remove on element inside a doubly linked list. So suppose we have this example. List 13 and 71 being the tail and seven being the head off for the mailing list. How do we go about removing the note in the middle? Take a moment and think about what changes need to occur inside the Link Lee so that we don't have to so that we don't have the element three inside it. So first, you might notice that some of the arrows here are going to disappear, right? So I'm gonna mark this arrow because this is gonna just disappear because it's part off the note with the value free and same as this guy, because it's no longer gonna be there once the note completely gets removed. Therefore, we only have these two arrows to work with. Correct. That means that we already have to do is change these two arrows so that are linked. List is basically doesn't have the note with the value offering it. And to do so, we can simply remove this arrow and change it so that instead of pointing toe free it points to seven for Jesus color, of course, just like that. So no one adult next is seven. That's nice. But then we have to change this hour as well. And similarly, all we have to do is just change this arrow from instead of pointing toe free to point toe one. So if I do that and make it point toe one, there we go now one adul. Next. It's 77 years our heads. So we have nowhere else to go and seven out of previous is one. And when he's out there, we have nowhere else to go. And the link only has these two elements no longer, Uh, we no longer see free as an element inside a list, right? I can see if you are either on either ends either the tail or head. You cannot get two free, even though free might have some links to the list. But now, since it's no longer a centralised, we can simply remove the whole notes so we can just free the memory basically for our note . And now we're just left with this to note inside the least now, practically how do we do that well, first expert, I want to change things a bit from how it they did with singling lists, because in signal exist. If you remember what we did was remove actual values were searching for values, and they're removing the notes. In this case, I'm gonna greatly function it instead takes in the noted that we want to remove and simply removed it all together. So we simply do void remove nodes. And we're passing the note here as a parameter a ah single pointer to note because we don't need a level point or in this case, and it's only need this is sort of an advantage with doubling place because we've seen real English, we couldn't have done this. Uh, if you remember, if you, for example, have this situation, you would have had to modify the previous notes so you couldn't just passing the noted the value free to the function you would have had to pass than over the with the value one as well. So that's why in the situation is much easier to remove a note with double English. You already have free arrow previous, and you already have free Arrow next to have references to both ends or both neighbors off that note. Now let's try to figure out what it is that we have to change. What we have to change. This guy. What's this guy? This is This is something Adul next. OK, but what is that? Something that something is the know that we want toe delete, but its previous. So it's free adult previews. Adam. Next. That is the value of the actual arrow that we want to morning so we can see here. No Adul previous right? It's still, for example, would be the note with the value Juan, that's nice. And then arrow. Next is the link to the well to this know that we want to remove and we want to give it a different value. So now it's value is the note with the value free, but that's not correct. We want to change it, so I want to change it to what to do on a node event of seven. How can we get that from the noted with the Vela free Simple while note While note is the note with the value free note, Adul Next would be the note with the best of seven, so we could say simply that equals no arrow next. So it's sort of skipping now over the know that we want to feel it. Similarly, we've the previously So we have to take a look. At what? What is this arrow he respect to our nose with the very free that we want to remove? Well, it's something arrow previous that something happens to be free Arrow next. So it's Free Arrow Next, Arup reviewers or no, that'll next and previous for, uh, every case it would be Node Adul Next arrow Previ ous. And we have to set that toe. What? Toby, The previous note, right? The previous previous to the current Know that we want to remove. So no arrow previous. Just like so. So now all the links are correct that there's a problem with these lines of code. What if instead, off removing the free, we want to remove one hour tail. Well, our till has the property that Okay, Tail arrow Next has some valuable Tell our previous This guy is always no and it's that's a problem because if this were to be tail tail and of previous would be no and we're tryingto the reference it getting They were next from it. So we have to check. You have to check if it's not know. And here a check. If no arrow previous is not know right? So if you're not the tail, then actually do this assignment. Otherwise it doesn't matter. We don't really need to change anything. It is the tail. We don't have a previous know that we have to link it to the next one, right? We don't have to skip over anything similarly, with no datil next. So no, Darryl next would be know if What if we wants to delete the head off our Double Inc list? Okay, now we're almost done. So we are in this situation right where our double English is keeping over are known, but we also have to remove the note itself. Well, we simply have to call the function free on our note on that. That, basically is the whole function takes in just the note and readings everything and simply freeze the memory so we can test it on. Let's say the note free. So if I say here, remove nodes off, let's say what's what's free three East, uh, second element. What's the second element? Well, the first element we know it's stale, so we can say Tail Adul next. That would be the second element. So I'm just gonna passing here Tail arrow next. And now if I print every single element here, you're gonna notice that we only have one and seven, so that worked nicely. But there's a problem when it comes to removing either the tail or the head off our double interest. If I try to remove our tail, which is element one, right. If you try to run this, you'll notice we get an error. Why might that be Where the The problem is very simple. We remove the no tail, we remove the no tail, we simply make the links proper. So in this case, it would be the seven would be our new or history would be our new tail. And you would just kind of like everything together. That's fine. Right on. And this guy at a previous would be no. So that's correct as well. But, uh, this stale guy is a variable is a variable inside of stack, and we don't provide a reference to that variable. So this guy inside our function does not change. And that's a problem. It doesn't change. That means that we still have a point or on narrow toe that placing memory that we have freed right here. And what happens if you have a pointer to that place Memory? Well, if your dear friends that you're gonna given at all most of the time now there are many ways to actually fix this issue. But they just wanted to just get on auxiliary point Or so, for example, I can see here no longer too. Daddy equals our work. New details hotel. I don't next. Right on that. We remove the tail. And since the police memory that tail is pointing to no longer is no longer accessible, we can just say the new tail equals who's your daddy, right? Because we still have this this point of view and we still have a little next knowing that well, Dale is not know, So you'll have to also check that, probably in our case, we don't have to check it because we know that it's not now. If I tried to run this, you'll notice I get free and seven. So that's something that you have to keep in mind when working with this stuff here and similarly with the head. If you have such a situation, all right, now as a home or you can take a look at the scene dealing place and try to make a similar function to this now, you're not gonna be able to do it. We've just simple pointers. Gonna have to have double pointers. But if you think about it a bit more, you're gonna figure it out. I think. Just remember you're gonna have to use double point. That's four days. So similar. Just remove note and taking a note double pointed as a parameter, not how we had it before with a root and the actual value that be on interesting, uh, exercise, I think. 20. Finding a node: knowing how to find an element inside a linked list is going to be a very important part whenever you're working with English. So we're going to start creating a simple function that what it does is taking a value and returns the node with the or the first to know that it finds with that that so if I were to pass in ah free, for example, it should give me the second note. So it seems there function is going to be called something like find note. It's gonna have to return a note for North Point, really, And it's going to take in our possibly our tails. I'm gonna get here a simple pointer, a single point to note because we don't need. We don't need a double pointer because we're not gonna modify the list. Were just tryingto either it over it and find a certain note that all and passing the reference to it. And then we want the value that I'm not also take into consideration the head. We just want to detail, that's all. So how do we do it? Well, it's very simple. We've learned how to enter it over a ah link list or a double English so we can use that. I'm just gonna copy and paste this four Roop. It's exactly the same as we've had previously, but in utilization its tail until it's not know until we have finished. Basically looking at every single note, right? And then the step is just current condoms are next because we have the tail. Have the beginning off are linked list, so we have to go forwards backwards. What do you do here? Very simple. If colon arrow What X equals r value value, then what we do. Interesting period going on. And that's it. Because if current adult next is the value we are searching for, then we just have to return current, which is a pointer toe, a note that has the value value passed to the function nice and as as a default if we don't find anything. So if this if is force for every single element inside that doubling least, let's also return something like no. So if we get no from this guy, we know that we haven't found anything and we can check for that now. Let's actually remove this part, and we have the link list One free and seven Simple enough Now let's Ah, let's try to find a note to say Here, node found equals won't find nodes off. We want pressing for that there. We don't need a double pointed to our tears were just confessing the tail and then the value within such a safe or, ah, seven. Right? And of course, the sprint half its That's his value. And that's also print f. It's next. So if we want to print a a pointer, we just say percent b on the backside so you can see here, uh, found Adul X and phoned Arrow Next, actually do something like value and next nicely formatted. So if I try to run this you're noticing gonna get value seven and the next point or is no So we know that this guy is the head, and if we change it for, for example, free. We did find value free, and the next point is not knowledge of value. It's a pointer to the next no decided double English. But simple enough. And if we, for example, do let's say four, remember, we don't have four inside our linguist. Well, everything is gonna break because we didn't check If our found note is no not remember, we can return all here so this guy can be no. Therefore, we shouldn't d reference it if it's no. So you can see here, if found is no to say paint F No node was found Mexican else, then just business as usual. So threat Randy's you notice? No, no, it was found. And if I changes to, for example, free. This works perfectly. Even if it's the first note off doubling placed can say one here, and it's gonna work now. This was very simple and straightforward. Let's take a look at the recursive version off this functional. I like it. Narrative functions they're easier to read. Easier to understand. But I know that many, many teachers out there are actually, uh, requiring students to know recursive functions, especially we've linked lists. So I'm going toe show just this example for recursive recursive algorithms or recursive functions. Really? And I'm gonna let you tinker with it later on. So what should this function return? Well, it's going to return definitely a, uh, note point or as before, I don't put it. Find node And again. What do we have to pass in? It's still going to be the tale, of course, because we have to start from somewhere, right? But I'm gonna call it, I mean, a genetic a manner called node because this guy is going to be called for certain for other notes other than the tale, right? And, of course, the fact that we're searching for All right, how do we do this? Well, if the knows that we're on is, um is the value we simply return simple enough nodes? Adult acts equals value. We just returned our note and that it would not Nice. Uh, if it's not, if it's something else than were here Well, if it's something else, what do we do? Well, we probably just want toe call it for the next element in line. How do we do that? We can simply say return, find no the recursive and instead, off saying node will say no Adul next and then same as before. The same values before, right? So the first situation gonna call it with our tails. So this guy's gonna be a tale is gonna say its tail arrow acts. Let's say three. Well, no, it's not. Our tail is one. So it's not gonna return here. Is family done this? What does this return? Well, this is no that'll. Next is the second note in our list, which has the value free. So it's gonna come in here at the second call, and this guy's going to be the node with the value free and the value is going to be free. So do you start gonna be equal and this guy's going to return? Right? So this is what is going to return out of the second quarter. The first call is gonna return. Well, the return off this guy. So we're just gonna get the second note. When were such a party? There's one caveat with this Onda we're going to see in just a moment here. So if I try to call this instead, find node recursive. So what is gonna happen with this? Well, this is the simplest example, right? We get the repressing tail here, and the values one on our tail has developed. One is gonna be tale And one male and one Dale Adul axes one. And value is once just gonna return the tailback. So for this example, we're just gonna find out that we get value one, and the next is not no off course, But what if we give it free? You forgive it free. We're gonna get well still value free. And the next pointer is a different one. Fair enough. Now, what if I give it a different value than one free or seven? If I stay here for what's gonna happen, think for a moment and Teoh recognize the issue that I have inside this gold, right? See if I try to run it, I'm gonna get the nettle saying that node is no Why? Why did it get to be? No, Because we called it with the tail. I remember this guy keeps on calling recursive Lee. We've the note, Adul next parameter. So first is the tail nice that's not noticed can be verifiable then is the second element. That's no, that'll next. It's a toward element. Know that our next No next that seven that met Still very node. But that last note Adul next is no. So we're passing in here? No, right as the fourth call to this function and no arrow, anything is just gonna break the program. So we have to check if this guy is no similarly as ah, we did here with the four up. This is where we were checking out. This guy was no here. We're not checking anything, so we have to do that. And where do we check it? Well, before actually de referencing it right here were defusing the value. We don't want to do that. We want to say if node he's no Then what do we do? Well, let's think for a second if notice No, that means that we've iterated over the whole list, doesn't it? Right? Because if notice no, that means that there was a previous node where it's no, that'll next was no. And what do we know about linked lists? Well, if we note if a note adul next is no, that means it's the head off the list. That also means that is the last note off the least if we're starting from the tail. So when we get to this condition, if this condition is true, that means that we have iterated over the whole list and we didn't find anything. So what? We can do is simply eternal in this situation. And if I try to run it, we're just gonna get no note was found. So that works nicely. Now we've seen singling. At least. What I did was implement account algorithm. Recursive Lee. What I'd like you to do is to implement account algorithm recursive lee on your own on doubling lists, right, and do the same for finding a node in a single link list. That would be a very nice exercise. I think it will help. You better understand this recursive nature of things. 21. Reversing a doubly linked list: next. Let's take a look at how to reverse a doubling list. Now, this is going to be very similar to reversing a single English and that what do we have to do? We have to starting from that from this example that we have one free and 71 being the tail seven being had. We need to get toe disliked list. Starting from seven, we have seven free and 17 being the tail in this case and had being one. Right. So this is basically reversing the whole linked list. What does that even mean inside our structure? Well, let's take a look at individual notes and start comparing them between the States. This is the known reverse. This is the reversed. You notice that this guy, this guy, is what Skype is? One arrow next is pointing to free, whereas one medal next is no in our reversed list, right? We have nothing here. Then you might notice this guy, this guy's one arrow previous in our reversed one is pointing to free. But in our known reversed in our initial state, this guy was no. So you might see this. You might see that, uh the previous and the next court swapped right now instead, off one arrow. Next, Teoh, pointing to 31 arrow previous points to free. And if you take a look at every single note, you'll notice the same thing. But Free Arrow Next, it's seven, whereas don't hear free our own arrow. Previous is seven, right? So for every single arrow inside are linked list. Everything is swapped right. Previous is next and next his previous now, right and everything got swapped. Well, also, the Taylor had got swamped, right? And you got Tale being seven and had being one. Now I have here the function that we have used to diverse the Single Inc list. Now let's see how we do the same with the doubling is by modifying this. So first, If you remember, we had to actually have a previous pointer, not only just the current, because we had to instead off ah, pointing it forward. We had to move that arrow two point backwards and so that we have a reference to the backward place. We had to keep it inside memory, but now is doubling. Least we have at every single note we have the previous pointer. So we don't have to do that anymore. We can simply remove this previous right. Then we have a current. We just either it over with a while loop And I remember date elation is something like this . You're forced to retain the next point daughter. You modify the current and then you move forward. See you have here. Colin tickles next, and you know that next is Colin Adul next. So it's really current equals current Adul. Next, as we've seen previously, we just have done it in two steps because we are modifying current battle next. And then we also modify previous because we have to keep track of previous. We don't know what what this previous. We can't go back with the mailing list, so let's start by first removing previous. We don't need it. We're learning that anymore. So can simply removed here. It removed. Okay, and this guy's going to complain. It's not really a problem. The first let's change the name. It's just call it reverse and let's also have here not route. But let's have the tail, and I also want to keep or get the hand as well, because remember When you reverse the whole list, Taylor head gets swapped right inside. Here. We have one being the tail, but they're here. Seven is detailed and similarly here. Right. So if you want to reverse that, you're gonna have to, uh, swap also both head and tails. Say here. No, that and head. That's now What do we have to the well, first we have to reiterate over with for a while. Oh, because it's it's simply easier with a while loop. We can do it. We can do this. It aeration process in two steps. We're going to start from the tail, not from the root. That's understandable. There's still the beginning, basically off our linguist. Then we everything the next. And then we should do what? What we have to swap next and previous for every single note. Well, you already have next here, So you can just say current Adul next equals well current at a previous because we have that point of now, so we don't have to worry about it Nice. But we also have to change current or a previous. So we haven't say current adult previous equals toe current title next. Well, you can't stay current on next because this guy already got changed before. What to say this. Then guess what this guy's going to be current or Previ ous. And since here, these guys are the current or previous we have the same point or both for next and previous . So we're gonna have to say here this auxiliary point or next that we retained here to say next year. Now, these guys both courts swapped and all we have to do is move forward. So now that we swapped all the arrows, there's one last step. Well, after we have stopped, all that does well, our tail is still one and are headed still seven, right, but are tell cannot be one because one Adul next is no. And we're not going to get the whole list, which is gonna get the first element. That's not correct. And one arrow previous is not know that. So we have to also reverse tail and head. How do we do that? Well, that's very simple. We're gonna use an ordinary point or I'm just gonna say here is and that's gonna be let's say, our tail. And then we make the they'll be our heads. Then we make the head of the hour, our regular pointer, which retains our previous Dale. So we just basically have swapped tail and head here. And since we have double pointers to this, we actually have actually will swap these variables from inside the main function. All right, I have already called dysfunction here That reverses the list. The list is one free and seven, remember? And if I tried toe run it now, after reversing it, we're gonna get seven free and one, so that works very, very nicely. If we, for example, don't reverse it, we're just gonna get one free and seven. Not a nice part about this function again is that if you, for example, have the front, the list being empty. So both male and had is no. If you try to run it, you're not gonna get any sort of crashes because, well, current is going to be tale, which is no. And then since current is no is going toe escape the whole my loop. And then we're just going to well, swap both tail and head, but they already know, so it doesn't really make any difference. And that's really all there is to waited. I think it's very simple and straightforward with doubling list. We've seen that increased. We've seen that we have to take into consideration. A previous point are and I was a bit more tricky, but this guy, we just basically have next we make it previous and then previous makes becomes next and that's about it. We just want that and then we also swept the tail and head.