In the previous video, we actually talked about the linked list, and
in this video what we're gonna do is actually start using it in our code.
So if I open the project that I opened, or created originally in the previous video,
I'm gonna create a new class to leave the other one as it was, gonna call it demo.
And when you're creating a new class in IntelliJ, if you want a main method so
that you can actually execute it, there's actually a shortcut.
You type psvm, which stands for public static void main.
And if you press Tab, before I do that you can see on the screen it actually tells
you what it's going to do main method declaration.
Press Tab now, actually creates that for
us cuz it's something that you wanna do in a lot of Java programs,
until it just makes life easier for you, but allowing you to work.
So next, let's create a link list.
And what we're gonna do is create a link list of the places to visit, which is
the capital cities in Australia that we talked about in the previous video.
And I'll type in LinkedList.
String, gonna call it placesToVisit = new, it's gonna be LinkedList
that was presented there, that's the default declaration.
And it looks very similar to an array list but of course it's a LinkedList.
So adding records is very similar as well.
We type in the name of the variable plus ToVisit.add and we just type
in Australia's places, so we've got Sydney and I'm gonna add a few entries here.
I'm going to add, do a couple different ones.
We're gonna do Melbourne, Brisbane,
let's do Perth, Canberra.
Got Adelaide where I live and we'll do Darwin as well.
So we've got one too many there.
So that's enough now.
We can actually create a method, I'm gonna do with such,
we create a method that actually prints them out.
I'm gonna type printList(placesToVisit) so
I'm gonna pass the parameter of the LinkedList.
So I'm gonna create that method and the printList is going to accept the parameter
of our LinkedList and it's going to use the concept of an iterator.
I'm gonna type in private static void.
Void, because we don't need to return anything, printList.
And the value we're going to be accepting as a parameter is LinkedList.
And we'll just call it linkedList, like so.
And what we're gonna do is just use this concept of an iterator.
So an iterator is another way of accessing and going through all entries that are in
a particular array, or an arrayList, or a linkedList, etc.
So it's got a concept, well actually on top of that, and then we'll go through it.
So type Iterator,
i= linkedList.iterator.
So notice that the .iterator, that method is actually part of the linkedList,
comes with it automatically.
We're doing the equivalent to a four leap.
Four leap four, i equals zero, i less than placesToVisit.size.
We're doing something like that, but we're doing it in a different way.
So what we're gonna do is type in while i.hasNext,
and we're gonna do System.out.
Now visiting, i.next.
Then we're gonna do at the end,
we'll just print out some equal signs just to show that we're at the end.
So what this is actually doing and going back to link this,
do you remember that the linkedList entry pointed to another entry?
So what we're doing is we're saying while that entry,while an element that's in this
linkedList is pointing to something else, in other words,
there's at least one more record to actually visit, while that is true,
we're actually gonna show the current record.
And that i.next is actually part of that.
So what that actually does, it actually sets it,
then as we go through you use i.next.
That actually also changes the value of the iterator.
That's equivalent to typing i++ i equals i plus 1.
We're actually saying I'll put that i.next which actually
gives you the current record but that also then moves onto the next record as well.
So consequently hasNext is just to say is there another entry,
but .next is actually moving to the next entry,
but it's actually returning what the current value is before it moves on.
So that's why we can actually put Now visiting,
and that will show in, the first time we run this, it'll actually show city.
So it will show a city but then automatically move to Brisbane.
So that's actually how it works.
So let's just try running this to make sure that it actually does work.
And you can see it's now visiting Sydney, Melbourne, Brisbane, Perth, Canberra,
Adelaide, and Darwin.
So it's going through the whole list automatically as you can see and
it's working nicely.
So let's actually go back here and add some more code.
Let's actually insert records.
So what we're going to do is we're going to insert Alice Springs and
that's gonna be in index position 1 which of course immediately after Sydney.
So if we do that, if we type placesToVisit.add, we sign,
add element at the index position 1.
We're going to add Alice Springs.
Let's do that.
Let's then also print out the result.
Let's try that and see what happens.
You can see the first time we have Sydney, Melbourne, Brisbane, Perth, etc.
The second time we've now got numbers in Sydney, Alice Springs.
And notice how Alice Springs is now automatically linking to Melbourne.
So this has happened automatically.
We've inserted that entry.
So you can see what's happened when we inserted Alice Springs.
Sydney is now pointing to Alice Springs.
And Alice Springs is pointing to Melbourne.
Whereas the first time, we actually ran through, Sydney was pointing to Melbourne.
So just by you typing in that command to insert that record with
the index position, the actual linked list functionality in Java has done that for
you automatically, which is pretty cool.
That it's sort of built in to do that.
So let's head to add a new entry to insert a new record.
If we wanna remove one, similarly, we can do something like placesToVisit.remove,
and we wanna remove the element at position 4.
So we do that, and we actually run the code again.
Well, actually what we'll do is actually add a print first.
We'll run the code again now.
And we can see automatically what's happened there.
The first list we had Sydney, Melbourne, Brisbane then we had Sydney,
Alice Springs, Melbourne.
This time we've got Sydney, Alice Springs, Melbourne, Brisbane but this is not Perth
and Perth was of course index position 4, which is actually the fifth element.
So one, two, three, four, five.
That was Perth,
that was the index position 4 which of course is element five.
So by typing the remove, you can see that what happened was Brisbane,
which was pointing to Perth, Brisbane is now pointing to Canberra, so
Perth has been sort of removed completely and that's how a linked list works.
I can say it's pretty cool that it does a lot of that for you automatically and
it handles the linking to the next records the next one in the list
automatically for you.
And of course with this mechanism if you have thousands of records,
there's not really gonna be any slowdown in performance
because it's literally only changing one or two entries at the most.
Everything else remains at the same position.
Now at the moment we haven't really done anything that couldn't be done with
an array or arrayList.
And actually in fact when it comes to adding other strings,
we have to count into the list to find out the entry, the index position to add to.
So we have to actually tell it we want it added in this position.
Likewise for deleting Perth we have to count the number of items and actually
decide their selves by passing the number as to which element we wanted to remove.
Let me now show you the advantages of a linked list.
What I'm gonna do is add the cities in alphabet order.
Now alphabetically it may not be the best way to visit the cities in a country
the size of Australia.
But really the important thing here is we're gonna be imposing an order.
So what we're gonna be doing is we're gonna be saying that every
time an entry is added to the linked list,
we're gonna make sure that it's actually added in alphabetical order.
So this was where you use some other algorithm to work out the distances or
something like that.
And figure out the most efficient way and perhaps add it in that way.
But in this case just as an example we ended up doing it in alphabetical order.
We're gonna start off an empty list, that means that the first
item to be added is always gonna be added right from the start.
But when it comes to add the second item what we're gonna do is,
we're gonna compare it to the first and then three things can actually happen.
Firstly, if it's the same as the first, in other words,
if it's a duplicate, we don't wanna visit the same city twice so
if that's the case we're gonna ignore that entry and not actually accept it.
If it sorts alphabetically before the first city, if that's the case,
we want to insert it before the current city.
And if it alphabetically is greater than the current city, if that's the case,
we wanna move it to the next city, and then we wanna repeat the process.
So I can say that by comparing that as we're actually inserting it,
we can put it in the right place each time.
So eventually when we get to the end of the list if the item has not been added by
now, then it belongs to the end.
So I'll add it there and implement it.
And we're gonna be using something similar to an iterator and
that's called a list iterator.
So what I'm gonna do now is just type in some of the code and
then we'll go through it and actually try running it.
So I'm gonna create this method.
Now close down this run window for now.
We're gonna use private static boolean addInOrder.
So the parameters we're going to have here are the parameters,
it's gonna be the new city, String newCity.
But for purposes I'll also add another one.
We're gonna add a parameter which we, the actual linked list itself,
that we want to actually add.
So, we'll call that linkedList, like so.
So, the first thing we need to do is create a new iterator and
you saw that in the previous code example above.
We used linkedList.iterator.
Well, we're gonna use what's called a list iterator.
And, as you say,
list iterator gives you some more flexibility then a traditional iterator.
And it's really made for situations like this where we're inserting and
inserting certain records and so forth.
So we can type stringListIterator equals it's gonna be linkedList.iterator.
We're gonna type while and that should have been list iterator,
listIterator, like so, while, stringListIterator.hasNext.
I'm gonna go through all the records.
And I'll just make a bit of space here so we can see what we're typing a bit better.
So we've got out listed array there remembering that the first entry or
when you create this for
the first time, when you point it to the listed array there, it's
automatically gonna go to the very first entry that's stored in the linked list.
Then we're gonna use the .hasNext, and using the while loop we're gonna navigate
through all entries that are in this string list iterator.
Then, we're gonna use a compare two function,
which we haven't talked about before.
So I'm gonna type int comparison = stringListIterator.next.
So, we're moving to the next record.
.compareTo(newCity), which of course, was the variable that was
passed to this method, which is the city that we're looking to insert.
So what that gives us is a number.
So it gives us a number.
If the number that's returned, the integer, if it's 0 it means that
both the value that's in the string is in the linked list the current index entry
that we're searching for is equal to the newCity variable in this case.
So there's no other words, 0 means that they actually matched.
If that's the case we don't wanna add anything so
we're gonna put if comparison equals zero so
that means they're equal, do not add.
So that would mean for example if we had the city being Adelaide already,
we're actually using that as a parameter to pass to this method.
If that was also the entry, the count goes through the wall loop that we were
currently looking at, we don't wanna add Adelaide again.
So if that's the case, we're gonna
print out a message that says newCity + is
already included, or as a destination.
Don't wanna add it again.
And we're gonna type return false.
False meaning that it wasn't successfully added.
Otherwise we can do else if comparison, if it's greater than 0,
what that means is the new item should appear before this one.
So if that's the case, we'll say it's the new City should appear
before this one and the example of that would be if we can't
really looking at the record for Brisbane, but if Adelaide was parsed as a parameter,
then Adelaide, alphabetically, starts before Brisbane, so A comes before B.
So the comparison would return a number greater than 0 if that was the case, so
we'd wanna then add it.
But we've actually got a problem at this point.
And the problem is, we've already used .next.
So in other words we've already moved onto the next record.
So we've done the comparison.
We've actually checked it but
the comparison was chosen when we used .next so we used the .next
which returned the current entry but then it moved to the next entry automatically.
So what we actually need to do in this case if comparison's greater than 0,
we to move back to the previous entry again, the one that we're at.
In other word, in this case Brisbane, and we wanna add new city.
So to do that we type stringListIterator.previous.
Commit previous means go back to the previous entry, the previous match.
So in other words, go back to the record that's linked to this one.
stringListIterator.add(newCity), then we add
the city at that point so that ultimately it's going to appear before that entry.
So in this case, again, if we're looking at Brisbane and we've found Adelaide,
Adelaide was passed as a parameter and by using the .previous,
it goes back to the Brisbane record.
And, by using .add, that's actually gonna go and add it at the right position.
It's gonna add it in that entry and that's what the .previous does.
So, we're using this special type of list iterator because normally,
you can't do that with a regular iterator.
Normally, you've just gotta go through all the records.
There's no way for you to go back to a previous record.
But, the list iterator is a special type of iterator
that enables us to actually do that.
So, that's why we're actually doing that.
So if that's the case, we were able to add the record, so that was good.
So the record was added successfully, so we can return true, else
if comparison, if it's less than
0 move on to next city, in other words you don't need to actually do anything there.
So that was a situation where we actually
found in a case that said Brisbane must pass as a parameter and
where actually Adelaide, well Brisbane doesn't come before Adelaide.
So we don't wanna do anything in that case because obviously we need to move
onto the next record because that record can't be added in.
And because we've done the .next up here automatically,
it's already moved on to the next record anyway.
So we don't need to actually do any processing at that point.
And finally, at the end of the wild loop, so
here if we get down this far, what that means is we've gone through the entire
list without finding a suitable point to insert the entry.
So the new item actually has to go to the end of the list in that case.
So what we really need to do there is type stringListIterator.add(newCity).
That's actually it.
So what I'm gonna do is end the video here.
In the next video we'll come back and we'll actually just discuss this a little
bit more and we'll actually go and change it so
that we're actually running our code using this method and just see whether it does
work, whether it does actually convert things and put them in alphabetical order.
So I'll see you in the next video.