Bummer! You have been redirected as the page you requested could not be found.
Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Java Data Structures!
You have completed Java Data Structures!
Preview
The `java.util.List` interface supports a collection of ordered items that allows for additions and deletions. Let's check out some of its power! You may never use an Array again.
Resources
Keyboard Shortcuts
- Clear: [Ctrl + L]
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
Remember back when we talked
0:00
about how adding and removing
elements from an array was a pain?
0:02
And I mentioned how I'd show you
a better way?
0:06
Well, here's that better way. Lists.
0:08
Just like arrays,
lists are an ordered collection of items.
0:11
You can insert or replace items
wherever you want by index,
0:14
and just like arrays,
those indices are zero-based.
0:18
You can check if an item is in the list
and sort it, too.
0:22
There's several implementations
of the list interface that are included.
0:25
Let's take a look at my most
commonly used one, the ArrayList.
0:29
Okay, so let's pop over to the List
0:35
Interface documentation real quick.
0:36
So again, this is an interface, and it's
0:40
defining a generic parameter
here called E.
0:42
And that type parameter
E is the type of elements in this list.
0:45
And there's different implementations
available.
0:49
Here they are, and each implementation
has its own benefit.
0:51
But no matter what,
since they signed this list contract,
0:55
they all define
the methods that are below here.
0:58
There's some great ones here too.
1:01
There's add,
and it takes an element and adds it.
1:02
There is another add.
1:06
Remember, that's method signatures
working for us here.
1:07
So this add takes an element, and this add
takes an index and an element.
1:10
So there are two different methods
with the same name.
1:14
Pretty cool, right?
1:16
There's contains.
1:18
You can empty it with clear.
1:21
Get is how you get something out.
So this is similar to how you do
1:24
array brackets. Remove, here's another one.
1:27
So you can do remove at a certain index
or at an object
1:31
but again it's the same name but
they're just using different parameters.
1:35
Method overloading there. And size and set.
You can set a certain
1:38
one at that value. I don't know about you
but i'm itching to play with this.
1:44
Let's go get JShell running.
1:48
Now one thing to note here
1:52
is that the JShell program
that we're using has, for nicety's sakes,
1:53
imported java.util.star,
just to be convenient for us.
1:57
Now normally we'd have to import
these things ourselves.
2:02
Okay,
so let's create a fruit list example.
2:05
Let's make a list of fruit names.
2:08
So we want something to use
that implements that list interface.
2:11
So let's explore ArrayList first.
2:14
So it's a list of strings
2:17
named fruit.
2:21
And we're going to set it
2:24
equal to a new ArrayList of strings
2:25
and add our parentheses at the end.
2:28
So again,
2:32
I'm going to hammer this home
as it is key to understanding the way
2:33
that this collections
framework is intended to work.
2:36
We're using the interface
as the type on the declaration side.
2:39
So over here is the interface list,
but we use the implementation,
2:43
array list, on the right side
over here in the definition side.
2:47
Now this allows us to change the
implementation at any time when necessary.
2:52
As long as we only expose the interface,
we can change the implementation
2:56
whenever we want.
3:00
All right,
so let's play around with this list.
3:02
So is it empty?
3:04
True.
3:10
Yes okay,
well let's add one. Let's add cherry
3:11
How many items are in there?
3:20
One, because we just added one.
3:24
This is like checking the length on an array.
3:27
How do we get things from it?
3:30
Again, it's zero-based,
so that's the first element.
3:32
Cherry.
3:37
Awesome.
3:38
It also has a contains method.
3:39
Fruit.contains cherry.
3:41
That is true.
3:47
Does it contain peach?
3:50
It does not.
3:53
Let's add some more.
3:55
And let's take a look
4:04
at what it looks these days.
4:05
Cherry, banana, and a coconut.
4:08
So using a method signature that takes
an integer in our generic type, or e
4:11
as we saw, which is string, we can insert
at a specific place in the list.
4:16
So say I wanted to put a lime in
before the coconut.
4:21
So that's that third element.
4:24
So I'd want to do fruit.add 2 for that.
4:26
And then I'm going to put a lime in there.
4:30
Okay, so
4:36
now if we take a look at the fruit list,
there is the lime and the coconut.
4:36
And I can also remove things
by equality or index.
4:40
So if I say fruit.remove, let's get banana
4:44
out of there.
4:47
Cool, take a look.
4:51
Okay, and we can also sort the list.
4:53
So if I say collections.sort fruit, much
4:55
we did arrays.sort,
now we take a look and it's sorted.
4:58
And that works with the same logic
with the comparable.
5:03
Things must be comparable
to do that sorting.
5:06
This framework also plays
well with older ways of doing things.
5:09
So you can make an array of generic
objects by calling fruit.toArray.
5:12
And you'll notice that
that created an object array,
5:18
which might be what you want.
5:21
You know,
some things require an object array,
5:22
but most likely you're going
to want to have a specific type.
5:25
So you can do this.
5:27
It's a little strange syntax,
but if you say new string,
5:29
you pass it basically an empty array
of what you want it to go into.
5:33
You'll create a new string
array out of that.
5:36
It's a little awkward,
but it's cool, right?
5:39
Now we can play with older programs
that only accept arrays
5:42
while still getting to use the much less
awkward list interface methods.
5:45
Now there's a handy way to create
a filled list, using the arrays helper.
5:49
You'll see this used all over the place.
5:54
So let's make a new list of strings
here named vegetables.
5:56
And you can say arrays dot as list.
6:01
Again, arrays is in the util package,
and it takes
6:04
multiple params here, as much as you want,
6:07
and that will return me back
a list of vegetables.
6:10
Cool.
6:14
And we can put that into an array,
just like we saw.
6:16
Let's drop this into the veggie array,
6:19
and we'll say vegetables.toArray,
6:23
new string array, zero.
6:28
Now let assume we had this
Veggie array here
6:33
and we wanted to get it as a list
You can also pass an array to the arrays
6:36
parameter
if we want to pass in the veggie array.
6:40
So we want a list of strings
6:43
veggie list
6:46
arrays
6:49
veggie array.
6:52
There we go.
6:56
And now we have the vegetables list again.
6:57
So that's the list interface.
6:59
And let's look at what
other implementations are available.
7:01
Let's go back to the docs.
7:04
So if you come up
7:07
here, here's again
all known implementing classes.
7:08
Let's look at the ArrayList
that we were just playing around with.
7:12
Okay, so ArrayList is a resizable
7:16
array implementation
of the list interface.
7:19
Okay, so that's what we were doing
earlier, right?
7:22
We had those arrays and we were resizing
them, copying them around.
7:25
Implements all of the optional list
operations from its elements,
7:29
including null.
7:32
Internally, it does those manipulations
that we were talking about.
7:34
Okay, so now I want to try something
a little different here.
7:38
Now, part of my goal as your teacher here
is to make sure that you can
7:41
eventually understand
all this documentation.
7:44
Now, my expectation is that this document,
this documentation here,
7:47
is probably going to blow your mind.
7:51
And I want to take the time to acknowledge
that this is unfortunate.
7:53
While all the information here is valid,
I really feel that the level of complexity
7:57
of comprehension doesn't line up
with the intention of this framework.
8:01
But as a developer, this is something
that you're going to encounter.
8:05
And this will not be the last time
that you read documentation
8:09
that is way out there.
8:11
So part of the trick to expanding
8:13
your knowledge is learning
how to weed through stuff like this.
8:15
And personally,
8:18
I feel that imparting these skills on you
is also part of my duty as a teacher.
8:19
So I'm going to attempt
to pop into a simulation here.
8:23
Okay,
so I'm going to read this as a student
8:26
who's just beginning and have maybe taken
some Java courses here and there.
8:27
And again,
I'm going to be thinking out loud.
8:31
Okay,
8:35
so this next paragraph here is where
we're going to start.
8:35
The size is empty,
get set iterator and list
8:38
iterator operations run in constant time.
8:42
Constant time.
8:46
Okay, so constant time.
8:47
I think I heard something about that
in that big O documentation he included.
8:49
I think I remember
reading something about that.
8:54
The at operation runs in amortized.
8:57
Amortized, that's a word.
9:00
That's in loans, right? Constant time.
9:03
That is adding in elements requires
9:07
O. Oh, but there's that big O notation.
9:11
That's what it's talking about.
9:12
Requires O n time.
9:14
All other operations run in linear
time, roughly speaking.
9:17
The constant factor is low compared to
that for the linked list implementation.
9:21
All right,
so I think I remember seeing that up here.
9:26
Let's take a look
and see what linked list is.
9:28
And let me
9:32
go back to the main interface
list page here.
9:32
All known implementing classes linked list.
9:36
Okay, here.
9:38
So let's take a look and see something
about the constant factor.
9:40
Let's go in here.
9:42
Okay, so this says doubly linked list
9:44
implementation of the list
and deque interfaces.
9:47
Doubly linked list implementation,
what is that?
9:51
Implements optional list operations.
All of the operations
9:55
could perform as
could be expected for a doubly linked list.
9:58
What is the doubly linked list?
What is that?
10:03
Why is there no link anywhere?
10:06
What is going on?
10:09
What is linked list?
10:10
Well,
I guess it was saying that the other thing
10:12
was comparing this, these two things
together, right?
10:14
Back in the ArrayList documentation, it
was comparing these two things together.
10:17
The constant factor is low compared
to the linked list implementation.
10:22
So I'm going to jump into Google
because I'm not getting anything here.
10:26
Let's see what we can find.
10:30
All right, I'm going to search
ArrayList versus LinkedList Java.
10:31
All right, let's see here.
10:36
This one, Stack
10:38
Overflow, that's always a good one
to check out.
10:40
Always been one
to simply use the list, right?
10:44
So he's using the list interface on the
left, in the implementation on the right.
10:46
And it says, I use the interface
as the type name for portability.
10:51
Awesome. That's what we've been doing too.
We know that.
10:54
So when should linked list
be used over array list and vice versa?
10:57
Oh, well, that's exactly what we were
just looking at.
11:01
Okay, let's scroll down here.
11:04
Too long, didn't read.
11:06
Array list with array deck are preferable
11:07
and much more use cases than linked list.
11:10
If you're not sure,
just start with array list.
11:13
That's awesome.
11:16
So, linked list and array
11:17
list are two different
implementations of the list interface.
11:18
Linked list
implements it with a double linked list.
11:22
There that is again.
11:25
We should probably look that up
11:26
because it seems important
to understanding what's going on.
11:27
An array list implements it
with a dynamically resizing array.
11:31
Cool, we knew that.
11:35
Okay, as with standard
linked list and array operations,
11:37
the various methods will have different
algorithmic runtimes.
11:40
Okay.
11:44
So here we see that again.
11:45
There's this O to the N.
11:46
Maybe we should
11:51
do a Google for Big O Notation real fast.
11:52
It looks it's
all kind of pointing towards that.
11:55
Alright,
I'm just going to do a Google search
11:59
for Big O Notation Java.
12:01
And let's just click on this
first one here.
12:04
The big O notation
is a fundamental concept
12:11
to help us measure the time complexity
and space complexity of the algorithm.
12:14
In other words, it helps us measure
how performant and how much storage
12:19
and computer resources an algorithm uses.
12:24
Okay, so I guess this all kind of wraps
back around to what I said earlier, right?
12:27
Everything kind of falls down
to how long do
12:32
these algorithms take for the type of data
that we're working with, right?
12:35
So these big O numbers,
they're all talking about how fast
12:40
it would work for certain situations.
12:43
So if you're struggling
a bit with the Java documentation,
12:46
don't feel discouraged.
12:49
It's unfortunately a pretty difficult one
to get the hang of
12:51
when you don't already have some knowledge
on other terms in place.
12:54
I encourage you to keep referring back
to it, though, and utilizing Google
12:57
when you need some help.
13:01
And don't worry, not all online
documentation is this difficult.
13:02
Whew!
13:06
So I don't know about you,
but I need to take a break.
13:07
I'm going to go do some jumping jacks
and get my brain moving,
13:10
and then jump back into
adding lists into our code.
13:13
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up