Deep Dive into the Linked List Data Structure

Key Takeaways

one of the tricky things about working with arrays is the fact you must know their size ahead of time this is a problem for scenarios where adding and removing elements happens frequently and a space must be made for the new elements to be added how can you provide a linear form of storage for scenarios like this the answer to this is the usage of linked lists in this video I would discuss the most important aspects about the linked list data cery which variations of it exists and and how can you implement them hi my name is Ricardo fera and I'm a developer advocate here with AWS welcome back to this series about data structures in this episode I will talk about the linked list this is one of the most deceptively simple data struers out there as its implementation may look straightforward but it forms the basis for surprising number of questions during coding interviews this happens because you can Implement a linked list in in about 10 minutes and interviewers want to use the rest of the time for you to solve two or three problems for a 1hour coding interview session this looks as a good usage of your time as interviewers can extract more from you with a single data structur interviewers also love linked list because it allows them to check your knowledge about pointers and references as Link at list heavily relies on them moreover Link at list a conveniently simple way to implement the backend storage of all data struers such as cues stacks and hash tables this means that knowing linked list and intimate details Grant you advantages with these other data structures let's take a look at linked list at a greater level so what is a linked list a linked list is a collection of data elements that are connected together via links each dat element in the collection includes a link to the next element and some variations of the link at Leist data sty may also include a link to the previous element in the chain allowing for efficient insertion and deletion of elements in the beginning the middle and in the end of the list there are three most common variations of the linked list data Cy and each one of them may be particularly useful depending on the problem that you have to solve for example if you need need to transverse the link at list only in the forward Direction which means starting reading from the head to the tail of the list you can Implement a singly linked list with this type each node has a reference to the next node only another variation is the dowly linked list each node has a reference to the next node and the previous node allow you to transverse the list both forward and backwards mind that both the singly and doubly linked list allow you to transverse in the list in the different directions but don't allow you to quickly go back to the head or the tail of the list if this is required then you must implement the third type which is called the circular linked list with this type each node has a reference to the next node and the previous node and the list itself keeps track of the head and the tail during insertions and remov removals as for what are the advantages of linked lists they allow for quick manipulation of the data within the list being a dynamic data cery that can grow and shrink in size at runtime by allocating and deallocating memory as a result there is no need to specify the linked list initial size there is no memory wastage in the linked list since the size of the linked list increases or decreases at one time the linked list makes it easier to insert and delete elements after an element is inserted or deleted there is no need to move it only the address in the next pointer or perhaps the previous pointers needs to be updated just like any other data cery link at Leist also have dis advantages for instance they require more memory than an array because a reference is necessary to store the address of the next entry or the previous entry in the linked list and all of this consumes add memory as a node is a combination of its data and its references finding a single element is much harder since there is no index pointing to the element therefore there is no random access to the elements you always need to transverse the list if you want to fight one single element also un like arrays linked lists provide no mem or locality using linked list brings many performance disadvantages as you cannot exploit the processor speed and his direct access to cash all right and off with the theory let's now learn how to implement a linked list and review some of the problems that you may have to solve during your coding interview all right let's start the most exciting part of this episode which is the coding part back to our Visual Studio code we're going to start implementation of our linked list we're going to start with a singly uh one so I'm going to ask code whisper to implement a singly linked list perod right let's see I'm going to hit enter see what happens next and then sometimes you're going to notice that code risper won't recommend nothing for you but what this means is that you might need to provide some hints about where you want the code to be generated for example here I'm not within any Declaration of a class or any method so it doesn't know what to do right so a linked list is usually going to be a combination of at least two classes right the actual linked list and a class that represents the node so I am going to actually invoke code whisper here besides the Declaration of the linked list and then as you can see here is starting to kind of a oh okay you need a node for the link list right so yes I need a node and just like is recommending here this node needs to contain data and a reference or pointer right to the next element so so so far so good I'm going to start hitting enter and there here is a very interesting Constructor for us to initialize the data another enter uh no I don't want to pointer to the next node what is going to be really useful here in this class is maybe some methods to retrieve the next uh the next element so maybe I could provide a hint one for retrieving the data I think this is important I think this is good good but if I hit enter again what I want is to set the data okay I I'll deal with it but what I need code whisper yes that's what I need is a method to retrieve the reference of the next node and for the sake of the argument want also to write the next reference so I think now we're starting to look good uh one thing that I'm going to do before proceeding is that I'm going to refactor the name of this class to maybe node element I think that's going to be a node element because I want to avoid in future episodes when we start like playing with a code whisper uh clashes of code whisper also recommending another class called node so for this particular case we're going to deal with the node element right so for code whisper it knows how to keep track of all the existing classes so it won't make any difference right so now that we have a node and let's recap this node contains the data and the reference to the next element and everything else is just play node pojo and Java to expose the internal attributes to the outside word right so with the proper uh visibility modifiers so now we can go back to our Link at list class and then if we put here an Ask code whisper I can always hit uh option C you're going to see that um it's starting to suggest some things for us here now what is suggesting here is essentially um what seems to be what we are going to accomplish later which is uh evolve from the singly link linked list to a dobly one because as you can see here it's sking track of the Hat in detail actually it's it's suggesting the user of a circular one but I'm going to accept it and modify the data a little bit because uh at this point I don't want let me close close this method declaration here at this point I don't want [Applause] to okay let me close this and then the defination of the node elements was created outside the Declaration of the class so maybe uh I need to close this class here first okay and then I'm going to put the node elements below so now the compiler is understanding better the code so back to what we're saying before uh we don't want the usage of the head and tail only the head actually for now because a singly linked list needs to have the reference needs to keep track of the the head first and I'm going to remove everything that has to do with the tail so one interesting thing that you can do with code whisper when this situation happens which means you accept something but you don't want all all of the code you can always literally remove everything generated and if you hit enter again it's going to suggest bed on the current shape of your implementation so now as you can see here it's only uh recommending things that match with what you have which is keep track of the head and keep track of the size right I'm going to do the same thing for the G here um actually I'm going to remove this method G we won't need any G to retrieve a specific elements um at least not for now and I'm going to remove the method remove sounds redundant but it isn't um okay so with that done let's sove this okay size is not being used because we're not exposing to the outside word so maybe what we can do is to use yeah so let's create a method to retrieve the size of this list now let's recap what we have done first of all you've declared a class that represents the node a node contains the data and the next element and then the exposing to the outside word and then the actual linked list the primary job is to keep track of the heads right and then which means that every time you're going to add some data in not only you have to provide a code that's going to do this but it needs to keep updating the head to always keep track of what is the beginning of the list right and then a method to retrieve the size for us to check if it's working let's create the famous method to print the list so maybe create a method code whisper is getting used to the way I think so it's suggesting exactly what I know so I'm going to hit enter I'm going to accept the implementation of it okay okay maybe I have to finish this here and then something else needs to be no this this uh is that correct retrieve the current lit which is starting from the head and then while it's transversing the list it means the current elements are different than n is printing the the current one and then retrieving the next one which is going to be the current one seems to be all right let's test it out so let's create a main method to this so main method all right so let's add three ele elements to this list and then let's ask the list to print the elements I think we're good here so we've instantiated the linked list we've added three elements one two three and then we're going to print the list so let's see how this goes I'm going to click run actually click click it twice but doesn't matter I can remove one of the consoles this this one's going to be fine so let's click again yeah one 2 three so it's printing the list list and matter that we are actually printing the list transversing forward direction right which start from the head and then we are iterating over the existing elements of the list so it seems to be working correct right now uh one of the things one of the problems that you might probably see in curent interviews is the transformation of a singly linked list to a dobly one right so uh the the main purpose of this type of questions for the interviewer perspective is for them to evaluate and measure your knowledge in terms do you really know the internal structure of a linked list right so in this case what is a doubly linked list is uh is a one that where each element contains a reference to the next element and the previous element so for our implementation here what we need to do is to create another reference to a node element that's going to represent the pre previous right the previous element so most of the time Cod whisper if you think uh press enter here is going to try to suggest this but if not you can always Implement yourself so like node element yeah here we go so it's starting to know what I'm tending to do it's predicting my intention so yes I need a previous one exactly and because of because of this I need also to create a blank Constructor yeah probably probably we need it it's always a best practice but more than this we also need a way for us to expose just like we did here with the GS and the SS to the next pointer so I'm going to hit enter here here you go I need a gter from from the previous and I need a Setter from the previous so that sounds more like it and here's the interesting part now that we've updated our node element right so that that's the first step when creating a doubly linked list you need to in the class or the implementation that you have for the node you have to have those two references or pointers but the job is not done you also have to update your implementation of the linked list because remember everything about the linked list is keeping tracking of the ad right because now even if you move uh backward or forward you need to also keep track of this and during the insertion time which is this method here add you also need to update the information about the previous or uh yeah we call previous yeah prev previous elements so again what you can always do with code whisper is literally remove all the implementation that currently is only providing awareness of the uh next one so you can remove and then if you hit enter again it's going to provide you a new suggestion that takes into the consideration the prev and the next one so as you can see here yep that's it so I'm going to accept it so as you can see here now not only is updating the references to the next element but for the previous element as well right um we don't need to update the print the print is basically moving forward so it's good uh the only thing I'm going to do here to test if this is double uh linked list is working is to create a new method that's going to do the printing but printing in Reverse meaning uh it's going to the end of the list and then it's going to print back forward right so it's to prove that it is able to retrieve the previous elements once given a current element of the list so I am going to create a method to print the list in reverse order which by itself it's another problem problem that you might see in your interview not not exactly with this name but again is the interview wanting to know if you understand the stery of a singly or a doubly linked list so let's see how this goes print reverse okay start with the head right and then let's see how this goes again and then it's going to basically iterate over the entire linked list pay attention to this because this depending of the size of this linked list this might be timing consuming and then here you go uh once you hit once you transverse the entire list meaning you're going to reach the the last element of the list so now you are doing the operation uh the inverse operation which is back going back right so you just move forward now we're moving in reverse and then you were printing all the data that's currently existing so in order to prove that theory we're going to include another method call here after list print actually let's do a the famous separation here so we can see the difference and then list dot print and reverse let's see if this works so I'm going to click run and it works as you can see here it prints 1 two three which are the elements that has been added and then 3 2 one which is start from the end it printed in Reverse so that proves that not only using a double link list you can move in different directions but also it proves to the interviewer interviewer that you know the structur uh of a singly and a doubly link list this is very important because this is what they want to measure on you if you have complete awareness about how to implement a linked link now let's do a similar exercise with might reminds a similar problem which is how to transform a doubly linked list or for the sake of the argument a singly linked list to a circular one right so uh a circular linked list is one that keeps track of the head of the linked list as well as of the tail of the linked list which is exactly what uh code whispered whispered in the beginning and we didn't accept it uh whatsoever but now we're going to accept the recommendation so the first step is to make sure that you have event imployment for the node perspective so from the note perspective since we want a doubly one everything is in place so you don't need to change much in here and then we're we're also need to keep track of the I'm going to hit enter here and see what code whisper suggests but if it doesn't suggest anything we can give a hint about Our intention which is hey code whisper could you yes here we go could you create a tail reference for me yes that's what I want I need a tail and now we need to not only modify the Constructor because we need to initialize with um actually for the Java perspective we don't actually need to do this this is more like a best practice but by default references in Java are intialized with no and primitive times are initialized with zero in this case of integer but anyway just for the make for the sake of uh completeness let's accept the recommendation and then we also need to literally replace the entire implementation of the ad MTH so just like we did before let's remove and delete everything and you can always ask code whisper to do your job again so now consider that not only you have to keep track of the head you have to keep track of the tail so let's see what could whisper is preparing for us it's spinning here as you can see in the bottom nothing yet so let's ask again option C uh all right now we have some suggestions let's whatever the suggestion had yes so now as you can see here the implementation is keeping track of the heads and the Tails right and all right so every time you add a new elements is going to keep updating those two references here so every time you need it you always have a reference of the current the the current head and the current tail every time you add a new elements because it's Dynamic right um in order for us to validate this we're going to use well first of all uh let's run the code one more time it needs to continue doing what it's supposed to do so printing one two three and printing 32 one so it's doing what it's supposed to do but in order for us to validate if the usage of a tail is actually impacting in the potential algorithms that you can write which is the main characteristics of using a circular linked list because you can always count with all right I have a reference to the end and then I can go back to the beginning because if you recall the print reverse what is currently doing once it was Implement as a double linked list was to transversing at least first the linked list to go to the end and then once in the end it was going back to the uh to the Head Right which is the uh backwards Direction so let's do this now that we have a tail reference let's remove this implementation and let's see if the new implementation suggests something more efficient because before it was doing like a two transversion of the list and this can be dangerous as you recall if you have multiple elements so I'm going to hit enter and ask code Whisperer to provide a new implementation and as you can see here the implementation is already paying off because look you have basically a reference to to the tail which is the reference that is being kept tra uh inside the link at Le data struy and then we are doing only one transverse of the list which is backwards so we have the tail and then we can go back to the be to the head to the beginning using one uh while loop so with that change let's see if the Behavior Uh didn't change right only it's more efficient right so I'm going to run the code again and let's see if it's continuing to print and generate the expected output and it is like 1 2 three which is the elments and 321 which is the reverse order but now what is the difference is because the usage of a circular linked list allows a more efficient algorithm to transverse back and forth look that that's the beauty that's what you have to have in mind while Implement these data structures very cool right so let's leverage another characteristics of circular linked list which is how easy can be to insert a new element but in the middle of the list right if you recall when we are dealing with arrays inserting a element in the middle of the list was relatively easy because arrays has the notion of indexes so we can kind of easy calculate where is the middle of the array but with liid list you don't have this concept of indexes right so how you can actually going to do the hole I want to insert in the middle so let's see how this goes uh which by the way it's another very common problem in Comm coding interviews which is how to add elements into the middle of the linked list so let's ask code Whisperer to [Music] create a method to remove no to insert a new element in the middle of the list all right let's let's be very specific about what we expect from code with I'm going to hit enter and then the method signature is not ideal at this point because I don't want to have to specify the index because this is not an array so for situation like this we can always like start with the method signature ourselves which is right insert and then accept but not the position only the data right so we can do this and then close the method declaration and then let Cod let's codee whisper do the rest uh there are some suggestions here let's see which one has a more efficient way to do things let's review the first it gets creates the new element with the new data of course start from the head and then transverse the list and then basically is no this is not what we want this is basically a plain Olde adding an element in the list so let's go to the other one create the element if the hat is new blah blah blah if not basically do what was doing before and then updates so this is not what we want in this one we have H is new blah blah blah else node elements start with i and then is basically comparing ah this is sounds more interesting it's basically calculating given the size because you know that every time you add a new element the size is updated right this there an internal attribute that holds that information so it's comparing where is the size if divided by two is the middle and then that's where the new element is going to be set and then basically do the whole pointing referencing and D references to the preview and the next one and let's just check the the last one to see if it's more intell intelligent Uh current no blah blah blah no so our winner is this one so let's let's use this one and then for us to see if this is working we need to create another method that retrieves what is the element that's currently stored in the middle of the linked list so this is going to be a new method so we're going to create a method to that re retrieves the element in the middle of the list all right so let's see how this goes C middle I like the signature this is exactly what we need uh in return say integer okay and then is basically let's all right let's review the code start with the head have a counter here I and then start counting until it measure if it's the middle and then when it hits the middle retrieves the current and then return the data that means that is going to transverse the linked list at least half of the linked list right so regardless of the number of elements that may take a while if it has 100 elements uh it's going to transver at least 50 elements of it so you have to keep this in mind right but anyway the algorithm seems correct Let's test it out so now that we have let's remove this we've we know that printing in Reverse is working so we're going to add the three numbers print them uh and then we're going to retrieve no we're going to insert the one in the middle last list so add where's the method signature that we've created for this uh insert data print reverse I forgot what what is the ma public void ins search we have two inserts right now uh uh one is ADD and another one is inserch all right so the one we have to use is inserch so let's insert the looking number 14 right if you haven't watched the series uh from the beginning you might have noticed that I have a history about the number 14 if you were curious about this put here in the comments if you want to hear the story about it and I will gladly answer for it so we're going to insert the number 14 and then we're going to uh print number in the middle which is yeah that's what I need thank you could whisper almost like you're doing more than I needed but uh yes we're going to print it insert in the middle and then we're going to printed Val I'm not very comfortable with the methods going to insert because it's a little misleading for our purposes so I'm going to refactor this method to something more descriptive so add element to Middle something more descriptive right so now we have more control about our intentions in the code all right let's see if this is working so um let's do another print here in between one print and the other so we can see more the details print yeah so let's run this code and see how this goes uh all right let's recap the the output this is the result of the first print one two three no big deal and then after this we've asked it to insert number 14 and the middle so one two the middle is is here three kind of makes sense okay and then number in the middle is 14 so the algorithm is doing what it's supposed to do uh if we recap the implementation so basically to retrieve in the the middle of the element the list or to add in the middle you have to calculate and keep track of where is the middle so you always going to have some sort of like have to have some sort of a counter and then you have to transverse the list to kind of a compare this counter to where is actually reach the um the middle of the list and that reminds me that I forgot to raise your attention to this very uh interesting element that Cod whisper generat for us and we didn't pay attention to it which is the concept of size right so every time you add or remove elements from the linol list you have to keep updating the size if further you want to do things like uh keeping tracking where is the Middle where is the 75% of the list things like this so don't forget to uh keep track besides like keeping track of the head and the tail right so let's take a look and how we can do some sort of a sorting in the linked list to play with some sorting the first thing we need to do is to include a method in our implementation to create some random values that we could play with so uh I'm going to ask code whisper to create a create you have noticed that every time I'm going to type up uh create I always misspell it and I have to go back and fix it so I have to take care of this a method to add random values to the list given a number of elements to be provided as provided as a parameter so I think that's very suggestive uh prompt for our code whis ER so let's hit Ender and then the implementation seems to be doing what it's supposed to let's review the code add random values we specify the number of elements to be added is going to iterate over this elements and then for each one of them is going to create a random value and then call the method add which mind you that it is the method that we have implemented before so this is one of the interesting things that you have to be aware about code Whisperer one of the nine thing it does which is the awareness of the existing code base you provide with so if you have your existing implementation open a tab and you have multiple other tabs with other classes or part of your code all of this is going to build up for code whisper to build a proper prompt that's going to be pass it over to the generative AI back end so all of this will sum up in for code whisper to provide with with a better recommend in this case as you can see here it's leveraging the existing methods available so that this is pretty awesome if you think about how you could expect code risper to suggest something that already exists and not just create random things out of nothing uh now that we have this method available let's use it so after creating our list we're going to list. add random values let's add three for now and then let's print the list to see if those numbers are indeed random so I'm going to click run and uh let's review the code 89 41 96 yeah they seem random to me right let's actually do something before we move forward let's use debug visualizer so we can inspect this truct of our linked list and so you can see how does it look like in in memory so I'm going to put a breakpoint here on print and then instead of clicking on run I'm going to click debug so debug um the code is waiting to be executed on list print so I'm going to select our linked list and invoke debug visualizer using selection as expression so this is our linked list mind you and although I'm sure that it's pretty hard for you to look uh as of now because the diagram is huge right but here is what you have to uh keep in mind first of all this is the root of our implementation so our implementation has a current SI of three makes sense because we have added three elements and then it has a pointer to the tail and a pointer to the head if we move to the head it's going to be the first element whose data is 71 let's see if this is true so if we print the execution so yeah first element 71 seven element 49 so let's see if this adds up so this is our link list first element the the date is 42 uh no actually this is the tail so we're looking to the tail which makes sense yeah the tail is 42 if we look this and look to the head the head is going to be number 71 makes sense here you go and then since it's the head of the link list it has no previous so makes sense it's new but has a next element so if we move to the next element the next element is going to have the data for9 so it matches what we are seeing here on the output so the thing that you have to keep in mind I'm going to zoom out a bit is that this is the structor created in memory for a li list implementation with only three elements now imagine the amount of references and pointers and links that would be created if you had 10,000 elements on this list so this is what I meant when I said before that linkoln list consumes more memory all of those references needs to be materialized on hip on a jvm in case of java of course so they can sustain those references and pointers through all over the place so keep that in mind because if the problem that you trying to solve is leaning towards more like optimizing in terms of memory consumption you have to remember oh yeah link lists are very hungry in terms of memory consumption so I have to avoid them as much as possible or perhaps trade off the usage of a circular linked list for a doubly or maybe a singly because a singly is going to use less references than a doubly or a circular blinket list so just keep that in mind uh I'm going to finish the debug visualizer so it's generating the random numbers that we've needed so let's play with the Sorting right now so I'm going to ask code Whisperer to create a method now the create was spelled properly create a method to sort the list just just this let's see how this what comes from this suggestion so sort and then I'm going to accept and giving the implementation we can almost figure it out what algorithm is being suggested here I would bet that this looks like a bubble sort right because remember the bubble sort algorithm has this kind of outer loop it's going to retrieve the heads start from the beginning the outer loop for each iteration is going to retrieve the current element and then it's going to have a inner loop that's going to walk over the implementation retrieve the current data set the current data blah blah blah and move to the next one right so it's basically do the whole swapping in the Inner Loop and then it's going to transverse all the entire list which is can be dangerous if that list is uh big right so this is one of the thing that you have to keep in mind also if you have to end up doing some some sort of a sorting always make sure to clarify with the interview okay are we dealing here with like a list of three elements like here or we're dealing with a list of 10,000 elements because depending of the size better sorting algorithms could be used such as like the merge sort or the quick sort right so keep just keep that in mind but I think bubble sort for our purposes here is going to uh suit our needs uh let's just change our main method quickly here to after we print we're going to put a separator here so we can see the difference for the unsorted version and the sorted version uh and then we're going to ask the list to be sorted and then we're going to print one more time so this print is going to print all the numbers uh unsorted we have a separator we're going to sort in place sorting right we're going to like do the whole like rearranging of the elements in memory and then we're going to print the current state of it to make things more interesting instead of only dealing with three elements let's add 10 elements I think 10 elements going to be more useful for our purposes here of testing the Sorting um sounds okay I'm going to click run and check if this is doing what it's supposed to do so this is our list printed unsorted clearly with random values and this is our list with a sorted version let's see if the Sorting makes sense 3 4 6 19 29 49 55 66 68 89 yep seems to be correct and these are 10 numbers so our sorting is working as expected so uh just a recap uh when you have to do some sort of a sorting operation of a linked list you always going to do either start from the head or perhaps you if you have a working with a circular Link at list you can start with the tail but regardless you were going to kind of iterate over instead of using counters and uh accessing the indices of a given elements just like we did with AAS you were actually going to retrieve the references and then keep using the next or previous elements to do the whole like moving forward or backward right so that that is the fundamental difference that you have to keep in mind regardless of the algorithm that you are going to use in this case we're using bubble sword but mind you that if we like had use it like quick sort for example uh the quick sort is basically an algorithm that does the whole like break it into multiple Hales it calculates a partition the middle of your list so you have to navigate at least the middle of the your list and calculate the partition and then break it out and do some sort of a recursion to sort one piece sort other and then merge back right so basically this is how quick sort works but regardless you have to remember that when you navigate through the list now you were relying on references and that's what you have to do to move forward and backwards all right let's wrap up what you have seen in this episode a linked list is a collection of data elements connected together via links there are three common variations of a linked list singly doubly and circular linked lists linked list allow for quick man population of data Dynamic size growth and shrinking and there is no memory wastage however they require more memory than when compared to a rays and finding a single element is much harder as they provide no random access to any one of the elements my suggestion for you is to keep practicing different problems related to linked list and use Amazon code Whisperer to assist you with the code generation then spend some time studying to generated code and whenever applicable criticize and correct the code in the next episode of this series we will take a look at the Q data struy if you start watching this series from the playlist the next video about qes should start pretty soon that reminds me the playlist from YouTube is essentially a linked list right a singly one because each video contains a reference to the next one if you haven't started watching the series from the playlist don't worry I put the link of the next video about cues in the description below see you in a bit