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