Hi, and welcome to episode twenty six of my
free Java video course. My name is Marcus Biel. In this episode, I will talk about the
Collections class LinkedList, including a hands-on coding session.
In the previous episode I introduced you to the Linked List data structure. As the name
implies, the Java class LinkedList is called LinkedList because internally it is based
on a Doubly Linked List. So what is the difference between the LinkedList
data structure and the class java.util.LinkedList? As an analogy, think of the abstract concept
of a car and a concrete car. The Linked List data structure is an abstract concept, independent
of any specific programming language. The LinkedList Java class is a concrete implementation
of this abstract concept. So in this episode I will focus on one specific
Linked List implementation, the java.util.LinkedList class. Among other interfaces, LinkedList
implements the java.util.List interface. You can have duplicate elements in a List and
you can go from element to element in the same order as the elements were inserted.
In a previous episode, I introduced you to the java.util.ArrayList class. As you can
see, both classes implement the List interface which makes them somewhat similar. So what’s
the difference between ArrayList and LinkedList? First of all, ArrayList is based on an Array
data structure, while LinkedList is based on a Doubly Linked List data structure. Compared
to an ArrayList, the Doubly Liked List data structure of the LinkedList class allows more
efficient insertion and removal of elements at any position within the List. Therefore,
as an implementation of the List interface prefer LinkedList over ArrayList if your main
use is to add or remove elements at random positions in the List. Otherwise, ArrayList
might be a better choice, because storing elements in an array consumes less memory
and generally gives faster access times. Besides the different data structures of ArrayList
and LinkedList, LinkedList also implements the Queue and the Deque interfaces which gives
it some additional functionality over ArrayList. In conclusion, there is no overall winner
between ArrayList and LinkedList. Your specific requirements will determine which class to
use. Let’s put ArrayList aside for now and have
an in-depth look at the LinkedList implementation. Here is a simplified code excerpt from the
java.util.LinkedList class. I don’t expect you to fully grasp every detail of the code,
I just want to show you that LinkedList is a normal Java class which anyone could have
written, given enough time and knowledge. The real source code is available online.
After watching this episode, I recommend that you take a look at it for yourself. Okay.
So, as you can see, LinkedList implements the List, Queue and Deque interfaces, as Deque
extends the Queue interface. Next you can see that the LinkedList class
has a reference to the first and the last elements of the list. Finally, you can see
that the class has functions like get, add or remove – to access, insert or delete elements
from the list. As we just saw in the code, the LinkedList
class has a reference to the first and last elements of the list, shown as red arrows
in this image. Every single element in a Doubly Linked List
has a reference to its previous and next elements as well as a reference to an item, simplified
as a number within a yellow box on this slide. Here you see a code excerpt of a Node. It
has private members for the item it holds, and for the previous and next Node in the
list. As a user of the Collections class LinkedList, you never directly access the Nodes. Instead
you use the public methods of the LinkedList class that internally operate on the private
Node members. In the episode about ArrayList I introduced
you to the methods of the List interface, so I won’t talk about those methods again.
Instead, let’s go on and look at the methods of the Queue interface implemented by LinkedList.
From a high level perspective, the Queue interface consists of three simple operations:
add an element to the end of the Queue retrieve an element from the front of the
Queue, without removing it. In the illustration the blue guy was copied,
but of course the operation returns a reference to the object and does not copy it.
Okay. Finally you can retrieve and remove an element from the front of the Queue.
In the lifetime of a Queue, there are special situations, like trying to remove an element
from an empty Queue or trying to add an element to a Queue that has a limited capacity and
is currently full. Depending on your specific implementation,
this might be an expected situation and you need a method that returns null or false in
this case. Alternatively this might be an unexpected situation and you need a method
that throws an Exception in this case. Therefore, the Queue interface offers each of its operations
in two flavours – one method that will throw an Exception, and one that will return a special
value in certain cases. Okay, let’s look at this in more detail.
A Queue allows to add elements to the end of the Queue.
“add” will throw an Exception when the Queue is full, while “offer” will return
false in this case. LinkedList, like most Queue implementations, has an unlimited capacity,
so it will never be full. ArrayBlockingQueue on the other hand is a Queue implementation
that has a limited capacity. Next, “element” and “peek” allow you
to retrieve an element from the front of the Queue, without removing it. If the Queue is
empty, the element function will throw an Exception, while peek() will return false.
Finally you can retrieve and remove an element from the front of the Queue. If the Queue
is empty, remove will throw an Exception, while poll will return false.
Okay, now we will look at some methods of the Deque interface, as implemented by LinkedList.
Deque is the short form of “Double Ended Queue”, so it is a Queue that can be accessed
from either end. Just like a Queue, a Deque allows adding,
retrieving and – retrieving and removing – an element.
But as it can be accessed from either end, the Queue methods we saw before now exist
in two variations – one for the first and one for the last element in the Deque. Again,
let’s look at this in more detail. You can add elements to both ends of the Deque. Just
like the add method of the Queue interface, addFirst and addLast will throw an Exception
when the Deque is full. “offerFirst” and “offerLast” will
return false instead of throwing an Exception. Please keep in mind that LinkedList has an
unlimited capacity, so it will never be full. LinkedBlockingDeque on the other hand is a
Deque implementation that may have a limited capacity. Okay, let’s go on.
You can retrieve elements from both ends of the Deque, without removing them.
“getFirst” and “getLast” will throw an Exception when the Queue is empty, while
“peekFirst” and “peekLast” will return false in this case. Finally, you can retrieve
and remove elements from both ends of the Deque. “removeFirst” and “removeLast”
will throw an Exception when the Queue is empty, while pollFirst and pollLast will return
false in this case. Okay. Now on to a completely different topic.
The Deque interface also supports the methods of the Stack data structure, “push” “peek”
and “pop”. Therefore java.util.LinkedList can also be used as Stack. A Stack is a very
simple data structure that can only be accessed from the top. As an analogy, think of a stack
of books. “push” adds an element to the top of the Stack. It is equivalent to the
“addFirst” method. “peek” retrieves but does not remove an element from the top
of the Stack. It is equivalent to the “peekFirst” method. “pop” retrieves and removes an
element from the top of the Stack. It is equivalent to the “removeFirst” method.
Okay. That’s enough for a first overview of the LinkedList Java class. Now let’s jump
into my IDE and see how all this works in practice. Okay, so now in part two you’ll actually
do some real coding with the LInkedList instance so this is actually the cool part. So let’s
start with the Deque reference variable and assign a LinkedList instance to it. Let’s
make it a Deque of strings and let’s use the so-called diamond operator on the right
side so we don’t have to write string again. The diamond operator was introduced with Java
7. So why do I use the Deque interface here on the left side? Well I will only show you
the methods of the Deque and the Queue interface. Deque extends the Queue interface. By the
way with just one click you see I imported java.util.Deque and java.util.LinkedList and
of course LinkedList also implements other interfaces like the Collection interface and
the List interface but this also what ArrayList does so if you want to see the methods of
the Collection and the List interface, you could watch my episode about ArrayList again.
So anyway, let’s already start adding elements to the Deque. For this, right now, I am using
add of the Queue interface. Let’s say I add a 1, Deque.add(“2”) and Deque.add(“3”)
and then let’s print out what we got so far. Now let’s execute this. And we have
a 1, 2, 3. Now add as I said is of the Queue interface so I could also say Queue here.
Then of course I would rename this to Queue but just for a second I cannot saw now addLast;
therefore, let’s switch back to the Deque interface. So if I say add or addLast, it’s
actually the same thing. Let’s see this. So addLast three times and execute it, 1,
2, 3. So let’s go a bit more in detail of what happens. We start with an empty Deque,
then we put somewhere into the empty Deque the 1 and then addLast just like add means
add 2 to the right side and then add 3 after it, always after it. And if we say instead
addFirst, this will then add the elements in reverse order and you see a 3, 2, 1. Of
course you could also mix these methods but this can get really confusing so I would try
to avoid that. And then also besides these three add methods, there is also offer and
offerFirst and offerLast. Now what’s the difference between these two methods? No,
not offer list, offerLast. What’s the difference exactly again between add and offer? Well
actually there is no big difference for a linkedList but there is a big difference for
a linkedBlockingDeque because we can limit it to two which means now we can add only
a maximum number of two elements but as you see here we add three elements so I would
expect that at line 13 something happens. And for offer, actually the offer method will
return a Boolean. It was added. So I can say it like this and then I can print it, execute
it. So it says that 3 was not added. Let’s also see this. So you see two and one only.
The three was not added. But what happens if instead I say add or addLast or addFirst
or whatever, this throws an IllegalStateException now – Deque is full. Well for a linkedList
instead, this is an unlimited Queue and Deque implementation so Deque cannot be an exception.
There is a difference though between addFirst and addLast because addFirst is a void method
so it does not return a Boolean but offerFirst and offerLast does return a Boolean but this
is probably a minor difference because it would only return last if the Queue or Deque
implementation is full. So those offerFirst, offerLast, offer, add,
addFirst and addLast, the methods to add elements to a Queue or a Deque. Now let’s jump to
the methods to retrieve but not remove an element from a Queue or Deque which is element.
But of course now let me rewrite that because before we can retrieve an element, we should
first of all add a few elements and to make this simple because we will focus on the retrieving
and not on adding, I will add 1 and 2 and 3 simply. Let’s remove all these. And then
let’s say Deque.element. Element is a function of the Queue interface so again just like
add we could here use the Queue interface or the Deque interface if we are just using
those methods. Let’s see what happens. And also to make it clear, let’s print out the
whole Deque after we called the element function. So you’ll see we retrieved 1, the element
here to the left, and then still the Deque looks as it looked before because it retrieved
the element but did not remove it. And now you might think there is elementFirst and
elementLast, no! This is a bit confusing. It’s called getFirst and getLast. So getFirst
in this case is the same as element and getLast should retrieve the 3. Yes it does! And now
of course besides element getFirst and getLast, there is also the peek method and peekFirst
and peekLast. Just like with add and offer, first of all, these methods look pretty much
the same. The difference is on an empty Queue or Deque… peekLast I think was still missing.
Exactly, this is the 3. Now if we remove this. We comment this out for the moment. Let’s
just directly remove everything. Now if I say peekLast on an empty Deque let’s see
what happens. See the Deque is empty – it returns null. Also when I say peekFirst it
returns null. But what if I say element or getFirst and getLast, it throws a NoSuchElementException.
getFirst as well as getLast. Now the question whether or not you want to use add or offer
or element or peek and these kinds of methods, this totally depends on your application as
said before and this is really important. Like if in your business case it is a normal
case that you could try to retrieve something from an empty Queue or Deque, then you would
probably go for the peek methods or if it’s normal that you have the case of a full Queue
or Deque, you would probably use the offer methods but if that is an exceptional case,
then you would use the add, addFirst, addLast methods so this is something that have to
decide. The Queue and Deque interface, this is really flexible, it allows you all different
types of behaviors. So now we saw adding and retrieving an element,
so what is still missing is retrieving and removing an element. We might just as well
directly start with the empty Deque and see what happens if we try to remove and retrieve
an element which is called here remove. So you see this also throws a NoSuchElementException
while it instead I would say poll, this again returns null. So each set of methods has this
difference of one version with an exception and the other one without. Of course, again,
there is pollFirst and pollLast. I think this is pretty easy now and remove and removeFirst
and removeLast. Maybe let’s do this once so before I say Deque add and then I say 1…
this was not IE, actually I want add. 1, 2, 3. It does make a difference that here we
have a LinkedList. A LinkedList allows duplicates so I could also add the 1 three times. Just
here I want to have 1, 2, 3 so that we actually see which element was removed. So now what
happens if I say removeLast, I print out the element that was retrieved and I removed it.
Before we just retrieved it, now I also remove it and then afterwards I print out the remaining
elements. So the 3 removeLast was removed and now the remaining elements 1 and 2 are
printed out. Let’s do the same thing with removeFirst. Now the 1 is removed and the
remaining elements 2 and 3 are printed out. So that much about adding, retrieving and
retrieving, removing elements from a Queue and a Deque.
Now, last but not least, let me show you the stack methods that are actually also part
of the Deque interface. There is no stack interface actually. There is a stack class
which extends vector but as said before in an earlier episode, you should avoid the vector
class and therefore you should also avoid the stack class. It was introduced I think
in Java 1 so like 20 years ago. From the performance side it is not so optimal but the stack methods
also exists in Deque and a stack is so simple you can just use an array or ArrayList of
course also but as we are talking about LinkedList and its methods, let’s still see its stack
methods so let me remove all these. Let’s now call this stack just to make it more obvious
that we’re now using the Deque as a stack. I hope this is not too confusing, I am sorry.
Yeah, there are really a lot of different data structures. So now for a stack, the method
is called push to add an element to our stack. A stack is a last in, first out data structure
so when I say I add let’s say a redbook and then let’s say a brownbook, just like
in our examples on the slides, you can think of it that the redbook is on the bottom and
the brownbook is on top. Now if we later retrieve and/or retrieve and remove a book, the first
one that will be removed is the brownbook because the stack only has one side that we
can access it. So first of all let’s leave it as it is and print it. This is the way
the LinkedList prints out its elements so this is how the toString method was implement
that it prints the elements from left to right. In the slides I showed it to you from top
to bottom but the way it’s visualized doesn’t really make a difference. What is important
is that we edit the redbook first and then the brownbook but you see here the brownbook
is to the left and then comes the redbook. Now what happens if I try to retrieve an element,
we say we peek on the stack and we might also print out this element then we cut this and
insert. So now the book on top of the stack was the brownbook. We peek on the stack. We
did not remove it, just retrieve it, so the stack just looks the same. Instead we can
also say pop and execute it again. So again, it was the brownbook but now there is only
one book left on our stack. Now of course I can also do this twice and then we should
have an empty stack and if I do this three times, pop will throw an exception because
we only have two books. There it is. So the first one was retrieved, the second one was
retrieved. Sorry the formatting here is a bit weird so two books were removed and retrieved
and printed out and then the third time there was the NoSuchElementException. We also see
this happened in LinkedList demo in line 14 so here at the third time we called pop, the
exception happened. So now what happens instead if I say peek on an empty stack, let’s see
this, this retrieves null so this does not throw an exception and there you’ll see
the stack is empty. And that’s it for this episode. If you enjoyed
it, click on the yellow box to subscribe to my newsletter.
If you have any questions, leave them as a comment below this video. And please remember
to give me a thumbs-up before you go! Thanks for watching, and see you next time.