Data Structures And Algorithms In The C Programming Language | Daniel McCarthy | Skillshare

Data Structures And Algorithms In The C Programming Language

Daniel McCarthy, There is always more to learn

Data Structures And Algorithms In The C Programming Language

Daniel McCarthy, There is always more to learn

Play Speed
  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x
14 Lessons (2h 17m)
    • 1. Introduction

      1:24
    • 2. Understanding Linked Lists

      8:32
    • 3. Creating your very first Linked List

      23:24
    • 4. Double Linked Lists Explained

      3:55
    • 5. Creating Double Linked Lists In C

      2:49
    • 6. Where the list value becomes the list element

      9:47
    • 7. Implementing A Linked List With The Value being the List Element

      12:38
    • 8. Understanding Arrays And Array Lists

      6:30
    • 9. Programming Arrays And Array Lists

      34:19
    • 10. Understanding Stacks And Queues

      4:59
    • 11. Creating A Stack

      4:49
    • 12. Creating A Queue

      13:23
    • 13. Understanding Binary Trees

      2:17
    • 14. Programming Binary Trees

      7:55
  • --
  • 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.

89

Students

--

Projects

About This Class

Have you already got some experience in the C programming language but want to take it further? Then this course is for you.

This course will teach you all about creating internal data structures in C.

This course will teach you how to create the following:

Linked List Implementation

Double Linked List Implementation

Array List Implementation

Queue Implementation

Stack Implementation

Binary Tree Implementation

All of the implementations described above will be created on video from scratch! You will learn how all of these work internally and when they should be used. This course is a "must have" for someone who has learned the fundamentals of the C Programming Language

Meet Your Teacher

Teacher Profile Image

Daniel McCarthy

There is always more to learn

Teacher

Class Ratings

Expectations Met?
  • Exceeded!
    0%
  • Yes
    0%
  • Somewhat
    0%
  • Not really
    0%
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.

phone

Transcripts

