(upbeat music)
- So how do we use linked lists
in a programming language?
Well, let's start with Java,
and create a linked list from scratch.
So we'll scroll down here, select Java,
and delete all of this code,
and replace it with some new code.
To implement a linked list,
we can create two blueprints or classes
to define what a linked list is,
as well as how we can operate on this data structure.
One of these blueprints will define our linked list
and the other will define a node.
Technically, these are called classes,
but you can think of them as blueprints
because they define exactly what the item is
and how to create one.
We won't get too deep in this object-oriented terminology,
but let's take a look at this code.
What does a linked list consist of?
Well, it has a bunch of nodes.
You can access every node in a linked list
if you have access to the first node,
or the head of the list.
This means we only need to keep track
of the first node in our list
to keep track of the entire linked list.
But what exactly is in this node?
Well, a node contains data
and access to the next node,
so we store that in our node blueprint or class.
We also add a way to create a node
with something called a constructor.
If you've never seen Java code before, don't panic.
This is just a way to build nodes from the concept
of our blueprint or class.
With our blueprints in place,
we now know how our data will be organized.
However, we don't have a way to access it or add items.
That's where we'll need to add some functionality.
This means we'll need to create an add method
or an add function.
Between the curly brackets here
is where we would need to implement the function
or implement the method,
and write exactly how the linked list
is going to add an item.
Let's implement some basic add functionality.
Every time we want to add data to the linked list,
we want to add it to the front of the list,
and adding data will be focused on two possible cases.
In the first, the linked list is empty
and there are no items in the linked list.
In the second case, the linked list is not empty,
and we must adjust the head and next nodes accordingly.
To check if the list is empty,
we check if the head of the list is null,
or that there is no head node of this list.
If the list is empty,
we simply create a new node with the data given
and set it equal to the head of the list.
If the list is not empty, then we create a new node
and make that be the head of the list.
Before we make it be the head of the list, though,
we have to set the current head or the previous head
equal to the next of the node we want to add.
So instead of the first node being the head,
now we're having the first node be the node we're adding,
and then the next be the previous head.
Now that's the add functionality,
where we add new data to the front of the list
by creating a new node and resetting the head and next node.
Now let's actually use this data structure.
In Java, we use the main function to execute code,
or run code in our program.
The first thing we do in our main function
is create a linked list,
so we create this linked list from scratch,
and it's an empty list.
Then, on line 19, we add a number,
we add the number 10 to our linked list.
So now we have one item in our linked list
and it's equal to 10.
10 is at the head of the linked list.
Next on line 20, we add the number 18.
18 now is the new head of the list,
because we added 10 and now the list is not empty,
so when we add 18, it gets pushed to the right
and we have 18 and then 10.
This means when we print our data out to the console,
the head of the list has 18 as its data,
and the second item in the list has 10 as its data.
Let's go ahead and execute this code.
And we get the first node in the list as having the data 18,
and the second note in the list as having the data 10,
which is exactly what we expected.
Now we could implement everything we would ever want to do
with linked lists from scratch right here
in this linked list from scratch class.
But since so many people want this functionality,
many languages provide libraries
with this part already done.
Again, this allows you to focus more
on what you want to build
and less on maintaining your data structure.
Now let's use the linked list class
that's built into Java to create a travel bucket list.
We're in JDoodle, and we can select Java
as our programming language.
The first thing we're going to need to do
is delete this code inside of our main function.
To use a linked list,
we have to import it into our program,
because it's not in our current package.
So we'll write import java.util.LinkedList,
and now we'll be able to use this data structure,
or the library for this data structure.
To create a linked list,
we'll write LinkedList travelBucketList.
That's what we're going to be calling our linked list,
and then we're going to create this new linked list
with the constructor.
So how do we add items?
Well, there are a couple of different ways we can do it.
First, we can just add an item ordinarily.
So we'll add an item to our linked list.
Next, we could add an item to be the first
of our linked list.
So adding to the front of the linked list.
Next we could add to the back of our linked list
with add last,
and then on line 11, we add to a specific index.
So we're saying, "Hey, at index two,
I want to add this item, Galapagos Islands, Ecuador."
If we run this code,
we can see our linked list in the console.
So we'll execute.
And here we see all the different items in our linked list.
Now, how do we access items in our linked list?
Well, we can use something called the get function.
So we'll write system.out.printlntravelBucketList.get,
and then we can choose an index
that we want to get an item from.
In this case, we'll choose index 2
to get our Galapagos Islands in the console.
We can execute after we add a semi-colon here,
important syntax, and we see it in our console right here.
Now this might seem like an array.
We are using an index to retrieve a specific item.
While you can do that, it's extremely inefficient
because you would have to follow all of the pointers
in order to find that specific item.
It's better to just access from the front of the list.
So if we write system.out.println
and simply say getFirst,
so get that first item of the list,
that's going to be a lot quicker and a lot more efficient,
because that's the head of the list.
It's the first item that we see.
If we hit Execute, we'll see that first item
is Barcelona, Spain.
If this is not the way you want to access your data
and retrieve it,
then maybe this is not the best data structure
for your particular use case.
We also get search functionality with the linked list.
We can write travelBucketList.contains
and search for a specific item.
In this case, we'll say Barcelona, Spain.
We'll go ahead and execute this,
and we see that it is, in fact, in the linked list,
which it is.
Similar to an array, you have to be careful
with these one-liners.
They look easy and simple,
but behind the scenes, they are computationally expensive.
We can also remove items from our linked list.
Here we removed the first item, the last item,
and then print out the entire list.
If we run this,
we'll see that the first and last items have been removed.
Barcelona, Spain has been removed
and Tokyo, Japan has been removed,
so we're left with these two destinations.
We can also remove items by object and by index.
On line 25, we've removed by object
with Santorini, Greece,
so we're saying we want to remove the object
that has this value.
Next we remove by index.
So we're saying we want to remove the item at index zero.
This is the same thing as removing the first item
of the linked list.
Then we print out the list.
If we hit Execute,
we'll see the linked list is empty,
and that's because we removed Santorini, Greece,
and then we removed the item at index zero,
which became this item when we removed Santorini, Greece.
Now this might seem a little overwhelming,
but the important thing to know
is that with data structures,
there's a way to organize, store and access your data
no matter the programming language.
(upbeat music)