Node-Based Data Structures in C / C++

ladies and gentlemen not too long ago on the channel we took a look at note based data structures in Java we saw how we could use object-oriented programming to well firstly build a node and we could use this note to link out rights to other notes to form data structures like the linked lists the trees and things like that today we're gonna go through a similar journey but this time using C and C++ the reason why we are doing this is because C and C++ have well pretty interesting ways of manipulating memory that allow us to see the actual mechanics of say a linked list in action all this and more in today's random Wednesday episode hello and welcome back to another random Wednesday episode so today we're gonna start off with the C version first using structs and pointers and we're gonna basically build our way up we're gonna see some issues in the C version we're gonna fix it using C++ and see what the difference is ah before finally moving on a get to a generic solution now unfortunately for this I do require you to have a little bit of prerequisites about how C works but the good news is well I've talked about all those things firstly you need to understand memory management in C that is well the whole point of using pointers for example so well with that a video on that will be using things like malloc your memory allocation we've talked about in venice well we'll also need to understand trucks which is the episode of Friday minis that just came out last week so yeah that's quite a few pieces of information you need if you need to go check out those videos right there'll be a card somewhere up on the screen I don't even know if I'm pointing to the right side here but yeah go check out those videos if you need to then come back here right we're gonna start to apply the knowledge from all those videos into building a note structure and from that I've linked lists so with that let's forget and let's start by building the simplest thing which is our note structure he said you youngling liz is essential for a bunch of notes pointing to each other right so while we're building first is our note which holds a value as well as a pointer to our next item we need to be able to find the next thing so we can essentially chain our way a lot we've see it's did simple really all you need is a structure that is a note it contains the data as well as a pointer to another note structure that's it the code looks something like this and yeah basically what you can do is you can chain along a few of these items as you can see I've created three items starting from the last one the third item points to nothing but the second item points to the third and the first item points to the second this is essentially a very simple Ling list since the items are linked to each other I can simply request for the next of an item to move forward so asking for the next of the first item just meet a second asking for the next of the second item gets me the third that's the idea what are you just dynast we've just built our node and then manually linked our notes together and that's great however two shortcomings come to mind immediately firstly we are just building our notes as variables so they live only within our main function clearly the more dynamic way would be to use malloc so though our notes actually hang around second right now we are directly manipulating our node connections and while that's fine providing an additional level of abstraction in other words actually building a linked list data structure will make it easier for us to manipulate the contents of that list so well let's build a full fledge Ling list data structure and we'll see how things work now in the case of C we can't only build them as functions and call them so well let's do that now before I enter into the actual explanation of a Ling lists do note that we have talked about Ling list multiple times right we did this the last time we looked at no base data structures so as usual I'm not gonna go into too much detail now what I'm gonna do is I'm gonna switch into my court page here right essentially these out of main things we're gonna cover we will briefly touch upon the theory s and when we need to about I'll try to keep playing shot firstly before we jump into the linked list stuff do take note of course of our set up of course we need to have our node struct right and since this is C we have no other way of keeping track of the head of our linked lists except by using a global variable like this well there are ways but to keep things simple we'll just do it this way right now we're gonna implement everything else it's just a function within the page itself and we'll have a main function right to set things up and to drive everything so that's what's going to happen in a nutshell let us now take a look at the actual logic for this let's start with a fine all gets function now in my code I call this get but the idea is if you're gonna find you know a particular element here's how you do it essentially you're gonna have to create a current pointer and it is going to have to move its way through the list starting from the head to find the item you want let's say I'm looking for item number two how I'm gonna have to do this is I'm gonna have to put current and he hit maintain account which is set to zero and then run a loop each time if the count is not yet correct the current is updated to the next of the current node and essentially what happens is this pointer moves forward like so of course we don't just move it forward we'll also have to update D counts as we go along so the idea is we keep doing this until we end up at the elements we are looking for let's take a look at a code for this part essentially the code looks something like this very simple we create our current right this is a pointer of type node and it starts off at the head now head is also a pointer so we simply well copy the points at Valley we have a follow-up here which does the counting for us right our counts is represented here as the value I and the idea is the user will supply a position you'll keep counting forwards until you hit that position and all you do moving forward is you simply update current current points at a note right now go to that note find its next item and set that onto current when you do that current moves forward that's it now let's move on to insertion let's say you wanted to insert a new item over here right between these two nodes our approach would be to well use our gets function right find our way to the slots before right so this is the previous item the one right before where we will actually want to perform our insertion and in order to actually find this we'll have to well get the actual position we want to go to minus one right you'll see that in the code later basically you've got to find a note that will come right before this new item what are you gonna do to it then if you're gonna have to find out what is its next item because now that will be the next item of our new node like so so the new node must point to it once we have that reference our previous item simply points towards the new item as you can see this essentially sort of flattens out to the correct structure right with the correct order again let's see this in our code of course we need to take in two values right not just the position but also the value we want to actually stop we'll create our new notes by performing a malloc operation where actually allocating memory here and that memory is the size of a single node we then want to populate the two values right we'll put in the actual value that the user once and we'll set the next pointer to nothing for now they're actually two cases for insertion one of which we didn't go through just now and that is if the node is going to go to the head of the linked list we simply update the hit and the next item that a new node has to point that would just be the current hit otherwise if it's not at a hit then we'll do the same algorithm we've just looked at go to the previous item see we had to get position minus one because that is the we yes right so we get that item and the idea is the new note must point to the item that comes after meanwhile the previous item must point a new note right these two manipulations and you get a new item in place then we have deletion which works again on a very similar principle you have to find the previous item once again and the idea is you have to find the item that comes after the item you want to delete once you have that it's simply a matter of taking the previous item and pointing it to that item the idea is that the item you want to delete now becomes out of reach going back to our code here is how we would do it try to give it the position if it is the first item well we simply point ahead to the item that comes after the current hit in this case since we're dealing with memory with a locates at ourselves we have to be very careful to not lose track of that piece of memory we free now while we have the ability to find it we can't free this later because we have no way of getting ourselves to that node so this is very important if you don't do this right you get a memory leak and that would be a problem this is the case of the head if you're not deleting the head you want to again find your way down to the previous find item you want to delete right which comes after the previous the idea is again the previous item will point to the item that comes after what you want to delete similarly you must free up the memory now speaking of freeing up memory we do actually need to do one extra thing that we didn't have to do in a Java version which is to properly free up everything when you're done using your linked list well since you've allocated that memory it's your responsibility to get rid of it so we essentially traverse through the entire list once visit every elements and free it up do note that I am using quite a roundabout approach to do that here and a reason is because well you have to be careful not to delete a node until you found a node that comes after that means you must be able to call current arrow next to find the next item before you actually free up the actual note itself that's why I have created a previous here right and the idea is that I still have some way of finding my item even after I've moved forwards so I can free it up for convenience sake I also have a display function right all it shows me is the address and the value of each item while traversing through the entire list so now we can come down to our main function right the idea is I start off initializing the head to nothing inserting a couple of items and then taking a look after that I'll try my division and take a look at it before properly clearing out the entire list as you can see the results are as you would expect the first four insertions insert one two three and four at the back of the list while five and six coming friends so well our first set of results are you know correct right and then after this we delete first the hit and an item in the middle and that leaves us with four items still in the same order and they go that will be y'all you know most basic note based data structure in the C programming language no we have one mini tiny load drawback here and that is the fact that well these are just functions that are lying around but what if we wanted to consolidate these things together to have a nice single unit of computation that we could work with well let's use classes and in order to use classes we're gonna have to switch programming languages C doesn't do classes C++ deaths so let's give that a try firstly before we go into classes we're gonna just part our entire code to C++ no while C and C++ are very similar in this case we're playing around with memory and as it turns out some things look a little bit different when we do that so first let's explore the differences before we actually step up our code what we have here are the two pieces of code side-by-side the C code is on the left the C++ code on right and as you'll see the differences are subtle I've tried to line up these two pieces of code as perfectly as I can but yeah let's take a look at a main differences you'll see one right here of the insert statements which are highlights on both sides now in C we would use malloc to allocate memory in C++ instead of saying malloc we would say new that she has a subtle difference between each one of these languages now malloc still works in C++ but it's no longer the official way new is now an actual keyword within the language itself and well that means that's the better way of doing things in addition this one is a little bit more subtle but in C++ the way you construct a strut is a slightly difference from how you do it in C essentially your struts becomes a function all to get a little bit ahead of ourselves it kind of acts like a class so just note that you know there is a slight difference in terms of how you actually do new items at the end of the day however the way we use this is exactly the same we get a pointer to it and we can start assigning values to it let's move down a little on both these pieces of code and we'll see another difference just like with malloc we no longer say free now we say delete so yeah again we're making use of new vocabulary given by C++ also note that because this is called delete I can no longer call the function name delete as well right there will be some kind of a conflict then so instead I've renamed this to delete No this of course applies throughout any function that you know does freeing up of memory we now call delete instead of free as well and the destroy function another thing I did instead of using printf right which is what we have to do as a standard for C I can now just say C out of course printf still works just fine but well since we're moving to C++ let's just move everything accordingly so yeah apart from the preprocessor statements at the you know very top of the piece of code those are the changes right we are still doing Struck's at the present moment and yeah from C to C++ we get the exact same set of results that means our parting operation has been successful now that we have these things out of the way we can start to convert our code you know from structs and functions which are separate things to a single class which brings everything together let's see how things change when we do that now right off the bat we've changed two things in the classes we have a node class as well as a linked list class now for the most part at least under the linked list class things look the same the note class seems a lot more complex you know in comparison to a struct counterpart but it really isn't this is what we have in common with the struct ultimately your node must hold these two pieces of information right so that's never going to change however we now have a bunch of other things write this as well as the private flag the idea is that you know these private attributes cannot be changed directly from outside this class that's all so we need to add these functions to allow these values to be manipulated this is actually what we call getters and setters also known as accessors and mutators right so the idea is that we have functions like these to get either the points of value or the value within the node itself and these are there for you to actually change those values so this allows you to set the pointer to the next item this allows you to set the value finally our last function here is called the constructor now for the first time what we can do is we can run a function and that gives you back a node that constructs the node to use the oil in terminology you don't have to create a constructor C++ knows how to construct things by default however if you want it to do something special during a construction process this is where you specify it and what we are doing now is we are taking this opportunity to initialize the values when the user creates a note they'll have to give us the value and that is the value that is being stored inside our node at the same time the next pointer is automatically set to nothing so yeah with this constructor what happens is we know exactly what's inside the node from the moment it is created and that is always nice this is our node in a nutshell and once we're done with this we can move on to look at our linked list class like I said most things are the same in this case our hit object is now helped with finding Ling list itself this of course makes sense right every Ling list needs to have its own hit so we can use that to find the rest the contents help with in the linked list the first function we see here is a constructor and all it does is it sets the hit to nothing again it's there for as to well ensure that we have a clear starting state what you'll find is that everything else looks basically exactly the same the only difference is that when we're trying to get information for example we can no longer just you know refer to the value held within the note we have to call the corresponding function this again is the result of having things private within the North class right so again we have to use the getters and setters do well touch the actual values aside from that things are exactly the same our logic is exactly as it is things haven't changed it's just that now we have to again Express things using slightly different vocabulary notice here that in our insert function we are now making use of our fancy new constructor for an old class notice previously we had to add two more lines here to set the value and the next pointer and we no longer have to do that now thanks to the fact that we have a nice constructor doing it for us don't forget we still have the new keyword here and that means memory is being allocated so yeah insert delete right exactly the same as well except we changed things to well make use of the functions instead same deal for display now another thing that's different here is this function notice we've replaced our destroy function with this a destructor if you can construct a class of course and make sense that you can destruct right you can get rid of it when you had done with it that is essentially what this function is for notice how similar to the constructor you may use off the name of the class but instead we write a little tilde sign before it the purpose of a destructor is simply instructions on how to clean up when I'm done using this class and I want to say hey throw this away what logic do I need to go through to make sure that everything is actually being deleted correctly of course that's exactly what we were doing before with the destroy function so well this just comes in handy right turns out there is a nice mechanic for this already in object-oriented programming so we just make use of it with this we have both our classes ready and we can start to use it over here in our main function things are mostly the same now we create the linked list where we construct it based on our class and yeah in the future whatever operations we run we have to run on our linked list object so the name of this linked list is simply ll right and what I can do is I can do my insertion display and all that as usual now notice one subtle change and that is the fact that I no longer have to destroy the linked list I didn't miss this out and then forget this as it turns out C++ actually destroys whatever objects you have creates it for you when your program terminates so that's one less thing you have to worry about C++ can clean up after you and how it does it again is by calling the destructor function so yeah that's one less thing to worry about we now have everything in place and if we run it you'll see that the results are exactly the same this tells you that our link lists the class version is now working as we expect ladies and gentlemen we now have a linked list data structure that is in a class form with this it's now so convenient right because we can have a linked list it can do its thing we can build a different Ling list that with you it's think and yeah both of these are dynamic data structures so it's very very powerful a lot more powerful than your basic array no we just one more problem to address and that is right now our Ling lists only whole integers the way we dealt with this when we first built this in Java was they use Java generics right generics is a way to say that well this type is able to contain an unknown type or a variable type T we can assign the type and while moving forward that data structure works with that type well C++ has something similar as well so well expressing it is an aspir - yes it is in Java though it is quite similar let's see how we can tweak up our code right and then let's test this with a different data structure how you do so-called generics in C++ is by using this thing called a template class the idea is we want to build a class but we haven't decided what type it is just yet so for now we'll call it t and later on when we actually you know construct and objects of this class C++ builds the correct version of the class that supports this template type so here's essentially what we need to do before building our class we have to say that this is a template class and it's gonna work with the type T so you can see that we've basically replaced every instance of integer with T right so essentially this is our node and instead of storing an integer it now starts the type T when you try to get value it takes back the type T when you try to set your setting type T so everything is now with respect to this variable type this makes our node versatile so we can store basically anything we like inside it the same needs to be done for the linked list again we say template class T right and yeah everything in sight now works with T now as you can see over here what happens is we are trying to build a node right so for the first time we are talking about this template class as a user of it but in this case we're simply saying what we're going to use type T right it is the unknown for this class then passing over to that class the note class up there so yeah I think you get the idea right every time we talk about noon we have to be clear that it is a note of type T so yeah whether we are just talking about a type or whether we are trying to instantiate it like we are doing here we have to mention T anytime we mention note we have to basically link it with its correct type everything else works basically the same way when you do insert you are now inserting objects of type T right so same view for deletion right we mentioned T as much as we need to same to you for display same deal for our destructor any time we mentioned note we must mention the type so we can now go down and actually use this in this case instead of using integers I'm gonna be using characters so I tell C++ that I want to stop characters in my linked list and yeah I create mailing lists like so so what happens is this character type is going to bubble its way down into the linked list and you know as a result of that to the nodes as well and what that means now is I can insert characters into my linked list if I switched out the type over here I'll be able to store a different kind of information at the end of the day however how things work it's exactly the same right I'm just storing a different kind of information so yeah there you go what we call generics in Java is what we call templates here in C++ but the idea remains the same we now have a versatile type of linked list that can hold any type of information and there you have it that was well building our node based data structure turning it into a linked list and then from there see how we could first package it as a class and then as a generic class we've basically looked at C and C++ in the same video but most of the contents were fairly similar so I hope that wasn't you know too much of an information overload but yeah there you go right and you can extend the same idea to do a bunch of other things for example you could build a binary tree right and to do that it would basically tweak up your node so that it will well instead of having just one connection one point it would have to a flash can augment this further add another pointer so it can find its way back to its parent if you want what about a general tree I've seen a pretty interesting one in which you could build a general tree with just two notes it's actually you would turn a tree that looks like this to a tree that looks like this every node gives you two things firstly a way to find well it's child note its first channel note as well as a way to find its sibling the next sibling well in that level so it's not the prettiest of ways but at the same time it works it gets the job done right you just have to tweak up your functions so that well abuse of things correctly but anyway that essentially is it for this episode on note based data structures this time in C and C++ hopefully this has been an interesting journey right playing around with pointers and things like that is always fun though as long as you have the right idea of what's going on but yeah that is basically it for this particular episode thank you very much for watching and until next time your cheese 0 6 1 2 TV with nut firstnet's thank you very much for watching if you like my work and are feeling generous you can shoot me a one-time donation on paypal or sign up for a recurring one on patreon of course you can simply like comment and subscribe you know that you for more videos links to my channel and it relates at playlists are on screen thank you for your support

Channel: 0612 TV w/ NERDfirst

Views: 6,705

Rating: 4.8805971 out of 5

Keywords: 0612, 0612 TV, nerdfirst, nerdfirstnet, nerdfirst.net, node, data structure, algorithms, class, C (programming language), C++, programming, coding, university, college, help, tutorial

Id: ADE1zCQs2Fk

Length: 28min 11sec (1691 seconds)

Published: Tue Jun 05 2018