Okay so here's my solution to the challenge.
And if you haven't watched the previous video, be sure to do that,
because towards the end, I typed out the challenge and actually talked about it.
And actually went through and sort of said what the challenge was.
And here it is again, repeated on the screen.
But if you wanna hear more about that, certainly go back and do that.
And of course the other thing to make sure you've done is to actually
have attempted the challenge.
And hopefully you've done that, and
you're actually watching this video to check your results.
So, let's actually get started.
So I'm going to create, firstly,
the first base abstract class and we're going to do this.
So we're going to right click new as we've done now hundreds of times.
And I'm gonna call this ListItem.
And we're going to make that an abstract class.
So abstract class, for starters.
Okay, so we need, firstly, we want a list item for the rightLink.
So we'll do protected ListItem rightLink
= null Cuz by default it won't have a link.
protected ListItem leftLink = null.
And notice how we're actually putting references to ourselves in the class.
We're creating instances of this very same class within a class.
And we want a protected Object value.
Then we need a public constructor which is going to accept the Object parameter.
So adjust the object parameter, which will be that one there.
And we'll click OK to that.
So we're setting the value.
Now next we need to actually start talking about the actual abstract
classes that we want in.
So we need firstly an abstract class for next.
So we'll turn to list items.
ListItem.
That's abstract ListItem next.
Abstract ListItem setNext, as well.
Which obviously saves the item.
We also because we've done a Next, we also need a Previous.
So we do abstract ListItem previous.
Which returns the previous entry, and of course we want a set previous as well so
we can actually set that previous link as well to the previous list item.
So setPrevious (ListItem item).
We actually also want that compare to method that we talked
about abstract int compareTo (ListItem item).
So we can compare and see whether or an object is the same based
on not just a simple comparison but actually a rather in depth one.
Field by field.
Then we just want a getter and setter for
value itself even though that's set in the constructor.
And that's not gonna be abstract methods, it's just gonna be overridden, so
the getters and setters are just for value as well.
So that should be our base ListItem class there.
So again we've got two variables and
they hold references to objects of type ListItem.
The right link and the left link.
Thus you can say that each list item object can hold a link to the previous and
next items in the list that we're actually gonna be ultimately be saving.
And notice that to find a constructor for the abstract class as well, any concrete
class that inherits from list item will need a constructor that sets the value.
So it really makes sense in that case because it needs to be done each time
to put the constructor in this ListItem abstract class.
We also defined a getter as you can see there, and
just a confirmation of the abstract methods defined, what must be implemented
by any concrete class it inherits from, this ListItem class.
So again, next returns a reference to the next ListItem in the list.
setNext where we're passing the parameter list items sets
the reference to the next item to refer to in the parameter, which is courseItem.
And previous and setPrevious does the opposite,
it actually sets the reference to the previous item in the list.
And then sets the reference to the setPrevious to the previous item
to refer to the parameter item, which is passed.
And again, compareTo, compares an object to the item.
Whatever has been passed through the parameter and returned zero with or equal,
and also returns a number if the item parameter should sort before the object,
which would be negative.
Otherwise it is gonna return a positive number.
And incidentally,
the reason that I've actually declared the fields to be protected rather
than private is because we need to be able to access them from our concrete subclass.
Now, we could have left the access modifier off,
which would have meant that the member variables are packaged private.
So in other words, subclasses in the same package would be able to access them.
But not subclasses in other packages, as that's why we've made it protected.
Okay so in order to create list items,
we need to actually have this concrete class we've talked about.
So one that actually implements all those methods.
And as a result, can therefore be instantiated.
So let's go and create that.
That's gonna be a new Java class.
And we're gonna call that Node.
So the first thing we need to do is we need to extends ListItem.
And of course we're gonna get a complaint that we haven't implemented those
abstract methods yet.
We'll start with the constructor.
It just uses the abstract classes constructed to set that
value of that object, and then next needs to start overriding some objects.
So we're gonna start with next.
Actually what we'll do is, the ones we needs are next, previous, setNext, and
previous, and also compareTo.
So what I'm gonna have to do is just create the stubs for those,
by just going in here and overriding.
And we're gonna select all of one, two, three, four,
five, all five of those there.
There the ones we need to override, and by doing that, we've now got a valid class,
but of course we now need to add the actually functionality itself.
So we're gonna start with the next method, and all that really needs to do,
this is the next item.
To the right, so we return this.rightLink.
Which is of course a field within the abstract class.
And with setNext, what we're gonna do is a little bit different.
So I'm gonna do this.rightLink = item, one that was passed to us.
And we go to actually return that very thing that was actually saved, so
this.rightLink.
Okay, and likewise for previous.
But of course previous pretty straightforward,
we're gonna return the leftLink cuz it's the entry previous.
So this.leftLink and
from a setPrevious, null points were actually deciding what this is gonna be.
It's gonna return, it's going to be this.leftLink = item.
Then we actually return this.leftLink as well.
That brings us down now to the compareTo,
and what we need to do there is return that value, which was negative 1,
if the item parameter should sort before the object.
Otherwise, we're gonna return a positive 1, if that's not the case.
And of course we return 0 if they're considered to be equal.
So, first thing we're gonna do, test for null.
So, we put if(item != null).
Then we're gonna return ( (String)
super.getValue)).compare.((String) item.getValue()).
Otherwise we do an else return a -1,
because it's actually null and
therefore has to be in that sort order.
Negative because any value is gonna be greater than null, effectively.
So you can see that we're actually using the getValue method
to actually figure out we're using the compareTo in comparing that to each item.
And in case you're wondering, we're going to be actually using strings as our
values, even though we've defined it as type Object.
So looking at that ListItem, we've defined it as type Object there.
In the node we're actually going to be passing this as string, so
that's why I can actually use string here for a comparison.
And .compareTo works nicely with string as well.
And again the next and previous methods are basically just getters, and
the setNext and setPrevious methods are very similar to setters and
what they're doing, but they're also returning the values as well and
returning any appropriate reference variable as well.
You might be wondering why we're doing that, but don't worry.
Later on, we'll actually talk about that.
It's not going to actually affect your solution.
It's done more for convenience rather than being actually essential to the program.
If you haven't returned it that's okay.
And just a confirmation that the compareTo method looks actually like a lot but
it's actually quite easy.
It's easy to implement here because we're storing strings as our value as I
mentioned, and the string class already has its own compareTo.
So if you were writing your own class and not using a string class in this
particular scenario, you'd have to write your own compareTo operator.
But in this case because the string class itself has got that built in,
all we really need to do is use the .compare and
that's going to return the 0, the -1, or the 1 depending on the actual value.
And the other thing we're doing is if a null was passed we are returning -1
automatically, because we can't test that, but negative is always gonna be,
that any value is gonna be greater than null, that's why we're returning -1.
At this point now, we've got a concrete class that extends our abstract ListItem.
And we can create objects of type node, and
build structures by making the nodes next and previous links point to each other.
Probably a good idea at this point before we go ahead and
actually do that, before we actually create a link list,
to define an interface that any structure using a node objects will implement.
And we can actually use that interface later on.
So let's actually go ahead and do that.
So I'm going to do a new Java class Interface.
And we'll call this one NodeList.
We're going to start off.
We're going to have a getRoot, which is gonna be the actual ListItem itself.
So ListItem getRoot and another function we need
is obviously the addItem that's going to be ListItem.
We need a removeItem which is also going to pass the ListItem.
And we need a void traverse.
So this is some way of actually going through the list.
transverse(ListItem root) like so.
That should be it,
because any data structure that we create must have a starting node,
we know about that, and that's what we're putting in the ListItem, the getRoot.
In the case of the LinkList, this is often called the head of the list but
using the term root is also used a lot and actually applies to
binary search trees if you researched on that, you've probably noticed that.
We also needed methods to add and remove items to the structure.
And that so we've done that in the interface.
That's why we used addItem to removeItem.
And finally we have that traverse method, which I mentioned,
which will start at the root and print in the values of each item in the structure.
Traverse is through the list, if you will.
And I spelled traverse wrong, traverse.
Okay, so let's now create a linked list class, and
I mentioned before about actually using the right names.
And getting confused with what is the linked list from Java in our own
interpretation of linked lists, so I'm actually gonna call this My Linked List.
Just so there's no confusion with the linked list that's actually built
into Java and the linked list class that we're actually creating here.
So, public class MyLinkedList implements NodeList.
And obviously we're gonna get error because we haven't
implemented everything yet.
So I'm gonna start with private ListItem root = null.
That's gonna be our basic, our head record or our root record.
And we need this constructor.
It's gonna be just that root item.
And we're gonna set the value for the root item to start off.
And next we'll need to override those other methods as well that were part in
parcel of the interface, so I'm gonna do that.
So we'll click implement.
And we've got four there you as can see that we actually must override
to make it valid, so we're just gonna do that.
Now some of these are easy, the getRoot will be just this.root,
gonna return the root.
So what we need to do for that, for an addItem we need to check for the empty
ListItem first, then add a new item as the head of the list if it was empty.
But if the list wasn't empty, then what we need to do is compare each
item in the list with a new item to work out where the new item should be inserted.
Because remember, we're sorting it in a particular order.
So the way we'll do that would be, you'll change the return for now, and
we'll start by putting if(this.root == null).
Well that's easy, so that's going to be just as a comment, the list
was empty, so this item becomes the head of the list.
If that's been the case, we could just put this.root = item,
which was actually passed.
Actually call that newItem, just so we're really clear what we're trying to do here.
So this new item is passed to us.
So in that case, because the root, we didn't have any other entries,
this is the first time it's been used.
We're setting this to become the head of the list, effectively.
And at that point we can also return true because we've
succeeded in adding the item.
Then we'll put an else, or we don't even need to put an else,
because we're gonna start with the code, because the code then is only gonna get
down to here if that first if block of code wasn't actually called.
So now what we need to do at this point is,
we need to start comparing from the head of the list.
So we're gonna type ListItem currentItem = this.root.
So that's our first head item, head of the list.
while(currentItem != null).
So while we've still got the ability to actually link through our items,
cuz we're gonna be going through and comparing them one by one.
And going through to the next and the next, so on.
If we reach a null, that basically means that there's no more entries
to actually go through in the list.
So first I'm going to then is do a comparison.
So int comparison = (currentItem.compareTo
(newItem), the item that has been passed to this method.
Now we start doing our tests.
So we do if(comparison), remembering that returns a negative number, a 0, or
a number that's greater than 0, if(comparison < 0).
So we'll do that one first.
And less than 0 is if the newItem is greater, so
we need to move right if possible.
So we'll put if(currentItem.next != null).
So if there's some way we can actually go forward,
in other words go to the next item, you're gonna go currentItem = currentItem.next.
You need to continue processing, otherwise we've reached the end, we can't actually
go to any other records, so we've actually reached the end of that list.
So what we can do is we can put, there is no next, so
insert at the end of the list which effectively is where we are at now,
so we can put currentItem.setNext(newItem).
And then newItem.setPrevious(currentItem).
And then return true.
So you can see what we've done there.
We pointed to the current item that we can reach.
Basically, we've got as far as we can.
There's no other entries.
And we go to .next because we actually received a null, so
we set the next null to the new item, where it was null.
The new item that we've just inserted currently can go back to that,
to the previous item, if that makes sense.
So, just as a recap, the current item, we're at the last entry in the list.
We're setting the next, so there's another record, which is a new item,
which was passed to this method.
But they were also setting the setPrevious entry for
the new item to point back to what was then the current item,
if that makes sense, so it can traverse and go back.
So if you didn't do that, the newItem previous would be set currently to null.
And it would be sort of like an record and couldn't go anywhere.
So that's why we're doing it that way.
So that's the first comparison if the answer you got was less than 0.
But we also need to do another one.
We need to come back here and put else if(comparison > 0).
So in other words newItem is less and we need to try and insert before.
So we need to do the other thing, we need to go through and do a test for
null but going backwards this time.
Going to previous entries.
So if(currentItem.previous() != null),
then we do currentItem.previous .setNext(newItem).
We also do then newItem.setPrevious.
Whoops I put an extra bracket in there by mistake.
(currentItem.previous()).
Then newItem.setNext(currentItem) and
your currentItem.setPrevious = (newItem).
So, again, what we're doing is, we know that we have to insert this before,
so if currentItem.previous returns something that wasn't null, so
if it still returned a record.
Then what we're doing is, we're setting the currentItem.previous,
what was the previous entry, pointing to the .setNext from there from there,
to set that to set that to the value of newItem, which of course is the item that
we've actually added to this, or we've passed, to this addItem.
And then we go on to the newItem and set the setPrevious link for that to point to
what was the curtentItem.previous, if that actually make sense.
And then we've done the same for .Next, so we're actually pointing with the .Next for
the current item, and then currentItem.setPreviousItem.
So, I know that sounds confusing, but essentially, what we're doing is,
we're inserting the new item, basically, before what was the current item,
and then the other thing we need to test here is the else.
Which would be else In this scenario,
the node without a previous is the root.
So, if we got to this point, it means that we've got to the very first record, and
there is no previous.
So if that's the case,
we need to actually make this new item effectively become the new root.
So, we're doing newItem.setNext(this.root).
Then we do this.root.setPrevious(newItem).
And then this.root = newItem.
So you can see what we've done there.
So in that case, what we've done is we're setting newItem.next to
point to what is currently the root record.
And that's because we're inserting ourselves.
We're becoming the root.
So we need to point to what was the root.
So we need another gate in traverse.
It actually goes to that entry.
And then obviously, the set root we're setting the set previous to point back to
the new item, because it's now not going to be the root anymore.
It's gonna be sort of the second item, and
needs to have a previous link to the new record that we're adding, the new item.
And last thing, we're setting the this.root, which is our head,
the head of the list to become this new item.
So that's the comparison for greater than 0 when newItem was less.
And then the other thing was, in the last scenario, is actually quite easy.
Because we've already tested, and then they're equal.
At this point, they're equal and
we actually don't want to actually add them if they're equal, so
we're gonna put newItem.getValue() + "is already present, not added").
Because we decided we didn't actually want duplicates.
And we're gonna return false here.
And incidentally here, we're gonna return true.
Because in both cases, whether we found the record at the head or whether we
actually just inserted it previously and fixed all the other links up.
In both cases, we were success there, so we're actually gonna return true.
And outside of all this code here, which we shouldn't hit anyway,
outside of the wall loop as well.
We're actually going there to put,
return false, just to fulfill the methods and the method is happy with that.
And that's it, so that's the addItem, which is quite a bit of code there, but
hopefully you understood that also based on linked lists which we talked about
in previous videos as well.
All right, so I'm gonna stop this video here, and in the next method we're gonna
actually look at some of the code we've actually typed and
I'm gonna show you some of the shortcuts you can actually use to reduce a bit of
code in scenarios where you're actually doing things like this.
So I'll see you in that next video.