1. Introduction: Hello and welcome to this course. This is the introduction video to data structures in the C programming language. In this course, you're gonna learn all about linked lists and how they work internally. I'm gonna take you through how to create your very own link lists from scratch completely from scratch. We're then gonna move to double linked lists. I'm gonna show you how you can add an extra variable in your structure in your in your linked list element so that you can also point to previous elements in your link list. Very useful indeed. So we're then gonna move on to a raise and a ray lists. I'm gonna show you how. How raise work. I imagine no, a little bit about that already. And then we will actually creating a ray list based on what we know about a raise. We then move to a stack implementation. I teach you how to create your very own stack in the C programming language, and I explain how stacks work, and I also give you a bit of history on them. We then move on to cues. If you're in a shopping market and you're a basket full of items you cue up. I show you how to create a que in the C programming language how to create a que in your actual program. We end the course with trees. I teach you how to create your very own binary tree structure. And I show you how they're a little bit similar Two linked lists. 2. Understanding Linked Lists: welcome to this course. We're going to start this course by learning all about linked lists. So what are linked lists? Linked list is simply a term to describe a bunch of elements chain together. So, for example, element a nose element. Be element. Be knows elements. See elements si no nos element D On they form a list. That's where a linked list is. So a linked list is non entity in itself. A link. This is a descriptive word to describe the chaining of linked list elements, so that is what a linked list it's. So the linked list elements structure has a value. This could be like a number a string. It could be like 50. It could be a name. It could be an age, anything. It could be an object I know in See You don't have objects, but in other languages it could be an object. So the element structure also has a pointer to the next element. So, as I was saying, A knows about B B knows about C. C. Knows about D right that is the pointer. So a nose will be because there's a pointer to the next element, which is be on. I'm just saying a b c d. Here to make it more simple for you, obviously, that they aren't labelled in practice. So some important notes about linked lists link listened on object in itself. It is just a term we use. As I've already explained. The linked list is just the chaining of linked list elements. It's just a descriptive word. So I mean, if you really wanted to, you could have a linked list structure of some kind that provides more relevant information . But it's really not needed, Which is why I describe it in this course as a descriptive would now next. Um, having only one link list element still means a linked list so you can have the head of a list on the head is the first element of the list, right? So even even having one element on it doesn't change. Do anything. It's still counseling list, so you can also think of a linked list as a chain around a castle, right? So each I am part is welded to the next, so unless you know different, right? So let's now imagine that we are creating a program that takes an infinite amount of input from the user on the program basically says, Enter a new number and then you enter a new number and it's stored and asks you the same question again and again forever until you press leave. So just imagine that for a moment. So let's now see how we can do this with a linked list. So we want to add the number 32 are linked lists that is currently empty. So let's create the list head so we can see the list. Head has a value of 30 on its next bearable here has a zero also known as no nothing, right, because it points to nowhere else. This is the only element on our list. So we want to add number 22 the list now. So what do we do while we correct another element with 20 on there on at this point in time , they are both. So they're both wingless heads because they they're not linked Teoh another list element in any way. So they both stand alone, right? So, yeah, as I say here, a link list head is just a way of describing the first element of a list. OK, so now let's join our second element with the value of 20 to our list, which will form a list of two elements So we can see. I've now represented the addresses here. I've made these numbers up, but in a real program, this would be the address in memory of thes to list heads. Okay, so our element with the value 30 has an address of 1005 hour element with the value 20 has a value of 1028 address value of 1028. So let's now join them together so we can see our first list head we created with the value 30. It's next bearable now points to the second element because it's not the next variable. Now has Theodore s of our second element, which is 1028. This forms our list of two elements. So if you're given the head, you can get the second element because the second elements address is soared in the list heads next variable. So also noticed that our second elements next variable is zero. This signifies the end of the list because there's nowhere else to go so Let's imagine this is a and this is be weaken. See a links to be. But he doesn't link to anywhere because zero zero is here. Which means it's the end of the list, right? One. The next variable zero is the end of the list. So let's now add 1/3 element into the mix. We can see the third elements. Addresses 1042 our second elements. Next variable is now 1042. So that points to the third element. So now are linked. List has three elements. So we have the list head that has an address of 1028 as the next bearable on the second elements addresses 1028. So the list head points to the second element and then our second elements. Next variable value is 1042 which points to our third element, which has Theodore s 1042. Our food elements. Next, rebel value is zero on because zero, it doesn't point anywhere else. So our linguist has three elements. So if you wanted to reiterate through the list, this is very easy. We started the list. Head is the next variable. No, no, it isn't. OK, jump to the next element is the next element. No, no, it isn't. OK, jump to the next element. Is the next variable? No. Yes, it is. We see a zero because remember, here is the value. And here is the next variable. So the column on the left here is, um the value on the right is the next rebel where it's pointing to when 10 is found. By the way, we can then stop. It's rain through the list because we know are linked. List has finished so we can allocate list elements on the heap and bear in mind when working with linked lists. The memory is non order, which is why we have addresses the on in order of each other. We have we have 5 2028 1042 If they were in order, we'd see something like 48 3012 depending on the size of our link list Element structure, right. They're not in order there. No, a raise. So don't think of them like that. Each element in our link list has an entirely different memory address on there? No, in order of each other whatsoever. So if we wanted to provide a index of some kind to these list elements, we wouldn't be able to access it the same way as we do in Array would actually have to look through until our counter reaches the index number on. Then we would know which elements return. So just as an example, let's Ah, let's pretend that we wanted to get the third element right on our I d started zero. So we can say this. Zero, this is one this is too right. So third element would be, too if we wanted to do that on we were used on but on this was an array and not a linked list. You would just do get index too right in the linked list where you actually have to Do you have tow start a counter? So this is zero. OK, zero is not too. Let's get the next element. OK, now the counters 11 is not too. Let's get the next element. Okay, two is too. So this is the element they were looking for. Let's return this element. So that is linked lists In a nutshell. I hope that makes sense. We're now gonna actually program them, and it will make a lot more sense than if you get stuck throughout this course whatsoever. Please send me a message because I always reply to my students. 3. Creating your very first Linked List: Okay, let's start making a linked list. The first thing I wanted to do is in your C program. Include STD i o dot h. OK. This contains, like, printing routines and so on so we can output to the terminal as you probably already aware . So let's now define a main function. This is obviously the entry point of our program here, and we just give it 10 0 in here. Okay? Cold Now I'm using windows. You can do this on you bun, too. It's entirely compatible into this on Lennix. Mac, whatever you want to use, you can still follow this along, so I created a structure we're gonna call it struck a list element. Okay. On this structure is gonna have some data, so that could be a void pointer on. Don't worry. If you don't understand this, all will be revealed. Andi, It also needs another variable called list verse of type list element that's called next. Okay, so let me quickly explain this than in our list elements structure. As you're aware and see, structures are basically storage containers where you can store multiple variables. Right. Okay, so in our data variable here this will contain the payload for our list elements. So it might be a string of some kind. Like a message. It could be anything, really. It could be an interest. Your anything, right? But we use a void pointer here because we're basically saying we don't know what the type is. So let's just put it as a void pointer on DA. Allow it. So So we can pointed to any time we like as basically what we're saying here. We used a void pointer here to represent that. We're not sure what type is okay now. Here we go. Struck list element Next. Now this points to the next element on the list. So what will happen when you're iterating through a link list? Essentially, you'll you'll start with the head of the less that top of the less the head, you will output the data. Assuming data's a string, right, this pretend data's a string will output the data. And then, if the next element is not know, then you'll go to the next element, and then you're output that data and then you go to the next element and then you'll put that data on this will go on and on and on until next is no. And then you finished iterating the list. So let me now do that with you here so you can understand how that works. Okay, So we're going to do then. I just want you in here when you go instruct list element head. Andi, we're just gonna go head dark. Data equals hello, world. That's all I want you to do. And another c I want you to go ahead. I thought next equals no. Now, that's all I wanted to do right now. Okay, now, why now? When you do down here on this, this alone makes sense. Just follow it. I wanted to make a pointer for the list element, and we're gonna call it, um, see you. Ah, for current, you know, on it's gonna be equal to the address of head cause heads to find the stack here. Right. So we used 1% here to get the address of the head. Right. Okay, good. Now, I just want you to go while, uh, see you are does not equal no print. Half percent s backslash backslash in there, and we're just going to go see you are Data a muller at it. We're gonna cast it to Constanta as well. Okay, so here we've created a link less with only one element the head on. Just to demonstrate this if you know Kampala gcc main dot C Dachau main We're just gonna type main and you see Hello world. I know it's how it's being printed forever. That's because I forgot one vital thing down here. You need to go see you are equal. See, you are next. That's that's what you need to do. And all this will be explained in the moment. Just re compile that. Run it again and you see outputs Hello Will Once. So let me explain what's going on. So here we create our list element on this is the head of the list. We set the data to hello world And remember these character sequences They get converted to a memory address at compile time. So even though we put hello world here hello world is stored statically in the in the excludable somewhere. What? What is compiled on then? This is replaced with the address of that character Ray. But that's how this works. So really our data is a number. It's It's the address. It isn't equal A hello world. Hello world. Stored somewhere inexcusable here contains a reference to it. Like on address to it. Okay, cool. So let's go over this, we create a list element called head. We set its data variable in the structure toe the address of hello world. Okay, we said its next variable to know. Meaning there's no more elements of the list. Now, here online 17 we start out putting those elements. So what we do is we create a pointer, A list settlement pointer that points to the head and we get we enter. The while that we say we say, is the current element no yet know isn't OK, so then we output the data as a cons char pointer. So this outputs hello, world. Because that that is, we appointed to head here on heads. Data is hello, world. So that outputs that. And in here online 21 we change our current pointer here. So the next element in the list now as the next element in the list is no. We leave this loop when we look back around, so, uh, because we leave this loop. Everything works. Works is expected if you didn't have next equals. Oh, no, that's coming that out. And you compile it again. You can see that actually crashes the program and it doesn't show us an error message on Windows. You will see it on Lennox, but it did crash nevertheless. Now that is because because this is initializing stack here and we're not setting this structure toe all zeros. Ah, our head next isn't an initial is in it. On an uninitiated ized state, right is in an un initialized state, which means it could be equal. Do anything right? Which is why it crashes. We don't have that. That's pretty important. But hopefully that makes sense how this this list is working, right? So the data here and we got a lot more to go. By the way, the data here is equal. Teoh, I don't know what a string and intra job. It points to one of those right points to a string and points to an injection points to anything, right? Andi, In this case, we pointed to some data. Hello, world. Right? We set the next to no meaning There's no more elements, and then we just output the elements here. It's really simple. Is that I said another element of the list. Then we're gonna go struck list element. Um, second. Okay, I just go. Second of data equals this is the second element, and then just go second. Done. Next equals No. Okay. And now, currently, these two lists, they're not part of each other. They're not linking to each other in any way because the heads next is no here. Right. So they wanted to do it when he's a copy. This and we're gonna pasted above head. Okay. And then keep this set to know, But we're gonna change heads 2.2 2nd Simple. Is that right? So now, so now if we now compile, um, run that again. You can see it says hello, world. This is the second element. So why is that? Because we create a second element here, and then we create our head and we set our heads next, uh, to point to our second element here. So because we sell heads next to point to our second element, the list continues in the slope here because the current resolves to second and no longer know. But then when it runs second element in our loop down here, the next thing becomes no right. The current then becomes No, because the next is no ending the loop. So that's how that's how linked lists work. I'm going to show you now how we can write some C code to make our list much cleaner. We're gonna have really nice functions. There's gonna be a lot, a lot of easy stuff going on to make everything easier for us. So let me know share to do that. Okay, so go to the top of your your see file, and we're going to include a few head is here, include Esti lived our page and include SD bulldog page, not shovel need bull yet, but we're just gonna included anyway, just in case. And here you have a linked list of the sea that we've done, but we're now gonna We're now going to make a clean a way of doing this. So what I want you to do, we're gonna get out of this, Okay? We are going to get rid of this, and we're just gonna have had here. Okay? Heading current Okay, good. So what I want to do here, then? I went to go way haven't defined these functions yet, but we're gonna We're gonna write it first, and then we'll make the function. So you will see Santic. Sara's just too innit? List element. And again, these are functions were going to be making two and percent head. So obviously this year will be responsible for initializing list elements. Okay, So let me just put a common here for you guys. Shukan makes comments yourself. So in it initialize the less head. Okay. And then down here them We're going to go, um, add a list element. We're gonna passing heads here. We're gonna pass and hello, world here. Okay, so, um, at the first elements to the list. So what does this to them? Well, this adds hello world. So the list hello will being our data. So now let's add a second element at the second elements to the list. This is just one way of doing this. There's so many ways to make linked lists and depending on what you're trying to do, trying to do will depend on the type of functions you'll make for talking with your list, right? So then we go. This is the second element, okay? At the third element and will only do for three elements, cause that pretty much shows what we're trying to achieve here. So we're gonna add less element head. This is the third element. So really is gonna be there simple. Right? So by using these functions, here will be added items to the list and an output the more here. Okay, so let's begin. Ok, so we're going to start by creating our innit list element function. So we're gonna go avoid innit list element, and we're going to go Struck's list element. And then we're gonna go e l e m. And all this is going to do is just set it all to know. And you could use the men set here because we don't have too many elements. I'll just manually do this. Okay, great. So we've just implemented that innit list element function. Now we need to implement the ad list element function. So what we do then we dio avoid at list element on. We're going to construct a list element on this will be called head because we expect the head to be passed here and here. We're gonna avoid pointer for the data. Okay? Okay. So the algorithm we're going to go with if the element they pass here in this case, the head right is, um, has has data. That is no. Then we'll just set that data in return. Otherwise, if the data is not know, then we'll create a new element added to the list. OK, so let's try it then. So what we do is we say, if head, uh, data equals no. Then head data equals data. Okay, House. And now here is where we need to actually adds the element to the list. Right? So before we go any further, let me explain this. We call add lest element here we pass. Hello, world. Now, at this point in time, the head state is no. So we just set the data to point to hello world, and we just vast said we're done right when you come around the second time. And I had this element of the list. The heads data is no longer know because we said it on the first time. We call this function right. So the else is called now in this else. What we're gonna do is we're going to get the last element of our list, right? And then we're gonna add to the back of it. It's really simple. Is that so? We need to make a function for that. Right? So let's do that now. So we're gonna go instruct list element, get last list element, and we're gonna pass in ahead here. Okay? Nice. So what we're gonna do, hear them got getting get last list element will do just that. It will get the last list element for us. So we're gonna come back to this, But let's go back into this body here. Now, for the moment, we're going to go distract list element, and we're going to go e l e m for for new element equals And we're gonna do a cast. Here, guys. My lock. So I had to allocate memory sighs offs trucked list element. Okay, cool. So we're going to now do We're going to go e l e m data equals data. So just for this clear, We've created a new list element here, but it is an attached to our to our new list. It isn't attached to our list yet, right? So it's just there on its own. So I hope that hopefully that clears up on. We set the data to data, but we did forget initialized this list, Ellen, which we need to do so just above here. Just do innit? List Element on. We're gonna pass in that. Okay, so that will initialize the list element. Then we'll set the data to the data provided to us. Okay, Now, at this point, it's just there on its own. We still need added to the list. Right? So we're gonna do that next, And to do that at the top of here, I just need you to go strapped. Lest element last year, Liam for last element equals get last, lest element. And we're gonna pass in the head here. So what, this will do, This will loop through all of our list until it gets the last element. Then it will return it. But, you know, as you concurrently see, got getting this get last missed element doesn't actually do that yet, so we need to actually implement that now. So what I want to do is I want to go struck a list element inside this function. Guys, we're gonna go see you off. A current for current element equals head. And we're gonna go while see you are does not equal. No. Okay. And in here, we're going to go if see you are next, equals no. Then we're gonna break. Okay? Otherwise, we're going to go see you. I see you are next. Now here just to return. So you are. Okay. So let me just go over this briefly, we set a pointer to our head, Okay? Called. See, you are current current element. Basically, we say if the sea you are is not know. So in other words, if they didn't just provide a no head to us, which would cause assist which would cause a program crash, we try to run it. Ah, run this coat. Okay. And then we say, If the next element is no, then we must have reached the end of our list. So that's break. So then it will break. And then there's our last element right there. Online. 28 being returned here, right? Otherwise, if next does not know, then let's go to the next one so we can look back around until we can find the last element . That's how that works. Okay, so in here, now that now that were wear what the last element is, we can actually add to it. So all you do to add to it to add to that list, you just go last e l e m next Jacuzzi a e l e m. It's a simple is that And I if you composite run that you can see Hello, world. This is the second. And when this is the third element, So I hope that makes sense. So I'm gonna go over this again briefly, just to make sure you understand. So we create ahead. Then we add Hello, Walter. The list we add this is a second element to the less. And then we are. This is 1/3 element of the list on our first call here. Add lest element Hello, world. We know that the head doesn't have any data yet. So what we do is we set the head to equal to something on our first on office call to this function, right? That's all it does on the second call. We can see that our head already has data. So what we do is we find the last element in the list by iterating through the list until the next is now. Know when the next is No. We know that the that element has to be the last element in the list. Right? So we get that element, and then we we create a new element, and we upended to the end of that note by setting its next bearable. Okay. And then we do the exact same thing for Adam and three here. So that is how all of that is working. Guys, I really hope that makes sense. If you're still confused, please ask me questions. Try to be as detailed in your questions possible. Eso Aiken best help you. Um, but basically, you know, the first few minutes of our video of this video, you know, is a lot more simpler. Well, it's no different. What we're doing here is absolutely no different. I've just abstracted out a little bit to make it cleaner so that we can just call these functions and do this nice. And simply now there is one of the problem here. We have a memory leak where allocating memory and we're not freeing it. I'm gonna show you how to do that now and then That will conclude this video. Okay, so what we do to free that memory, then we need to create two struck function. So first things first down here after we've ever positive, we're gonna call destruct List and we're gonna pass in the head there so that that will clean up the list. Clean up the memory off the list, OK? On what we're now going to do, we're going to go avoid to struck list. And here we're gonna have a list A list element provided to us. The head element, I should say. And we're going to say struck list element. See, you are equals had next. That's all we're gonna dio on your nose. We use head next here, right? That's because that the head is initializing stack here. If we tried to free the memory of the head, it would cause the system cause the program to crash right. Our rule for using are linked list implementation is that you were responsible for the memory of the head were responsible for the memory of the other list elements. That's the rule in our system. Right? Uh, we've just made. So that's why we use head next. And we don't just use head, okay? And also this. The rule also requires that the head is not know as well, right? That had when when they pass it to destruct list. So here we go. While see you are there's no equal. No. So we do on now. We do. Um, instruct a list element. Uh, next equals c ur next. OK, and then we do free. See, You are and then we do see ur equals next seal notes. We've had to create a variable here, right? That stores the list elements next on. The reason for that is because we're about to delete the memory of our current list element . So if we were to do something like see you, I could see you are next. We've just freed the memory for that. So this could crush program, right? Which is and this is the reason why the store local variable here before we delete the memory of see you are okay. So if you now come problem run that you can see that works fine on our memory leak is gone . Because now, when we called the strike list, it goes through it all on. It frees the elements that we allocated here because you can see here we allocate the element with my lock. This frees them. 4. Double Linked Lists Explained: Okay, so we just discussed what linked lists were. I know. Want to explain what? Doubling lists. So to be on this video, I assume you followed the course all the way through so far on that you've created your very first link list. If you haven't go back and do that cause you won't understand this lecture until you do that Okay, let's continue. So what are double linked lists? Essentially, they're pretty much like linked lists apart from there, aware of the element before them as well as the element ahead of them, a traditional linked list is only aware of element ahead of it, right, not the element before it. Double linked lists are aware of the element before it on the element after it. So let's explain that a little further. So what is the element structure for a double linked list? While they have a value, elements of a double Inglis have a value they have appointed to the previous element and finally appointed to the next element. So in our normal linked lists, we only have a value and appointed to the next element. Right? Double likeness has ah pointer to the previous element as well. Okay, so let's create the list head. So let's imagine that we've added 32 are double linked list. You can see that the list head, which is 30 the very first element, has a value of 30. Its previous pointer is zero or no. On its next point. There is no So we know that this is the head because the previous pointer is no right. There's no element before this one, so it must be the head. Right? Okay, So let's now create a second element with a value of 22. Right? So now, now I showed the addresses that I've made up for this example. We see that the list head is addressed 1024. The second element addresses 5 12 So if you now look at the list head, you can see it's previous is still zero. It will always be zero because it's the head of the list. On the only time it will no longer be. Zero is if you replace the head with a different head. Right. Okay. You can see it's next is 5 12 which is our second elements address. So down to our second element you can see the value is 22 it says here the previous element is 1024. So address 1024 is our head, so you can see the second Adam points back, back to the head, and you can see it's next to zero basically single, signifying the word the end of the list because there's no other element after this one case. Let's create 1/3 element so we can see it's address is 5000. Its value is 83. So holds value 83. Its previous element is 5 12 on the second elements. Previous element is 1024 Right, So can you see how you can trace it back? By using a double linked list? We can work our way backwards or forwards, whereas with the traditional link less, we can only work a way forwards, Right. Okay. So we can see the third elements. Next is no. Which means that the third element is the last element. The list. So, you know, double Inglis a great because let's say that you were only aware of the third element. But you wanted to find out whether head waas Let's be easy. You can see the previous is 5 12 So you go to fight 12 which is this one. And you can see the previous is 1024. So you go to 1024 then you can see the previous zero. So 1024 must be the head, you see, Double Inglis are fantastic guys. So, yeah, we're going to get onto making those now. 5. Creating Double Linked Lists In C: Hello and welcome. So we're now gonna learn how to create double linked lists. Will be working with code we made originally for original link list. Will be adjusting that So it works is a double linguist. So the first thing I want to do I want to go strapped list element prep for previous on. Just put Put that pointer inside the list element structure here. Okay, so your list element structure will now also have a previous variable as well as the next. OK, so now what I wanted to do is go to your ad list element function here. You'll notice we set the next, but we don't set the previous we need to set the previous now because we're creating a double linked list. So to set the previous just to e l e m prev equals last hour elements right here. Right? So what we do here is we get the last element that gives us the last element. We create a new elements. We set the element data to the data provided we set the elements next bearable to point to us, which is correct. But now we do something different. We set our previous variable 2.2. The last element. Okay, so then that allows it to become a doubling list. Because then we can take any given note and we can work our way backwards or forwards. It's up to us. Okay, So we now need Teoh Goto our initialization function on We need to initialize the previous to know and now I think we have done If we now compile, um, run that gcc main dot c Dachau main may we can see that it works as normal. But now let's program it so it reads backwards. So then just to represent that, we need to get the last element first. So we'll call our gap, get last list element function here and we'll do C u r equals get last list elements and percent head. So that'll our current will now be our last list element. We can see if current does not equal no Then run this. But now, instead of setting current equals current next to currently quiz current prev right previous pref. So if you now compile that again, run that you can see that it now plays it backwards. This is the third element this is the second element hello world, whereas when we do it the normal way, it says Hello world, This is the second element. This is the third element so you can see that by making a double linked list. It can allow us to go toe the previous element on the next element in the list so we can be given any element in the list and we'll know what the previous element waas on. We'll know what the next Ellen Waas of the element provided to us. 6. Where the list value becomes the list element: Hello and welcome. So I'm gonna show you how you can do a clever little trick here and see Now, wouldn't it be great if elements list elements could be the item itself? So, for example, you see here we say add list element. Hello, World on. Then it creates a new list element and sets the data, right. Wouldn't it be great if we could have string list element? And it is somehow the element itself. So think of inheritance are like a base class, for example, called list element You might have string element extends list list element number element extends list element will obviously in C in the C programming language, you don't have object orientation. Right? But it's a special need, little trick weaken due to get close to that. And by doing that, it will mean that we won't have to pass in data like this on the list. Element itself will be the data. So to demonstrate what I'm talking about, let's first make a copy of this. So we have a backup because I'm gonna actually stride a new C program. Now just to show you what I'm talking about and I'm gonna zoom out slightly. Okay, So what? I wouldn't do that. I want you after. You mean a copy. I just wanted to delete everything here, right, just to lead at all. Okay, so we just have a normal main function here. Right on what we're gonna do, I'm gonna show you this Look trick. Um, and then and then we're gonna apply what we learn to the linked list. So I just wanted to create a new structure. Call it base destruct. Okay, on. I say, this is a trick. In reality, it's not really a trick. It's just it's just how memory works. But we'll get to it, right? So just create two variables in here A A and B that should be be Nazi. Just just so is more readable. And then here, we're gonna have a child struck struck child construct. Okay. And that's just gonna have a seat. So, in the inheritance, when I talk about inheritance in in high level languages, how would you do that? I didn't see them. I mean, it's not really inheritance, but from a memory level, it kind of is. So how you do that is you do instruct base trucked Be So you do that in the child's trucked ? Right? So now child struck now holds the base trucked. Okay, so now let me show you how you can use this. So here, we're going to go striked child's trucked, and this is gonna be appointed, by the way, guys. So prepare for that on. I'm just gonna call it CP for Child Pointer. And I'm just gonna go and cast this now, Malek size off obstruct child striked. Okay, good. So obviously, my lock here was a collect will declare enough room for our child struck in memory. Right, Which is good. That's what we wanted. But now we can now set it so I would I just want to do that. I wanted to go see p b dot A Equals a capital all lower case. Whatever your preference, I suggest you follow exactly as I'm doing. So it's easy to follow. And in here we just go see p c equals see. So obviously our base trucked here, Uh, contains a and B and then our child struck has see in here. Right? So here we just set a to a B two b and C and C two C. Now watch this. Follow what I'm doing. Instruct based struck BP equals instruct base trucks. Cp. Ah, Now, if we just went print F percent C back section, which will output a character does percent cease for on We did BP a What you think's gonna be out? Put it well, capital A of course. So if you if you if you think about this, this makes sense how this works. Because in our child's tracked the base trucks at the very top of the structure. Right? So, you know, if you imagine is taken up some memory, right? And then just below is R c, right? So when we cast her base struck pointer here we have access to A and B, which are which are above sea. So that's so That's how that works, right? Andi, it does work on. We can use this sing concept to make our list elements. Also the list value the list object, right? So you know, like I said, if this was a multi if this if, see if the C programming language had inheritance, you know you would have base element and then you would have a child element. Right? And the child element you would add to the list on the list would expect a base element. Right. Well, this is how it doesn't. This is how you can do this stuff and see So rather than passing a payload, and then we have to set the data element, the actual element itself can also be the value by doing something like this very, very good technique. And indeed so, if we was to now compel that GCC main dot C Dachau main on, we just run made. You can see a So I worked. And if you change this to B and you compile that, you could see B. So you can see we've set the child structure memory here. But even when we cast into the base structure here, the base struck pointer here. We can still access that information because it's at the top. Now, what if it was not at the top, right? Well, if it was not at the top, we have a huge problem. Let's just put this beneath here. Andi, I want you to now output A If we know, compile that run that we see. See? Now why do we see? See why are putting a Because Arch RC is above the base trucked for this toe work it has to be above has to be at the very top for us to cast it like this Because what we're casting the actual memory, right they compile is not aware of any solve in Harrison's going on here because C programming language doesn't have inheritance. Right? We're just literally casting Appointer and essentially telling our program. This is a base trucked right. That's why it has to be at the top of his beneath. Then the cast will What was will point you to to see by here which is not what you want. So it has to be at the top. Now that limit the Lennox Colonel itself implements a list system similar to what I've just shown you here. Apart from it does something quite clever. It uses a key word in the C programming language called Offset Off. Now what offset off does it gives you a relative address from the structure to a member of the structure? So, for example, let me give you an example. If I did offset off, see right, it would give me to right? Because because everything above this the size of charge is one size Charles once last too . Right? So the position of our child strict, remember, see, would be to So I'm now going to show you how to do that by using offset off. We won't be using officer off in our list implementation, but I'm gonna cover it because I think it's important to know. OK, so to demonstrate this, let me get rid of all of this because I don't need any more. And I'm just gonna go print f percent I and I'm gonna dio Baxter. Same there. Don't forget that. And I'm just gonna do offset off. I instruct Child struck And then I'm just going to see right here and now I need us to include s t de death. Dark age include the head fo we now compile that we run we can see to so you can see the offset of our see variable inside the child struck is two bites. So the reason this this is useful to know it's because that that would mean you could place this base trucked anywhere that you like inside your structure. It could be at the bottom of the top on if we then compile that again and also change this to be first guys. And we compile that again, we run main. We can see that the offset to our base tract is one bite. So the Lennox colonel uses offset off so that it confined where the list member is inside your structure. So with our implementation which we're now going to implement, it will always have to be at the top, right, Because we're not going to use this office it off. But the lyrics Colonel, they make use of this offset off just as I've done here, which allows him to place the list element anywhere in this structure they like. So if that makes sense 7. Implementing A Linked List With The Value being the List Element: this lecture continues from last. We're going to create a linked lists now that has the value being the list element. So the list element will both be the value and the list element itself. So make sure you watch the previous lecture before continuing here because you're going to be very confused otherwise. Now, firstly, make sure your program looks like mine. Include thes headers on have a main function like this. We're gonna be creating this list again from scratch so that we can make it perfectly for this example. As you already understand how to remove elements from a linked list we won't be covering any of that was simply gonna only have add and get on. This is important because it allows me to show you what you need to know but not teach you . We've already learned. Okay, so let's start by making our structure destruct, lest element and now our list element this time won't have a value of any kind. It will simply hold the next element. We won't be making a double list, a double linked list year. Guys, this will be a normal linked list because you already know how to make a double linked list if you've been following all of the lectures. Okay, so that is actually it for our list element. All it takes is a next on that is it. So our next element will be no if the list, if there's no other elements on the list. Otherwise it will point to the next element on the list. Okay, So what we're gonna do, then we're gonna make a animal structure that will simply hold animals, name and the animals age. That's all it'll hold now. We obviously want the animal to become a list element. So I need you to put destruct, lest element element at the very top of your structure. So, once that is at the very top of your structure, we can cast or a list element pointer at any time on an animal structure. Andi will be had access the next variable off this list element here. Okay, so let's make a initialization function void in it list element. So this will be responsible for initializing list elements. Andi, in here, all we do is we go element next equals No, That is all you do on in here Now. We're gonna actually create our animal head. So I just wanted to instruct Animal Head Okay, And then we're going to go in it, lest element and we're going to just pass in the heads by here, and we're going to cast it. So a list element and you'll see that works correctly because list element is at the top of our animal structure. So by casting it to a list Ellen pointer, it has access to the next variable. Remember, this has to be at the top or this will not work correctly because of the way the memories is aligned. Let's now compile a run that so you can see it works correctly. GCC main dot c. Dachau main type main and you can see nothing. And there's been no crash, so that works correctly less now. Compile and run that so you can see it works correctly. GCC main dot c Dachau main type main and you can see nothing. And there's been no crash, so that works correctly. So we're now gonna want to add the A B to add elements to our link list. So let's just create another link a link list element here. We're gonna go instruct animal. Uh, dog. Right. Okay, so the dog we said its name. It's a hello world. Well, I tell you what, let's call it this. Call it a proper name. Sam. Sam the dog. And we said it's ah, age to 14 is an old dog. Um, Okay, cool. So now you also need to do in a list element. Appear, guys. Andi passing, um, the actual address of the dog. Okay, because, remember, animals are list elements in this implementation we're doing okay, so then we go add list element, and now it's gonna expect the head. So we do an percent head cast. That's a list element on day two here. We're gonna cast another less gentlemen here, and this is gonna be absent, dog. Okay, so this will add the dog. So the other actual linked list and we pass in the head, which is here now, the head could also be a real animal, and it probably should be as well. So this might be a cat or whatever, but I've called it head just to keep things simple right now. Okay, so we know need to implement the ad list element function so I want to do. I wanted to go. Avoid add list element Instruct, lest elements head instruct list element. Um value. Okay, Andi, Now all we have to do is find the last element in our list and a pen to the end of it. So we need a function for that. Do struck a list element. Um, we're gonna call it get last list element just like before on that is gonna accept the head . Okay, now, here. We need to look through until we have the final list element again. So just instruct, lest element current equals head while current does not equal no. And then we go See you. Ah, next. Now we go See, you are equal. See, You are next, and I just appear we say if see you are next equals no. Then we found the last element return. So you are OK, so that will return the current list element on here. We could just return. No. Okay. Okay. So what we now do then is we say, um, obstruct. Um, lest element and we say last element equals Get last list element on We pass in the head there. Okay. Oh, and actually, before we continue, let's just change this slightly right instead of instead off doing that will just break in here and will return. So you are here because we shouldn't actually return? No there. So here we get the last the last list element. And now the. Now that we have the last list element, we actually have to append its next variable to our list on value. So to do that, just go last element next equals value, and it really is as simple as that. That's how you can add lists elements to the list. Okay, so now we need to give the A beat, actually get elements from the list. But before we do anything like that, I just want to say something quickly. You'll see here we cast a struck list element. This might be a bit annoying, right? Doing this every time. If you don't have it on you, compile, you'll see that you'll have a compiler warning, which is not good, right? If you want to get around this, then this could be a void pointer here, which means that you won't have to cast what you're passing in UK and then you'll have to cast this void head back in the list element inside this function. But it will mean that people using your code won't have to cast a list element every single time. So that's just a design decision you might want to make. But I'm gonna keep his list element. Just keep things clean and simple for you. Okay, so let's give our head animal and name. So we'll call this. I don't know, Alice. We had named for a cat, right? Um, and I was his age. Is 10 an old cat? Um, so once we have added the dog to the head, we now have to list elements. Andi, just to demonstrate that we're now going to loop through are linked list output thes actual animals. Okay, so to do that, we're going to go strapped animal, and we're going to say, see you off a current and we're gonna point that toe head. OK, now we're going to say Well, see, you are there's no equal. No, we're going to go print af um percent s and then we're gonna go column percent I and then we're gonna go back slash So what basis? Just gonna output the animal's name and age. So in here, we're just gonna go see you are and we're going to go. Name. See, you are age. So hello. Put Alice Colon. 10. Sam Colon 14. So here, if you just If you just to see you are equal. See, you are next and no. Sorry. See, you are element. Don't next. That's where you need to do because we haven't casted to a list element. Right? So we need to actually manually access the list elements from animal structure here. If you wanted to cast that, you could. But it doesn't make sense, because without putting animals, So this this makes a lot more sense here, right? Okay, so if you compile that now, you're probably sick and power warning. Yes, you do Assignments trucked Animal from incompatible point A type now our next. Our next variable here is still a list element, right? But we know that all our list elements in this list are animals, so you can just safely cast it to an animal like that without any consequences. However, however, bear in mind, if your linked list have different types of elements, then this would be dangerous and would not work. If you now compile them, run that. You'll see it compiles you. Run it on it says Alice. 10. Sam 14. So you can see we don't have to add the head to the list because the head is the start of the list. Right? Um let's say we wanted to add a cat, right? Not a cat. Add another type of animal. Let's say on elephant, Right, So we'll name it. Elephants will initialize the elephant. I will call the elephant on a Bigfoot or whatever, unless to say he's 22. Is that all for an elephant? I don't know. On if you change this to elephant here as well. So now we should have three elements of the list. So if you now compile them, run that again. You can see an error. Why do we see in error? Ah, because I set the dog by here. You need to actually change these variables, guys, because I copy and pasted that. I assume you did the same. So there should be struck dead animal Elefant We initialized elephant and then we set the name on the age. So when I say we initialize elephant. What I mean is we initialized actual list element of the elephant on Do not the properties of the animal. Um, okay, so if we know, compile it again, Run that we can see Alice's 10. Sammy's 14. Bigfoot is 22. So there you go. Now you know how to do it. You now know how to have the list element Also be the value off the list. This is how the Linux kernel does it. This is the correct way to do it. Um, you can you you can create Macron's in C to make this process a whole lot cleaner. But this is the This is the correct way to do it. Um, So you could also use the office it off key would that I talked about in last lecture to improve this implementation. But I hope that makes sense, guys. And if you have any trouble with that, please send me a message and I'll explain it all 8. Understanding Arrays And Array Lists: Okay, so we assumed to create our own array list in the C programming language. Before we can get to that, I need to briefly go over how raise work in memory. Even if you have created a raise before it's important, you understand how they work at the lowest level, as we're gonna have to be doing some of these calculations ourselves. So what is it? What are raise a race, hold a fixed number of elements much in the same way a pack of Pringles crisps can hold only a certain number of crisps, Unlike the Pringles example, a raise always hold the amount of elements they were allocated with, regardless, if the element in the array was set or not. In other words, if you decide you want a program that holds 20 numbers of Instru type, even if you don't use all of those 20 numbers, they will always exist. So you've created array that could hold 20 numbers. Those 20 numbers are either un initialized or set. They always exist. So another thing about raise. If you want to extend or shrink the array, the memory must be re allocated. So back to the allocation of an array that can hold 20 elements. Um, if you wanted to only hold 15 you have to reallocate the array, which is time consuming, So a raise must also hold fixed sizes. In other words, you can't have an array that holds numbers and strings and characters on bites. It can only hold a fixed size type, and this on the type, must always be the same for the entire array, or at least the same size that is you could you could technically store elements of the same size. But storing elements that are smaller or greater will not work. Okay, let's not see how an array works, so less less. Imagine an example program where we request five inches numbers from the user on we create in the ray named Array that then holds those five in judges. So what we do is we create an array that's that holds five inches. That's the first thing we do currently. They all hold zero. You'll notice that Ah, here I've put indexes. This is how it works in your program as well. Index zero is the first element in the array, and then it goes Index one index to index Tree index four and so on until the end of the rape. Accessing a race starts at zero in the C programming language, we don't access Element one as index one, we access element one as index zero. So here we set index zero in our rate to 10 setting index to 2 30 Results in the relative address in memory two multiplied by four. He was eight. So address a get said 2 30 now more will be explained on that later. So if you now look at the physical memory of our two indexes in the array, you'll see that they Each index represents four bites because in judges are four bytes in length in the X 86 family, each index accesses the start of four bites. So, for example, Index zero will stop from accessing bike zero. Here, Index one will start by accessing bite for here, so also noticed how each element in the array is right next to one another. This is important to note. Unlike link lists, a raise have their data in Siris right next to one another, so Index zero represents four bites. Index one represents four bites accessing Index zero will access by zero accessing index. One will access by four because in judges are made up of four bytes, each four bites represents one inches. The's four bites represent the first interest er in our raid. Thes four bites represent the second injured in our ray index. Zero is for the first introduced in Ouray Index one is for the second instrument in our rate. So if we wanted to retrieve the value of Index one, the compiler generates code to get the absolute offset. This this is pretty simple. It's the elements size multiplied by the index. There is the relative offset from the array variable. So let's pretend we access index one. Ah, the math is formal. Supplied by one equals four. So four is our relative offset from the array to get to index one. Our second element. Remember, our introduce are made up of bites. Four bites are each element because inches are four bites Insights. So when should you not use a raise? Don't use a raise if you don't have a fixed amount of elements. If you're unsure how many elements you're gonna be using than a raise are a really bad idea . Use a linked list instead. Do not use a raise if you want to store elements of different types. If you're storing longs and in changes, you can't stop them together in an in an array. Use a linked list instead. So we are going to be implementing our very own array list implementation in the C programming language. We will allow users of our list to easily add elements to the array using functions we will create when our Rayburn's at a room, we will actually reallocate the entire ray, making a larger allowing form or elements to be added to it. We will also allocate more memory than we need to, so so that there is less memory allocations. This will lead to a faster array list implementation. 9. Programming Arrays And Array Lists: welcome. And in this lecture, we're gonna program a raise. So first, let me show you what Honore is. If you just follow this. This is an array. The holds 512 characters. You said each character by index, you can access each character by index this output index one be so a raise allowed to store data in order. In other words, these 512 bytes are right next to each other in memory. Right here we store the data on the stack, the array of stored on the stack. This means the one released scope. That information is no longer accessible. Let me show you how to create a raise on the heap. So the first thing we need to do is include the STV lip Hedda down here. Just do shar ask a risk. Buf equals Shar asked. Risk my lock 512 Okay, That will allocate 512 bytes of memory on the heap. Here we cast to a char pointer allowing us to access each individual bite You can now do be UFC Ro equals a buf one equals B just as before. If you use GCC main dot C, Dachau, Maine. And you run the main application you'll now see. Be out. Put it to the terminal. So what we've just done here is we've created a raise. Now let me show you how you can create an array list using these techniques you've now learned. Okay, so let's briefly go over what we've done so far. We allocate 512 bytes of memory on the heap, so the operating system will return to us a memory region that can hold 512 bytes. Now we cast this to Char pointer, allowing us to access each individual character by index. So Buff zero is the first element. Buff one is the second element. We can then set those two characters or access the miss characters. Okay, so we're ready to begin less first. Ensure that you have included sed ioo dot h and SC live dot h. I now need you to include STD bulled our page. Okay, now let's start with our our structure Do struck array list. This structure will hold our ray list. Properties in here trade a character pointer named PTR. This will point to our actual data on the heap and I want you to do size. T count on size T. Oh, count. Now, just to explain this count will be the number of elements that actually are in our array list. Oh, count will be the number of elements we are aware of and can access. Essentially, we will. We will always allocate more memory than we need so that if you are adding to the list quite a lot, it is, ah, much faster. Because if we didn't do this, we'd have to reallocate the memory every single time. We wanted to add one element of the list. This will mean a very slow list. So what we'll do is we'll allocate the memory more than we need to. So, for example, if we were to have one element of the list we would allocate 10 elements on, then that would then mean that they someone could add up to 10 elements to the list before the list needs to be resized again. When you reach the 10th element will extend the list to 20 elements, and then, obviously when they reached 20 elements, will extend the list of 30 elements. This is much better than doing it one element of time because otherwise we have to reallocate the memory every single time. Okay, so let me now explain. Count on. Oh, count count is the size of our A list. How many elements that holds? But this is not the accessible count. Oh, count is the accessible count the amount of elements we can access now. Now what do I mean by this? Well, one you add elements theory a list. You have to resize theory every single time. This is a very slow process. So what we do? Instead, we make sure we allocate more than we need, so that so that we have to do less reallocations on Les reallocations of the memory means a faster program. So, for example, our account, maybe 10 which means we can actually hold 10 elements. However, our account may be only too, because we've only added to elements of the list won. The O count reaches 10. We extend the count to 20 recites the list by 20 elements. Account is still now 10. It can then become 11 as you add another element 12 as you had another element 13 as you had add another element. All the way to 20 where the list will then be resized to 30 elements. Count now becomes 30 0 count is now still 20. Oh, count could become 21. So on so on until it reaches 30. And then the list is extended to 40 elements. Count now becomes 40. Oh, count is now 30. I hope that makes sense. We will definitely begin into that more shortly. Okay, so you'll notice the's are size teas. We can probably get away with just insurgent types here. Maybe more appropriate. So I'm gonna change those inch two types on also down here, we need a size t element size. Now we want our A list to be able to hold a certain type. We don't want it to be strictly only for in judges only for chars only for this particular type structure. Right? So what we'll do is we'll take the elements size, and when we know the elements sides, we can make the air a list work with any type. Okay, So what I now want us to do, I want us to make a definition of top of the file here. We're just going to call it um, memory, um, element increase. I was just going to call it 10. And granted, that could be named a lot better. But this is just an example, right? So this is definition that just hope that is just equal to the value. 10. So when we use this throughout our program, it's just replaced with 10. Now, this will be the element increase. So remember I was talking about the counts, the difference between counter no account. While this will be the increased number Ah, the amount of increases. You know, it said, you know, when from 10 to 2020 to 30 we'll ask, Possessed 10. If that was five, be 5 to 10. Toe 10 to 15. So on. But we're gonna keep that is 10. Okay, so let's now create our initialization function, which will initialize are array list just to avoid. Ah, a realist in it for initialization. We're gonna pass in our realist here, pointed to are realists on here. We're gonna have the element size. So they tell us the element size when they initialized the array list. Okay, so the first thing we need to do in our ray list initialization function is we need to actually allocate some room for our 10 elements. Because remember, we start with 10 elements, and and it goes to 20 then 2 30 so on. Right? So what we're gonna do is we're gonna go list PTR equals, and we're gonna cast a chart here. Matlock elements size multiplied by memory element increase. So this will, This will make enough memory forests, toehold 10 of the elements that this ah program is gonna be storing. Right? We know that it can store tended them because they told us what the size of the element is that they're going to be storing here when they initialize theory a list. They tell us the size of their element so that they would pass something like size off in it. For example, where she'll be replaced with four, because inches of four bites and x 86 processes and then size Tieleman sized out before. So the equation he had becomes four multiplied by 10 which is 40. So this becomes 40 giving us enough room for 10 inches. Okay, so next we need to say, lest count equals memory element increase because we know that the air. A list can hold 10 elements of this point in time. It holds 10 elements of this point in time. I mean, now we need to go list. Oh, count equals zero. Why do we do that? Because they haven't added anything to the list yet. We can hold 10 elements before we have to reallocate memory. Which is why we set the count to memory element increase on. We have allocated enough room for 10 elements here, but because they haven't actually added anything to the list, our oh count is zero. Meaning are less sizes zero. So what I now want you to do, I want you to go list element. Size equals element size on that, is it. Our ray list is now initialized. Less. Now, make a function that returns the total count in our list. So we just go into your array lest count and we they're gonna need to pass in the air. A list structure here pointed to it on. We just go return, lest account. Okay, So now if they call the ray list count and they pass in the array list, it'll return the count to them. Granted, you could just access the actual variable in the structure like this. But by using a function like this, it's cleaner, right? So make sure you pay attention. Here we return the account, not the count now, So when they call a rail is count, it will return the amount of elements they have added to, the less not the amount of elements that are potential without having to reallocate memory . Because remember, we allocate more memory than we need so that we don't have to reallocate the memory every single time. We wanted to add an element to the list. OK, less now, actually, start using our A list implementation it coming to do anything right now, But I just want to show you how we can use it. So the first thing you do is get rid of everything in your function. Currently, apart from returns here, Obviously, we're just gonna go struck array list, lest so this is our actual less right. And we're going to initialize it by passing that in on. We're gonna hold in changes in our list. So we just to size off and it okay, And now if you know, did um print f percent I A ray list count, and you passed in that I'm person listed to give the address in list. You would then see that this would just output zero because there's nothing in our less. So just to demonstrate that now I'm going to go gcc main dot c Dachau main. I'm gonna run main on I C zero because there's no elements in our lest Oh, count is zero. Okay, so we're now going to make it seeking Add elements to your list on. Granted, this is a lot more complicated than the link list. So if you have any trouble, just go back and listen again. Or some your message. So the first thing you need to do is include the memory dot ph Had a file. Okay, good. Now we're gonna create a add function, so just avoid array list at, and it's gonna take an array list pointer on a void pointer. Um, okay, so the void pointer contains the address of the element. We're adding to the list, and obviously the array list here is is the list we're adding it to. So when someone calls this, they would essentially call it like this so if we just go into our was 50 and we want to administer to the less right, So we do a realist ad, you pass an M percent list for the address of list and then here you passing and percent r for the address of variable are. So that's how you would add are to the list, right? However, because this does nothing at the moment, it won't be added to the list. So we're now going to create this this function here on implemented correctly so that it can add elements to the array list. So once we've done that, we should see that 50 is added to the list successfully. Okay, let's start implementing this array list. Add function, then all I want to do is only to go at meme copy, M e M c p y. And we're gonna pass in list PTR on. We're gonna open up these brackets ready to pass in the index on the index will be less Oh , counts multiplied by lest elements size. Okay, so that will be where will be writing the data to and I'll explain more about this in a second Now the source will be our PTR. On the size will be the list element sites. So what's happening here, then? Well, no, it's Hear what we say Array list in it. On we pass in the size of in it, which is fall, right? And then we set element size to fall. Well, our pointer here is a char pointer, right? So it we access it as one bite at a time. However, we need to offsets the correct place in memory. If we just did list account, then unfortunately, that would not work. What we need to do is we need to go list. Oh, count multiplied by the elements size. So if I get up calculated quickly, um and I lost to get a note pad. Let's say here than you had an interest. You're right. Let's say you had room furniture here. Right? 12341234 Now the's aarej bites right one inches, four bites. So if you're accessing index zero, this will be zero multiplied by fall, which is zero. So we right four bites at offset zero because remember, here is the count list element sizes. The count PTR is our source where we're reading from and this is our destination. So let's try this again. Let's say you did 11 multiplied by four. So Index one, then that will be the fourth bite. So it will read from so it would right into here it is right for bites into here, right? So that's how that is working. That's why we need to multiply by the elements size. If we didn't do that, then Index one would be here. So it overwrite our first interview in the in the actual list, which is not good because we overwrite another indexes memory. So now, in case you haven't what realize yet Oh, count is our index here. This could be used as our index because when not we're not having it so you can insert a certain position. We're just having its you can add to the list. We're not gonna over complicated too much. So now, down here, I just needed to go list account plus equals one. Okay, so then if we wanted toe call a realist ad again down here, you don't have to do this and just showing you Then the second iteration, the second call here. Oh, can will be one. So this will be one multiply by elements size on elements sizes four. So this becomes one multiplied by four which gives you for said that this opposition is fall, which is correct. We read four bites from our PTR variable here and we write those four bites into here. Okay, So that that a work so that there's one problem with this implementation when we reach maximum count. Because, remember, we've allocated room for 10 elements only right when we reach that count. Unfortunately, then we're gonna be writing to memory we don't own, and this is very bad. So what we need to do is we need to check to see if our account is above or equal that the current total count available to us. And if it is, we need to extend the memory. So let's do that now. So to do that, all you need to do is you need to go if list oh, count above or equal, lest count, we must precise the memory. Okay, so now you do is you go list. PTR equals. Really Look. And also make sure you put a chart cast you guys sharp when the cast here really lock and we're just gonna pass in, um, the original block, which is less PTR. And now we need to pass in our new size. So our new size will be the current list count, which is 10. Right now on the first the first time this this happens, it's 10. So we did the current discount multiplied by the lest element size. Okay, Andi, by here. Now put another bracket here and we're gonna go plus memory element increase. Okay, Unless should do it. So what happens here? Them the less count, which will be 10 at this point in time. When this is first called, we get the list count, we add at the memory element increase to it, which is 10. So this becomes 20 right? So then we do 20 multiplied by four, which is 80 on then. We have now successfully reallocate the list. We can now add another 10 elements to it. Okay, Um however, there's one more thing that is due here. We need to change the count. So we go lest count plus equals memory element increase. So then that means that on the first on the first call to this one on the list. Counties. 10. Right on the old counties. 10 will happen is we reallocate the memory Now we had just account by adding another 10 to it. Right? So then let's count is now 20 0 count is still 10. So Oh, count can become all the way up to 20 before we ever have Teoh, go back around on DA. Reallocate this to 30. Okay, so that makes sense. So now, instead of reallocating every single time, you want to add an element of the list, we only reallocate when we need to. Meaning it's gonna be much faster. Okay, So there's one of the thing you need to do here now, before this is ready, I need to put an percent start by here cause I forgot to do that. Put Anderson by there on DA that that that will get us the address of that index. So we now compile it again. GCC main dot C, Dachau main. You'll see that compels fine. If you type main, you can see that we see too. Because our rail is count is now too. Which is why outputs to Because here we are put there a discount. So we saw 50 on our ray list twice. Obviously, we don't have any function right now to access it so we can make that next. Okay, now let's make a function that allows us to get an element from our ray list by index. So essentially, I just wanted to go instrument sult equals zero a ray list get, and that's going to take in our list. It's gonna take in the index, so we'll just do index zero for now, and it's gonna take in the result. So we haven't made this function yet, obviously. But we're about to make it on what this will do. When we call it like this, it will get the value of index zero and story and result. If that was one, it would get the value of Index one, and it would store in result. Okay, so let's make that function No. So I just wanted to do, um pool array list. Get struck. Array list less on. Here goes index I NT index. And here is a void pointer to are out so you can call that out of you on. We'll call it out Okay, So you need to ensure that STD Bull is included. If you haven't done that already, guys, otherwise there will be a problem here. Okay, so what we're not going to do is we're going to say a meme copy and percent list PTR. And now here we're going to go Index multiplied by lest element size. Okay, Andi, um, best fine. Now, at the start here, we're going to go out. Okay? And then here, we're going to go. Ah, list element size. So all this will do this world copy from our index into our out variable into out pointer here, and it's gonna copy the elements size. So once again, here we initialize our A list with the elements size off the size of in it, which is four bites. So this basically becomes four by here. Right? So this becomes index multiplied by four on we copy. Four bites. That's how that works. So that will work. Okay, um, down here, you returned true because everything went fine. I now want us to do some bounds checking, so we're going to say if list account and at the top at the back here, we're going to go index above all equal account. So So if the index provided is above or equal the the count on the list that the use account on the list, I say use a camp. What I mean by that is they've added two elements, so the account be too. If the index is above or equal to, then there's been a problem. So we return false because the out of bounds right, the out of bounds. Now, obviously, we we know we have enough data to allow them to continue because we allocate more than we need. But that's not the point that's supposed to be abstracted out from the user of our A list, which is why we use the account here because they're not actually supposed to access the memory that they haven't told us about yet. We've made more room that we need to. They're not supposed to access that until they actually call ad right Then it's legal to them. OK, so now let's change this array discount here, and we're just gonna output results on that. We should see 50 here, right less compile that run again and we see 50 so well done this is working now, just by here. We need to change our 20. Okay? Just after this first ad, and I want you to come polymer that again and we still see 50. That's good. Now change this toe one for index one. Compile and run that again. And now we see 20. So, congratulations. You've made an array list implementation that actually works. We now kind of want to make it so you can remove elements from the list on. We also want to make it so we can actually destruct the list gracefully. Because we have allocated memory here. Andi is our job to clean up after ourselves. So we're now going to implement the ability to remove elements from the array list. So follow as I do, we start with an array list remove function that requires our list on the index to delete. Notice how it returns a Belene. We need to do bounds. Check in here, make sure you return Sure at the bottom of the scope. So if the index is above a recall, the list count will return false because we cannot continue safely. Otherwise we returned. True. Obviously this doesn't remove the element yet, so we're going to get to that now. So the way we remove an element from the array list is we have to shift all the elements to the left, so follow what I'm doing. So we looped through all of the elements we have pushed to the array list or added to the array list, I should say, And now in here, we need to actually shift them. So we do that with a men copy, so follow what I'm doing. Meme copy, Empress End list PTR. I multiplied by list element size, which will bring us to the actual data for our A list. Now, um, noticed This is the destination. Okay, now, next comes the source, so the source will be amps. Unless PTR our bracket I plus one which will give us the next element. And then here we're going to go multiplied by list element size on here. We do list element size as well, because that is the size of the data we are copying. So that should work. Let me explain this briefly. We copy the next element into the current element were arm and obviously this is the loop rights of the current elements represented by I. The index of the current elements represent by I. So then we multiply I by the elements size to take us to the correct position in our bike data. And here we do. I plus one taking us to the next element. Right? So we copy the next element into our current element on. We want to copy the amount of elements size, which in our case, is four bites because we have a a ray list of inches. So there's one more thing we need to do. We need toe, actually deck crimen the O County A. Right. So to do that, you just do, lest account minus equals one. Okay, lets no test our A list. So what we're gonna do is we're gonna delete element zero and then output alum and zeros to change this 1 to 0 on in here. We're going to say array list, remove and we're gonna pass in our list on we're gonna pass index here, here and now. When we output element zero, we should now see 20 instead of 50. Because we delete Snell, um, from the from the last right. So let's no tests that out. See if that works. So to do this, compile your program and ah, type of Maine and you see 20 on my main functions. Avoid there and change that in Ginger. How that happened, right? Um so we see 20 output it, which is correct, Right? Because we removed 50 from the list. So then we only have 20 on the list. Okay, so let's no make a loop to correct quite a lot of these, right? Just to make things a bit simpler to see, so we do. Intra, Aiko zero I below I below 10. I plus plus on. We're going to go in here and we're going to say, Ah, released at and percent list. And he is gonna ask for a pointer. So we're gonna pass in absent, I So this will add I to the list. So on the first situation, I zero So adds you to the list. Second, Iterating denies one. So adds ones of the list and so on. Right? I'm just gonna comment this out of second, and we're now going to loop back through it here on output, whatever the value waas. So here We're just gonna go for Instru equals for instant. I equals zero. I blow 10 I plus plus and then in here we are going to run this code here. The Coby wrote earlier. So this zero here is our index remembers. So you need changes, toe I So this will, um first situation will load index zero load the value of index zero into result second iteration load that it lowered the value index one into results and outputs. Thumb as it does that. Okay, so we now compile that again. You can see 0123456789 Which is correct, right? So less Tilly Element three. So, element three them will delete that. So just do a ray list. Remove and three in here. And remember where Deleting by index. Here. Not value. Right? Okay, let's now compile. Um, run that. So if we do GCC main dot C Dachau main on we run main. We see 012456789 So you can see it's deleted three from the list. So this worked correctly. You'll notice we see a zero at the end here. This is because we read 10 10 bites from here, right? We read 10 elements, I should say not 10 bites. We read 10 elements from the list here, which is why we see zero there. Because on on this situation on the final iterating in a realist get actually failed, it returned. False on. Just to demonstrate that if statement there, you don't have to do this and just showing you, um and I do print if, um a really scared failed. Okay? And if I now compile and run that again Yeah, you can see a release kept failed, right? Because on the final element, it tried to get index nine, which doesn't exist in the air. A list Serve return. False. So we made a function earlier this perfect for this array list count. So you have to do when we're out putting it by here. Just do a realist count. Pass in amps. Enlist here. And now if we now compile, um, in that you can see it. Only it now only ghostly what is actually on the list? Because it knows how many elements that that list has at this point in time. Because we removed three from here which deck remounted account, right. Which means the size of the list changed. Okay, when our raids do the final part, and that will be to destroy lucked the actual array when we're done with it. So I want to do is down here in the main function I wanted to say array list destruct on passing. Ah, the address of list here. Okay, so now we need to actually create that function. So we're gonna do that now just to avoid a ray list destruct. And this is gonna pass in a pointer of list while it's gonna expect a point of ah ray list . Sorry. So when this is called, we need to actually free the point of memory of this list so that it's simple enough to do . Essentially, we just do free and we've hasn PTR on that Should be it. Try that on. Now, just for good measure, we're going to set the list pointer to know we're now going to compile this program with GCC main dot c Dachau main. If you now run made, you can see the program works as expected. Congratulations. You've now created your own array list implementation 10. Understanding Stacks And Queues: welcome. And in this lecture, we're going to discuss stacks and queues. Throughout this lecture, the world container will be used. When I use the word container. I refer to something that maybe an array, an array list, a linked list or any other possible type of structure. Stacks and queues are a way for you to add data to a container of some kind. On later, pull that data back out in a particular order. More will be explained in that shortly. Discussed Here are two types of stack implementations life Oh, and FIFA Life Oh is last in first out. If this is the model you're using, then this is known as a stack elements added to the stack former container. You can then call a function to get and remove the last element added to the stack Fife Oh , or first in first out, if you use this approach, when you adds an element of the container, it will join a que think of a que In the shopping market functions would exist to get the element in the front of the queue and pop the element from the front of the queue, otherwise known as D cute. Let's now explain this a little better In the stack. Implementation. A user pushes the number 50 20 and 42. The stack user. Them pops from the stack. 40 is returned. Now the stack only holds 50 and 20. This is a stack. The last in first out approach. We pushed 50 to the stack. We pushed 22 the stack. We pushed 42 The stack. The stack now holds 50 20 and 40. As can be seen in this graphic here we now popped from the stack. Notice how the last element we added to the stack is removed. This is last in first out forties returned. The stack now only holds 50 and 20. We popped from the stack again. Now 20 is removed from the stack again because 20 was That was the last one added before 40 . Stack now only holds 50. We popped from the stack again with stack is now empty and we have popped all elements from our stack implementation. The stack is now empty. When should you use stacks? You should use tax when you care very much about the last element that is added to a list or a container. Did you also know all modern processes, including the one in your laptop, have a built in internal stack that almost all applications ever written? Make use of even the Web browser you're using to watch this video? Right now, you will not even know that you are using the stack Modern languages, including C and C Plus plus abstract this out. From your view, we're now going to explain what a Q is. So let's imagine the scenario where three people are buying lottery tickets. Each lottery ticket has only one number. The customer can only pick one number for their lottery ticket. So Jack joins the queue to buy a lottery ticket with the number 50 you can see he is now at the top of the Cube. Chloe then joins the queue on buys a lottery ticket with the number 20 she's now waiting behind Jack. She's also joined the queue. Dan joins the queue to buy lottery ticket with 97. He is now at the end of the queue behind Khloe. Our Q is now full. The shopkeeper finally returns from his long, lazy break, and he serves the person in the front of the queue. With the lottery number 50 you can see that he has now been served on has left the Cube 20 is now at the front of the queue, and 50 is now irrelevant as it is out of the queue, and we have processed it. Our program has processed number 50. The shopkeeper now serves Ticket 20 and now, once again, 20 is now well irrelevant, and 97 is at the front of the queue. The shopkeeper now serves ticket number 97. The queue is now empty for now until someone else comes and joins the queue. So here are some really world examples of queues. Printer jobs. If you If you want to print a bunch of documents, they will join a Q A printing queue. Game lobbies, so you're free. Your favorite games one that when there's not enough room for you to join the game, some games will add you to a Q, and it'll say like five people ahead of you while this is a cube, so that's a real world example. Off a que inside a computer program, stacks and queues can be implemented in many ways. We can implement them as a linked list Honore list or even just as an array 11. Creating A Stack: welcome. I'm now going to show you how to create your very own stack by using an array on a variable that points to the position in this stack. Let's now begin. Firstly, make sure your program looks like this. Include the STD ioo dot h head a foul on the sud lib dot age header file on Have a simple main function the just return zero Once you have done that unp ause the video. Okay, we're going to create an array called Stack at the top here that can hold 512 elements. Now here we're going to create a stack pointer which was just going to call SP now in here . We're going to say void in its stack and all of that is going to do is meme set the stack two zeros and it's also going to set stack pointer to zero as well. Now be sure to include memory dot Hey h at the top by here inside your main function now coal In it stack. We're now going to create two functions. A push function on a pop function will create a stack push function that takes in an interview called value. It will add this in treasure to our interest Stack. And we will also down here have a stack pop function which will Papa ninja from Mossack. Let's now implement the stack push function Simply do Stack s p equals vow SP plus equals one That is your stack push. It will add an element to the stack at the Cone Index represented by SP variable. It will send it to vow, and it will increment the stack point of by one so that it points to the next in Ginger in the array. We're now going to implement the stack pop function. So all I want to do is to SP minus equals one to deck Ament the stack pointer by one. And the reason we do this is because here we add one to the stack pointer. Right, So that points to the next element, ready for the next push. So when we pop, we just need a minus one just to bring it back to the last pushed element. And now here. I just wanted to go return stack S P It's a simple Is that on? We can now actually use the stacks. Let's no do that. So to use the stack, simply Go stack, push 50 stack, push 20 stack, push 45. Right. And now, if we now go print f percent I back session stack pop. We should see 45 output it because that was the last element we pushed. And remember the stack when you popped from the stack, it gets the last element that was pushed. So if we now compile that, you can see 45. Excellent. If you copy and paste this So it's exactly the same. You're lost to see 20. Output it. Now compile that again. Run that. Now you see 45 20 so you can see that we push 50 to the stack. We pushed 22 the stack. We pushed 45 to the stack. Then here online 34 we pop 45 from the stack and then here we pop 20 from the stack So you can see here that it's all based on ordering here we push and then we pop our pop functional are stack will always pop off The last Elem pushed. So when we pop our 45 here that the next element that was last push would be 20 because that was the element that was last pushed before 45. Which is why, when we pop here, we see 20. If we were to pop 1/3 time, we would see 50 and then our stack would be empty. So that is, that is how you stacks there. Very, very useful. So one final note. Then we implemented the stack. By using a raise. You can implement stacks as linked lists, array lists. There's many different ways to implement a stack. I went with the array approach because I haven't shown you this approach yet. 12. Creating A Queue: In the previous lecture, we created a stack in this lecture, we're going to create a que we're gonna create our Q Similarly, to how we create a link list. So firstly paused the video and make sure your program looks like this include the STD Io head. If all SG lib memory and your main function should look like this Once you've done that, resume the video. Excellent. We're now ready to begin. Let's create a structure Que element on this structure is gonna hold a value which will call Val and it's just gonna hold a number. It will also contain a left Q element on our right Q element. We also need a structure que our Q structure will hold the first Q element. Now that you've done that, we have all the internal data structures that we need set up, and we can now begin creating some functions. So firstly do struck Que que? This is a global variable. It represents our cube. We're gonna have an innit que function that simply passes in. Q. On also passes in the head of our cute. Now the head of our Q will go here and we're going to call in it. Q element. And obviously these functions don't exist yet. I'm just showing you how it works, and then we'll implement those on in a queue. Element will just simply take in the Q element, okay? And we're gonna also want to pass the value in here. So let's say 30. So this will initialize R Q element with the value of 30. Essentially, it'll set left and right to know, and the value here will become 30. That's what this in a queue element, will do. So this is the head of our cube. Um, this, even though this is the head is still counts is an element in the queue. For example, if if you were waiting in a game room like I like, I explained in the last video and you are waiting before you could enter the game because there was too many people playing the same game that you want to play, for example then and you were the only person waiting, then you would be the head of the queue. So the head is still a valid entity. That is all I've being trying toe. Get across here. Okay, so let's just let's let's just summarise what I've done so far. Here we initialize the head of the queue and then we call in a queue on we pass in the head which will set the first variable here. So the head. So we need to implement those functions now. So up here, let's go avoid innit Cube element instruct que element and all that's going to do is set left and though right to know And we also need a passing the value here as a second argument and that's going to set element vow equals value. So that's all our initialization function is going to do now for a in a queue we go struck que que and in here struck que elements element and we're simply going to go Q first equals element. So just toe put this in perspective. The first variable, the variable named first in our Q structure represents the first in line, essentially the person at the front of the queue. So you can call this front if you want, but I'm gonna call it first There first in line there at the front of the queue. They're going to be served next. Okay, So currently all we have waiting in line waiting in our Q is the head on his values 30. Now, if you remember the understanding stacks and queues video I made on this course, you will know that I referred to the cues as, Ah, a bunch of people buying lottery tickets. So we're going to stick with that example why we code this just just to make it easier for you. So the person with the name head is trying to buy a lot of particular 30. He is currently at the start of the Cube. Okay, so let's ah, create another imaginary person will call a Chloe. We'll initialize that element. And Chloe's trying to buy a lottery ticket Number 97 now. Currently, she is not waiting in our Q yet, so we now need to add her to the Cube. So just do n Q. And we're gonna pass in, um, em person head here on an percent. Chloe here. So what? The ANC you'll do. It'll add R Q element to our Cube. The first argument here will be the Q element you want it stand behind on the second argument here will be the element you want to add to the Cube. So in this scenario, we're saying Khloe should wait behind head. So that's now implement. Thank you function cause we haven't done that yet, so just go void and q obstruct que elements on this will be the element that we want to stand behind again. Eso We're gonna call it standing because he's already standing in the queue, right? And then we're gonna go struck que element element. So we wanna make the elements stand behind the person that's already standing, So follow what I do. So the first thing we do is we need to check to see if the person standing already has someone standing behind him. So the check for this just go. If standing right, there's no equal, no, that means that someone's waiting. Right? So then we need to go standing. No, we need to go element, right? He was standing right. Okay. And that's what you need to do here. Now, the reason we need to do this is because we're about to change the standings, right? Variable 2.2 us to point to us the element. Now, that's all well and good. But we could actually break the queue. If we don't do this, check here. So if someone is already standing behind him, then we need to change that person. So they stand behind us. Because down here, we're now going to say standing right equals element, which will make us stand next to the person that's already standing. So in a way, our thank you function here does allow people to push in. You're allowed to push in behind anybody in the queue that you like, And I wanted to demonstrate it this way to really give you a fully understanding of how the cues work. Okay, that's all well and good. Now let's copy and paste these three lines here. We're gonna pace those on. We're going to call it Jack. Okay, Now, Jack wants to buy lottery number 27 now. Currently here. Change this to Jack. So this will put Jack just before the head. OK, But you know, Jack doesn't want to push in line. So we put Chloe here instead. So this all put Jack behind Khloe. So Jack will be waiting in line behind behind Khloe. Okay. To buy his lottery ticket. So we're now going to implement the de que function which will pull the guy from the front of the queue to serve him. You know, if you're the shopkeeper, you want to serve from the front of the queue. Right? So what we do is we go struck Que element de que Andi in here? We're gonna expect our cue to be passed to us. Okay, so now I just wanted to go struck que elements front or first, whatever you like and we're going to go equals Q first. So when someone passes the queue here, it will get the first element in the Q and set our local front variable to be equal to it. So what we now need to do is we now need to change the queues first variable because it's no longer going to be first because we're actually taking the first element. Arup the queue now. So to do that, all you do is you go, Q first equals front, right? You see how that works? So what this will do? It will get the first element here. It'll story in our local front variable and it will change the first element the queue to the person to the right of us. Now, if there's no one to the right of us, then that will become no So in the queues, first variable will become no right. So what we now need to do down here? We need to say return front on that. Is it Dick? You should work now. Let's just do some quick safety checks here. If people call Dick you too much, then the front element will become no right because here we go. Q first equals front. Right now, Front Ray is no than the first element becomes know as well. So let's just do a check. You we say if front and make sure you have an explanation mark here. So if front is no, that's what this means. Then return front. All this could be returned. No. Whatever you prefer, right. Um or you could even do it as if front que first equals front. Right? Both of those situations would work. Personally, I prefer the return one, the one that I just showed you. So just a brief overview. We get the first element from the queue. If it is not know, then we set the next first element to the person to the right of the element we just got. And then we were. And then we return the element we just got okay, so I hope that makes sense. So to use de que all you have to do is go strapped que element. And this is appointed, by the way, we're gonna call this current, and we're just gonna go equals D Q and we pass in are cute. You can now go print f lottery number Sen Tai back session current Violet, If you know, compile that with GCC main dot c Dachau main and you run main. You will see lottery number 30. Why do we see lottery number 30? Because their first in line if you know, copy and paste this so that it says current equals D Q. And it does that again. But without Redick lair ing the actual variable again and you and you then re compile that type main. You now see lottery number 30 Lottery number 97. Why? Because on the second call, 97 was in the front of the queue. If you now do it again and you compile that run, that you'll now see 30 97 27. Because the reason you see 27 at the end because it's at the end of the queue now, using our thank you. We could cheat here and place it in front ahead. So let's just do that and see what happens. We're gonna put Jack in front of, uh, we're gonna about Jack just behind the head. Right? We compile up. Now, you see 30 27 97 so you can see that are thank you. Function allows people to push in front of the queue, which I wanted to do just to make sure that you knew how the Q functionality worked. Um, so now we're not playing by the rules where we're essentially putting ourselves behind the head, forcing Chloe to be at the end of the queue even though she was there first. Jack's pushed in front of Chloe. So that is accused for you. I hope that makes sense. So one other thing I wanted to quickly note you'll notice here we don't use our left variable. We haven't had to use it in this example. The reason I put it there is because you could use it if you wanted to. However, there's no point over complicating this 13. Understanding Binary Trees: welcome. I'm now going to explain what binary trees are. Binary trees are essentially a structure that I like double linked lists. They're made up of notes. Each node represents a part of the tree, just like with a linked list. How each element makes up a part of a list. Nodes can contain data such as a number much in the same way a linked list element can contain a value notes have Point is to the left note on the right node on the tree, similarly toe how linked lists on doubling lists have pointers to the next and previous elements. The root node is the top note of the tree. It's left and right nodes point to its Children. The Children of those nodes point to Trojan of their own. This happens until the end of the tree, where the nodes point to nowhere when the notes have no Children, their cold leaves. So this is a visualization of a binary tree. You can see we have our root note here that has a value of 50. The roots a left note, um defined by a here. I've labeled it a So it's easy to read. Has a value of 20. The roots, Right? Note on before I continue because A has no left or right node. It is a leaf because it has no Children. Right? So now, now let's go to the roots. Right. Note on the roots. Right? Note. You can see value 60. Now this node I represented by the label be just to make it clear. Now bees left is C, which, which has a value 35 He's right, is DE, which has a value of 91. B itself has a value 60 right? So you can see that the root points to nodes those nodes. 0.2 nodes Those nodes 0.2 nodes until you have lease that have nodes that point to nowhere . And that is how by Neary tree works. 14. Programming Binary Trees: Hello and welcome. We're now going to create binary trees in C, so make sure your program looks like this on. Then on pause the video. Okay, let's begin. First created structure. We're going to call this a, um, note. Okay, Now, your node should have a left note on the right note and finally of our value, and we're just gonna have an inch of your value for this note. We're now going to create an initialization function that initialize is these notes, and it's going to pass in. It's gonna expect a note to be passed to it. And all it's going to do is set the left. And though the right to know on the value to zero now, in your main function, let's just go struck note on. We're gonna call this route, so the root notes value will be 50. Okay. And now, above that, I just want you to go struck note. Child left child left. Underscored child. Okay. On also by here, remember the coal in it? Note here is Well, guys. Okay, now here we dio innit? Note again. Oh, unless should be an route. My mistake. Here We do, innit Note again. On we pass in the left child on the left child's value will be 30 right? So I'm just gonna go over this correctly because I've gone a bit fast, So I'm gonna go trace trace back for you guys. So here we create a left child note which isn't actually on the tree yet it stands alone. It is a leaf. Now here we create a root note. Okay? The root note also stands alone. So it's a leaf now less so. We wanted the left child Teoh be on the left branch of our route. Will to do that, you just go root dot left equals and percent left, child. So Empson left Charles the address of the address of left trial left child. So now our route could be seeing as something like this. We get a paint. So he is our route in here. We have 50. Okay, because that's the value. The root note. And then the left notes here is 30 and that's our left child variable. So this is how it can be visually represented. What we've done here, the roots left node is the left child on the left child's values 30 right? So the left child is 30 on the route. Value is 50. So the left child values 30. The root values 50 right? The roots left is our left child, which has value 30. The route right is no meaning it doesn't have a right child. Okay, let's now create a right child. So to do that, just go struck note, right, child, innit? Note and percent, right, child. Right, child. Dark vow equals 2029 28. Whatever you want it to be now currently are right. Child is not actually on our tree because we haven't set the roots rights. Now, the reason I haven't said that is because I want to make the right child also have a child of the sun. So let's do that now. We just go struck note. Right. Left, child. So this is the left child of the right note in a note percent. Right? Left child. Right. Left child. Doc, Val equals, let's say I don't know, 22. Okay. So, again, both of these aren't on the tree right now. Now I want you to copy, right? Child here, pasted under here. Okay, Because we're gonna reference right, Left child now. And I just wanted to do right child dot Left equals ampersand. Right, Left child. Simple as that. And now down here, Go route That right equals ampersand. Right, child? Okay, so lesser. Go over this. We create a left child that is not on the tree yet. A right left child, which is not on the tree yet on the right child, which is not in the tree yet. Now, when we create our right child, we assigned the left to hold the right left child. Right. So just to demonstrate this, if I can get up another paint that I'm going to select this at this point in time, Okay. May just select all at that point in time See what I've selected there at that point in time, The tree looks like this, right? We have our left child, which has 30 Andi. It is also on its own, by the way, completely on its own. Right. And then we have our, um right child, which has a value off 29. Okay. And then we also have our right left child. Noticed? I'm saying right, left, child. I'm referring to the variable names here on our right left child has a value 22. So that's how the tree looks currently because we haven't finished joining it. Right? So the left Charles on his own here. It's basically its own route. It's not on the tree. Ah, all right, Charles, also on his own. But we've assigned the left node of it to our right left child variable, which has value 22. So now the final piece of the puzzle is to put them all together by creating route. Right. When we create roots, we get 50 on its own, right? But then down here, we assigned left and right to the left child in the right child. So if we now copy and paste this So we assigned the left child, which is this So that goes there. So the left cholla route is now set, and then we set the right child, um, off the, um, root element. So then let's just move this a little bit. There's a bit of room. So then what happens is we have something like that. I know that didn't render. Probably, but I hope that makes it clear. So then are right no Divi route has 29 on the left, noted. That has 22. So that's how it works, Guys, we just literally upend these pointers as we go along on the tree, naturally comes together.