in this lecture I'm going to talk about how to mutate linked structures we're going to do this using an example to insert an item into a sorted list for example if I have the list 11:21 41:51 and I insert 31 the new item should go in the middle I have other tests written here which do when you would expect this is a kind of complex problem so we're going to look at it in pieces the first thing we need to think about is how we would go about inserting an item into a list at all let's suppose we've already gotten to the place we want to be and we just need to stick an item in there how do we do it well we need to create a new node and we need to somehow stitch that node in the right place in this case I want the new note to go between 21 and 41 for my example inserting 31 that means I need to update the pointer of this object I need to change the next pointer of the node that has value 21 to point to my new object and then I need my new object to point to the item with 41 so let's just think about how we might do that let's start off with a pointer to the object that holds the item 21 to get there I'm gonna go through first and then through next note that I could also write this I'm doing this from the insert method so cut I could also write this with an explicit use of this so that's fine but it's normal Java style to leave out the use of this so I'll just say I'm going to first done next so you can see in the picture that I've made some progress here I've now a pointer X which is pointing to the item after which I want to insert the new node let's go ahead and create a new node and to store that I'll use a new variable called say Y and we'll go ahead and give this node the appropriate item and we'll just initialize the next pointer to null so there it is now let's watch that and see what happens and here I have my insert method I have X set to point to the object with 21 and I have Y pointing to this new object with 31 that's great so now I just need to stitch these things together so what do I want to change well I'm going to want to change two things I'm going to want to change X dot next and I'm gonna want to change Y dot next but if you notice here one of those things is important to remember as well so I need to remember the old value of x next before I destroy it one way to do that is to create yet another node variable called something like X next or whatever I will just call it f for the time being so it's the thing I'm going to go in front of and I'm going to make that equal to X dot next so now I have three pointers X F and Y and you can see that Y is now meant to go in between the X object and the F object so I can do that by using two commands one to update the pointer for X dot next and the other one to update the pointer for Y dot next so I'll do that here it doesn't matter which order I do them at this point so let's say we'll update Y dot next to be F and we'll update X dot next to be why those are the two things I want to do I want to set X to refer to this object and I want to set this object to refer to the object with 41 when I execute line 15 X dot next will change its gonna break the link of this list from 21 to 41 and have the list instead point from 21 to 31 here you can see that happening so I've got my new item correctly in the list but you can see here my list temporarily at least has lost all of the rest of the list so it's important to stitch this back in there and I can do that by the next line on line 16 I'll set Y dot next to point to this remainder of the list and once I've done that I now have 31 in the correct position in this list so that's our insertion logic this code will pass some tests it will fail others but it's clearly not done so let's think about what we need to do now we've managed to get a node in the right place but we did this by sort of hard coding where we were putting it we need to write a loop to find the right place in the list as with all loops will do this in pieces first we'll just assume we're doing things in the middle then we'll worry about what happens at the end then we'll worry about what happens at the beginning I've already put in an induction variable X so let's not worry about its initial value right now let's just think about what the loop is gonna do well what we want to do is loop along to a particular position so we need to move X to the next position in the list and the way we do that is simply saying X gets X next this will update X 2.2 the next thing in the list we've already seen this with linked lists accessors so that's how we make progress what we need to think about now is how do we stop how do we know where X should stop moving forward let's roll back the execution to the point before we put in the item 31 and what you can see here is we wanted X at a position where it's pointing to something less than 31 and the next item is something bigger than 31 the key thing here is that the next item is going to be bigger so if we don't want to stop at 11 we don't want to stop at 21 we want to stop once the next item is bigger than the item we're trying to insert we can write that as X dot next dot item less than item what this will look at is whether X next item is greater or smaller than the parameter item note that parameters are in brown fields are in blue note there's a difference between an object and the item it contains if I were to try and write something like this if X dot next is less than item I'll get a compiler error and the error here says that the comparison operator is not defined between nodes and doubles so here I'm trying to compare a node object to a double that's not okay and that's not what I actually want to do I want to look at the item inside the node and compare the item to the parameter that I've been given comparing X dot next to an item is something like in an array code just comparing an array to something it doesn't make sense you can't compare an array to a double you need to look at the items or the values in the array and then compare them now that we've figured out how to stop the loop we need to figure out how to start it the initial value I've chosen will work for some tests but it seems rather strange to start it first dot next why why don't I just start it first and this would allow us to insert after 11 in addition to inserting after 21 and things later than it so this loop is looking pretty good and I can run the code and see what it does when we start the call to insert we simply have the special variable this pointing to the particular list that I want to insert into on line 12 I'm going to allocate a new variable to alias the first node in the list so here is the variable X which is holding the address of the first node object in the list now we're going to check on line 13 whether X next item is less than item and in this case if we look at X next item we see it's 21 that is less than 31 and therefore will execute line 14 line 14 is going to move the pointer forward on line 13 again we check whether X next item is less than the parameter and in this case that's going to be false so we fall out of the loop and we'll update Y and proceed to stitch in this new object as we just did a second ago so once we've got it in place we're done note that graph is can get very creative drawing its pictures so this code is looking pretty good let's see what happens if I run my tests now I'll just comment up my drawing code and run the basic tests let's see what happens Oh bummer I'm getting what's called a nullpointerexception and that means that I've gone off and probably gone past the end of my array let's see where it's happening it's happening in Maine on line 36 and indeed this test is a test that's trying to put something at the end of the array and where am I going wrong well it's happening in the insert method on line 13 looking at line 13 you can see that this is the test where X dot next item is being compared to item well let's just walk through this particular test and see what's happening so I'll go back to my drawing code let's check it out X starts as before and we're gonna move X forward here and it looks like this is the place we go wrong so stepping back a moment we can see that X is pointing to the last note of the list and what I'm looking at here is X dot next item ah and this is the problem X dot next is null and therefore if I try to access X dot next dot item I get a null pointer exception this is the linked list equivalent of an array index out of bounds exception where you've gone one past the end of the array so I need to stop this search before I get to the end of the list in the case that the thing that I'm adding is actually meant to go at the end of the list I can do that really easily here simply checking for nullity and what I'm going to look to see is whether X dot next is null so while x dot next is not null and X dot next item is less than item I can go forward this is a very standard thing to do where I check for nullity of a pointer before I dereference it because at this point it is possible that X dot next has become null I need to check for nullity before I look into its item let's run this code and see what happens now as I run along I see that X is at the penultimate item and on line 14 I will update X dot next one more time to the last item of the list when I get to line 13 note that X dot next is now null and therefore we will not look at the item here this shows us an important property of Java's double ampersand operator which is true for the and operator in most programming languages we check the left hand side argument and only if the left hand side argument is true will we look at the right side argument note that if the left hand side is false false and anything is always going to be false therefore there's no reason to check the right hand side this is an important fact because it stops us from getting a null pointer exception were we to check this since X next is null we now go on to create the object and insert it and surprisingly the insertion logic doesn't change here note that the exact same code that I had to insert in the middle of the list is also working for the end of the list well that's fantastic let's see if we pass all of our tests Oh bummer I'm still getting a nullpointerexception is it in the same place no it's not now now I'm getting null pointer exception not at the end of the list but at the beginning so what's going on here well I'm trying to insert into the empty list and I'm getting a problem so let's drill in on this test and see what we can tell you can see the exceptions happening on line 13 so what happens is I execute well line 12 is fine I'm gonna set X to be null oh no is the value of first right now ah of course because I'm working on an empty list first is null for an empty list and therefore X will also be null oh and now we immediately see the problem we have that X next is null in this case and we're gonna get in trouble what do we do now well we could try something like this mmm X not equal null here and put another ampersand in here and let's see what happens in that case we're still getting trouble but now we're getting trouble on a different line okay this is not the right approach what I just did is what we call whack-a-mole debugging I just tried to do the obvious thing to get rid of this particular problem and you can see I whacked it down in one place and it just popped up somewhere else so generally speaking whack-a-mole debugging is not successful instead we actually need to think so let's think about what's going on here if I want to insert in this case note that I do not have any nodes in my list at all and so in this case there's really nothing I can do except put this item in a new node that's gonna follow first and there's no way I'll be able to do that using line 18 line 18 is updating the next pointer of an existing object there is no existing known object in this list that means I need a special case here so let me just put a special case so if first is null I'm gonna do one thing and if it's not null I'll do all of that and what do I want to do in this case well I'm gonna want to do something like this in this case I don't want to change the next field of an existing object I want to change first so everywhere I have X dot next here I'll just replace that with first let's just run the tests and see what happens well phooey I'm failing yet another test that's a bummer let's look and see what's happening here well in this case I'm feeling this test it says that I'm inserting eleven into the list that has some stuff oh so this is gonna go at the beginning of the list and my problem here is that we're expecting of course the item to go at the beginning of the list but it's not going at the beginning of the list it's going right after 21 well what the heck is going on with that let's zero in on this test and see what it looks like when we start at line 12 we can see that first is not null therefore we'll go to line 18 and initialize X on line 19 we'll check for the nullity of X next then compare X next item to the parameter in this case we see that X next item is 31 that is indeed greater than the current item so we'll break the loop and we'll insert the object here but note that the new node is going to go into the list after X that means that it will be the second node in list not the first what I really want to do here is update the first pointer what that means is that I need to expand the condition here if there are no items in the list clearly the new node needs to go at the beginning of the list but also if the first item in the list is greater than the parameter then I also need to put the new node at the beginning of the list thus I want to execute this branch of the conditional under two different circumstances if first is null or if first dot item is greater than the parameter it's important for the correctness of this code that the or operator in Java is asymmetric just like the and operator the right-hand side is only evaluated if the left-hand side is false that's important because if first is null we don't want to look at first item if we dereference a null pointer we'll get a null pointer exception now we can check to see if this is passing our tests and now we have correct code I've written this code using lots of intermediate steps explicitly and that's to make the pictures easier to read and make it easier for you to understand what's happening step by step but usually when people write code like this they'll make it much shorter by inlining a lot of this in fact this will become a single line so rather than using this variable to hold first here I will simply initialize the new node to first and rather than using Y as a temporary variable I'll just take the declaration here of Y an update first directly so this is the more typical way of writing this code and the same thing happens down here where X dot next is going to get a new node you can see that this code is still correct by running the tests you shouldn't be intimidated by this kind of expression in Java if you understand the assignment operation everything's just fine the assignment operation will evaluate the left-hand side to get an address and the right-hand side to get a value and then it will perform the assignment so note that this assignment to this location in memory doesn't happen until after the new node is created before I call the new node constructor I dereference X next so this is the old value of X next before the assignment the location that held that value is updated after the return of the node constructor if you're more comfortable with the more explicit form that's fine you can write your code this way however you should be able to read it in both forms to make sense of the kind of code we have here on line 21 it's really useful to think about what's happening in the underlying machine so I'll go ahead and draw the object IDs redundantly here so you can sort of see what's really going on these are all local variables that are holding values the object values are addresses of the objects so X here holds the value 156 and you can see in fact X is pointing to node 156 Y holds value 207 and you can see it's pointing to the node with value 207 likewise F here is pointing to 155 and you can see that indeed that's the value stored here so what's going to happen when I actually update X dot next well we're going to go to object 156 there it is and we're going to update its next field note that the next field currently contains 155 so what am I going to do well I'm going to copy the value of y what's the value of Y well it's the address of object 207 so we'll copy the address of object 207 into the next field of X and the effect of that is to update the diagram so that X next is indeed pointing to the object with ID 207 note that F is still pointing to 155 and when we execute line 22 what are we going to do well we're going to look at Y next Y next is this slot right here it's the second slot in object 207 and what we're going to do here is copy F well that's the address of object 155 so we're going to copy the address of object 155 into the second slot of object 207 then you can see that that's indeed what happens object 207 s second slot now holds the identifier or the address of object 155 and therefore we've sort of completed the whole list so that's how you insert a node into a linked list you need to understand the insertion logic you need to find where to put the element you need to figure out how to deal with the end of the list I need you to figure out how to deal with the beginning of the list finally once you've got it all figured out you can clean up and simplify your code