Real World Interviews Qs: How to Implement Linked List?

hey hey what is going on guys welcome back to another exciting episode on the channel I hope you guys are having a fantastic date in today's lesson I would like to discuss the topic of something called a linked list and this topic is actually pretty popular in the study of computer science and in fact if you're trying to get an internship or a full-time development job it's highly probable that you'll be asked a interview question related to how to implement a linked list and so in today's video we're gonna talk about how to actually implement one and you know what goes inside the implementation but before we get into the nitty-gritty code we would like to go over a simple example of why and when you would like to use a linked list right and so I'm gonna start with the simulator on the left side here and you can see we have the brand new tinder course where we can swipe our images off the top of our stack right so we have a lot of cards and we have cars behind cards like so and so for a linked list what you have is a head object which points to the first item inside of your list and so you can treat the top of your stack right here as your first item and this item is going to have a next pointer and that points to the next item in your list which is this card back here so we have Nancy and I'm going to swipe her right and then you have the next card which is Kelly she's 25 and she's a singer and so when you're on Kelly right you're going to try to find the next card in your stack so you can maybe perform the animation like that and then if you swipe her off you're going to get to Lisa which is the next pointer for the previous card of Kelly and so what you have is a linked list with all the nodes pointing to the next object in your list and you can keep swiping and swiping and swiping and what happens is at the very end of your list you have a nil pointer or the next object points to mil which means that you've reached the end of your list all right so this is a very common use case for you know something like a linked list and hopefully you kind of get the idea of how it works what I would like to do now is to go into a graphic here so let me drag this in and I drag myself through the bottom right - you string me down a little bit so you can see the image and so let's say that we have another situation where we want to use a linked list for something like Michael Jackson's best hits and let's say this is a list of audio songs or audio tracks and for your linked list you have your head which is this node right here and this note has a value of something called Billy gene which is Michael's Jackson's best hits at the top of the list and then for the next node we're going to point to the next object inside of the best sits which is the value of throwing another very popular song by Michael Jackson and then thriller will point to the next song which is beat it and then finally the next pointer it goes down to nothing which is just nil which means that you've reached the end of the list and so hopefully these two brief examples help illustrate what exactly you can use a linked list for what I want to move onto now is to actually implementing a linked list and we're going to insert some values inside of a list using a node and also delete values as well and so let's go ahead and jump into an Xcode playground and do some coding right now all right guys welcome to Xcode playgrounds which is what you're seeing on the left side of your screen or right over here hopefully you're ready to kind of get your hands a little bit dirty with some code today in this coding session I want to show you exactly how to create a class called a linked list and then we'll move on to discussing how to insert values into our list as well as delete and if we have enough time we'll talk about a special type of insert at the very end of today's video all right so I'm going to try to do my best job here to explain a linked list and you know why you would use one as opposed to something like in a rain I don't guarantee that I'll do a good job but I'll try my best all right so why don't we start by creating our class called a linked list we are going to define it using the class type instead of a struct because struct inside of swift is really confusing and it makes this example really hard to follow so let's just use a class for today's video and for our link list we are going to declare one simple property inside of this game we're going to save our and the head of our linked list represents the very first object in our list and I'm going to declare it as a node optional type if our head is nil that means we have a completely empty list okay so on the right side we have this error now that says use of undeclared type node what exactly does this mean well we don't have this no class defined so I'm gonna move on to the top section here and let's go ahead and say class node and let's see what goes inside of here well the node is going to represent one of these guys so we have a value and we have a next pointer our value I'm going to declare my value as an integer type just and make today's example a little bit easier to follow so let's say let's value and let it be a type int just like that and then we also have to declare this next pointer guy that points to another node object and at their very end it can possibly be nil which means that we need to use an optional this little bit of syntax will look like this here so I'm going to declare at the next pointer as next and let it also be of type node optional alright so that was pretty good if you hit the left little play button everything looks like it's compiling okay and you have this error down here that says that you don't have an initializer for this node class and if you're using a struct you get your initializers for free but it's a little bit different for classes you just want to say and knit and declare your custom constructor little syntax here at the parameter we're going to use value and let it be of type int I'm going to make a second parameter here and let it be of type optional node and during the initialization you want to set the self dot value which refers to your instance property to the incoming value which is just that hopefully you guys are familiar with this index by now we'll do the same thing for the next and just set that guy you it's the next like so alright the syntax is there looks almost perfect running we don't get any errors that means everything is looking a-ok let's now move on to actually using our linked list somehow what you would like to do is to say let you know sample list equals linked lists like that constructed using an empty constructor and now you have a very very dumb linked list you can say sample list dot head you can print this object out I don't think you'll get anything but a nil down here and you know that's exactly what we have okay so right now this is a pretty useless list right why don't we actually insert some objects inside of our linked list somehow and so we really have to declare some kind of function like insert and then actually implement this thing but if you're not familiar with how a linked list works it's actually easier to create a sample function so I'm going to say set up dummy nodes and I'll set up my linked list using some dummy nodes inside this function just so that you can kind of see what's going on a little bit better I'm going to declare my head and so let the head it be the very first item in my list and I'm going to declare it as a node it has that constructor that you declared right over here on line 9 and so let's say I want to create the list of one two three right so let's say I wants to say one and then two and then three and then at the very end is going to be point two nil just to represent the last object which is nothing all right so what we have to do is say the head is going to be one and then the next node has to be this two node here so I'm going to declare two equals node and value of two and then the next node has to point to these three and what we'll do is the same thing pretty much up here node and the value of three the next is going to be nil because the next is just nothing okay so what I'm going to do now is to move on to popping this three into that so let's get that highlighted double-click the two and put that inside of there okay if I try to run now let's see a run we'll still get the nil and right now what I'll do is I'll say a sample is dot set up dummy knowns and if I try to run this now and you should be able to get the value of optional one so let's say head dot value instead and then we'll get optional one if you say a head dot next dot value you should get the optional two and then if you keep doing this by appending the next note to it you'll get a three and then you'll get nil okay so you know you can keep typing this out to figure out what exactly is inside of your list but what you typically have to do inside of an interview room is to implement a function called display list so let's say function and display list items and this guy will say printout here is what's inside of your list and colon and the quote and so down here you would like to print out the entire list in sequential order starting from the head node I think is a pretty good idea and so instead of using this print statement I'm going to just comment that out and so hopefully you guys can see what's going on down here what I'm going to do is to say sample list dot display list items and try to hit the play you'll get this being printed out which means that this function is now being called correctly and moving on here we would like to print out everything is starting from the head node and so what you can do is you can declare some kind of while loop and then have a condition and then perform some code inside of this loop here and I'm going to just type out the code because it's really hard to explain what the logic is without you know having the code in front of you what we're going to do is to declare this current variable here to equal the head object and then what I'm gonna do inside of this while loop is to perform the condition check current not equal to nil and then during the looping I'm just going to say current equals current dot next okay so this guy right here is just going to set the current node to the very first object in your list and as you are executing the iterations of this while loop you're simply saying the current node to the next node which means that you're going to start at one advance on datato you're going to execute another iteration and then you're going to get to three finally advancing to the Anil note at the very end and then once you get there this check will no longer be true hence exiting outside of your loop okay so hopefully that logic is clear you might have to go through this in your head you know no pun intended inside of your brain a couple of times to fully understand it and so what you are going to do inside of this while loop to print out your display is to simply say print out let's see we're going to say current dot value which is your node values of current is your known so this is your node up here and then you can simply say dot value you can get rid of that little warning there by just using the nil coalescing of two question marks on this optional object here and then what you'll get is if you run this all the way at the very bottom you'll get that the items inside of your list is just 1 2 & 3 right so that's exactly how the print statement works for this while loop hopefully this makes sense make sure to go through it a couple of times by yourself to fully see what exactly is going on okay so now that we have the ability to print out our list it's going to make our lives a lot easier in terms of implementing the insertion and then the deletion next so let's move on to inserting some values inside of our linked lists without having to you know call this set up dummy nodes dummy function and what I mean is I'm going to declare a function here called insert and it's going to take in a parameter of value and it's going to be of type like so we're just going to insert some value and let's say we want to build up this list of 1 2 3 and you know perhaps 4 and 5 what we would like to do is well you want to say sample list dot insert value like that and just pop in the 1 and then whenever we actually call this we want to make sure that sample list display items should print out the value of 1 and so what I'm going to do inside of this insert here maybe I'll get rid of this dummy 1 that we declared earlier I'm going to say let's see if head if this guy is equal to nil that means we are in the case of the empty list so it's always good to check if we are the empty list if this is the case we're simply going to declare the head equal to a brand new note and the value is going to be that one value that we inserted which is the value parameter from the method call and let's just hit that and the next note is nil because you know we don't have any additional items so that's all we get for the insert and once we run this now you'll see that we have the display and list items function prints out the value of 1 all right now that we have our 1 inside of our list we won't like to get the value of 2 in there as well if you run and now you'll see that you'll still get just the value of 1 because we're only handling the case for an empty list up above instead of our insertion we would like to you know handle the case of in inserting additional items like a 2 or a 3 and so on so forth and so how exactly do you do this right well this is also maybe a little bit tricky and sometimes when I have to do this I actually forget the implementation and so we're going to declare a current object just like what we did before up here we're going to declare it as the head object again all right so the idea here is I'm going to advance to the next node continuously using another while loop so I'm going to say while like that and was it while current next not equal to nil and then Emily's a current and let's say current equals current dot next hopefully I have this correct and by the end of this while loop here we're going to advance to the last node inside of our list so what I mean is at the very end right here end of your function you can simply say current dot next equals something and I see I have one little mistake and I'm gonna go back to the case of the empty list and use a return right here and this means that if we're the you know empty list will create our head and just completely exit outside of the function using this return statement and so all the way down here I know that I'm at the very end of my list through the logic of this loop which I might explain in just a little moment here on Wednesday current down x equals known and then I'll insert the value from the function of here and then let's just use the next of nil and this is going to help us insert the one in the case of empty lists and then when we call insert again with the value of two we're going to come down here and now we're going to insert the item correctly and I'm going to pray that I've done this correctly and so what we have now is we have the list of one and two and let's try to insert the value of three as well and run again we will now have one two and three okay so that's kind of how the insertion works and let me try to go through what exactly this logic is doing first we insert our one value which comes up here and then after that we insert the two right which means that current equals head means that we are at the note of one and then current dot next for the node of one which is down here is going to point to a nil object because right after here we are pretty much 1 and nil and so what that means is we actually never execute this while loop and current is going to equal to the head of one and then we just simply say you know 1 dot next is the next node which is two so we get one two and so basically this will turn into one points to two and points to nil and then you have the you know very similar effective inserting three right below there and then finally you can you know display your list items you get one two and three and so luckily I was able to perform the actual implementation correctly sometimes I do get this wrong but you know it's pretty easy to check what's wrong with your code if you know what's going on and you know that's the insertion and typically what you'll be asked next is to delete an item instead of your linked list right so we've gotten the insertion done now we won't like to say how do we delete a certain value like let's say three or two or maybe even the one and so what I mean is when I make a function call let's go let's see insert is there let's now go so this is usually the second question or maybe the third question delete and let's say a function deletes and will delete a value and and we'll just close it off like that okay so what is gonna go on with the delete well we're going to say sample list delete a value and let's say we delete the value of two right this shouldn't give us a list of one and then we can get to the three and then we'll get to the nil because we've removed the object of two and so lets us assume that we don't have any repetition instead of our list you know that'll make this example a bit easier to follow and the question is how do we implement the deletion inside of this code here so this one is the actual tricky one and we will go inside of here and so let me now show you how to implement the delete function right over here now the first thing I'll do is to check if the head right here if this value is equal to the value that I want to delete so I'm just going to specify that if this is true then I'm just going to simply say head equals head dot next and so let's try to figure out what this is doing here by trying to delete the value of 1 and so on doing the value of 1 from my list of 1 2 3 we're going to run into this because head dot value is 1 which equals the 1 and then we're going to make the head of our list point to the head necks which is going to return us a list of 2 3 and nil and so let's try to see if that is actually true by removing this and so we have insert 1 2 3 delete 1 and hit the play over here we'll get 2 & 3 because we've deleted the object of 1 ok so hopefully that's pretty straightforward the next part inside of this delete function is the harder ones to actually understand and why don't I type in the code you can try to do this on your own first and see if you can come close I'm going to declare two nodes now in addition to this previous variable I'm going to declare a second one called current right below it and I'm going to set this guy equal to the head node like that alright so what I'm going to do inside of this little while loop that I'm going to declare a right below is a couple of different things I'm going to say while current is not equal to nil and then I'm going to specify a second condition inside of here so there's some condition check that I have to implement inside of my while I'll simply say current equals let's see current dot next and I believe the other line is going to be something like previous equal to the current like that and so the other question is what exactly goes inside these question marks and why exactly am i declaring this previous thing in the first place well let's try to run through this example one more time with the deletion of 2 so I'm going to say it deletes and why don't I just delete the value from our list of 1 2 3 and so with the elipse kind of like this right here I want to know when I encounter the value of 2 I have to make sure that the previous note of 1 is going to point to the value of 3 that's the kind of logic that has to follow in order to make sure that the deletion is done incorrectly and so that's why I'm defining this previous note on line 48 hopefully that makes sense and during this loop right here what I'm doing is I'm advancing the current node using current next and then the previous right here this variable will capture the previous node by saying previous equals the current you do have to go through this a couple of times in your own brain to fully understand what's going on now the last thing I'll do is I'll perform one final check right here which hopefully I'll be able to do correctly and I'm going to check if the current node dot value if this guy is equal to the value that I'm going to delete right here I might be able to do this correctly soon let me try to set then and maybe that's correct it might be not equal but I'm just going to let that guy be that I think it's not equal that makes more sense to me right now and so after I'm done it rains through this loop I'm pretty much guaranteed that previous will be the one and then current will hopefully be the value of 2 because the deletion value of 2 will mean that I want to exit out of this because current value is 2 so what I can actually do here is I can say previous which is the one in the case of dealing to you I can say next equals the current dot next like that and I think I'm good this looks okay to me I'm just checking off-screen to verify that the code is indeed correct so Wow yeah this looks a little bit confusing right but we're going to run the example right below here by deleting the two and let's see hit the run we deleted the two out of our list and we did this let's see if we can still delete the ones and delete one we get to three let's see if we say delete three we get one two and so now it's pretty good if we say samples the sample list dot deletes why don't we delete the one first and then delete the three we should have a value of two finally if we say it's out delete evalue - we should have an empty list and this should not crash which is looking pretty good everything is running correctly okay so that is the deletion if you want to make sure you understand this code do this a couple of times in your head to kind of print out what exactly is happening with your previous and current nodes okay so that was definitely a mouthful and let's kind of go over the last little item in our itinerary on the very top here so whenever you are inside of an interview room they're going to ask you I think about like two or three questions and if you get through the couple of first softball questions of let's see we have display list items you have to make sure you understand how to print out all the lists items inside of your linked list this is the easiest one if you're not able to get this and this pretty good chance that you're not gonna get the job the second little exercise is to make sure you can insert objects into your list so make sure to understand this this delete one is a little bit hard but hopefully you should be able to implement this one correctly and and then the final one is sort of the bonus kicker here the special insert which there's a pretty good chance they'll ask you this question to really test your understanding of a linked list and so this is the special insert and I'll tell you exactly what it is right now and let's see I'm going to say function insert in order and let's say value is that and you know this guy will be integer as well and so the point of insert in order is to make sure that you insert everything while you're checking the order of the items inside of your list so for example if you have one C one two and yeah four and you have five and this points to nil if you insert the value of three inside of this list here you have to make sure that you have one two three four and five okay so that's not an insert in the order it works you make sure that you're checking the order of the insertion so that your list is still kind of sorted correctly and you know this might be called sort insertion if you want to rephrase it and so this one is actually a little bit harder to implement and I checked this a couple of times on the internet for the actual solution I don't think I want to go over exactly how that is done so what I'll do is you know perform a little good ol copy and pasting sheet and this is the answer that you wants to implement for insertion in order ok so now that I have that you know function and this mysterious answer declared inside of my linked list what I can do is to comment the deletes I'm going to insert 1 2 4 & 5 so sample list and let's insert the value of 5 and then at the very end here I wants to say sample list dot insert in order and popping the value of 3 and hopefully this works out for me we're going to get the insertion of 1 2 at the top here we get 2 4 & 5 and then we have the insert in order of 3 so if I print out this guy display list items and try to run this you'll get a better picture of what's going on we have 1 2 3 or a 1 2 4 5 with these four objects and then the second insertion will pop in the 3 right between the 2 and the 4 and that's kind of what we have for the implementation of a linked list object make sure that you actually understand how to do this before you go into the interview room now one last thing that I would like to mention about a linked list is why exactly do we want to use a linked list in the first place instead of just a very simple object like an array right so let's say we have an array of objects of 1 2 3 & 4 and that's just a sample or rate and what happens if you want to insert something like the integer of 5 inside of this array right you would probably call the function called a pen and just pop in a value of 5 and this turns our array and see 1 2 3 4 and 5 and you probably don't notice what's happening if you've never studied computer science what happens is the array right here actually needs to resize itself so that you can add this extra element of five at the very end there and that's actually pretty resource intensive if you have a linked list all you have to do is to make sure that you're at the end of your linked list and you just append a new node onto it and the amount of work that that's required of your computer is actually relatively small compared to the array insertion there are a lot of other reasons why you would want to use a linked list but maybe we'll leave that for a later video all right everybody that's gonna wrap it up for today's lesson hopefully enjoyed it make sure to let me know your thoughts and comments down in the section below if you want to download the source code for today's playgrounds you can find the link in the description below as well if you want to learn more about iOS development as well as just Swift coding in general make sure to check out the couple of courses at using the links down below such as the tendrá course over here as well as the couple of other courses that's gonna be here for today I will see you in the very next video bye guys

Channel: Lets Build That App

Views: 15,389

Keywords: ios, swift, development, tutorial, learn, xcode, programming, code

Id: oLXRe7JWJ5g

Length: 29min 54sec (1794 seconds)

Published: Sat Nov 03 2018