Java for Beginners 25 – Linked List data structure

Hi, and welcome to episode 25 of my free Java
video course. My name is Marcus Biel. In this episode, I will talk about the data structure
LinkedList. First of all, let’s have a look at the term “LinkedList”. Why is LinkedList
actually called LinkedList? For the term “Link” – as an analogy – think of a weblink – when
you click on it, it brings you from one website to the next. A list is a collection of related
objects. Think of a shopping list – it contains every item that you plan to buy. So a LinkedList
is a collection of related objects, where a link will bring you from one item to the
next item. Technically, in our LinkedList, an item or entry of the list is stored in
a so called “Node”. In our simple example, this entry is the number twenty three. Each
node has a link or pointer to the next element of the list, the next node. For every item
that we want to add to the LinkedList, we create a node and store the item in it. The
first item of the list is usually called the head, the last item of the list the tail of
the list. For every new item, we create a new node and link to it from the last element
of the list. So a LinkedList is a dynamic data structure that can hold any number of
elements, as long as enough memory is available. After the list is created, to navigate through
the list we call a function like next() which uses the link to go from one item to the next.
This type of a LinkedList is called a Singly Linked List because the links only go in one
direction – from the head of the list to the tail. So to navigate to the previous element,
for example from the element 42 – to the element 9 – you have to go back to the head of the
list – and you have to call the function next() – on every single element until you reach
the element 9. If the list contains a lot of elements, this may take some time. Inserting
an element after the current element is relatively easy with a Singly Linked List. You create
a new Node containing the new element. You link to the new element “17” from the current
element “9”. You add a link pointing from the new “17” element to the existing “42”
element. And you’r done. Inserting the same element before the current element is generally possible
in a Singly LinkedList, but usually not very efficient. It will require to navigate to
the previous element, starting from the beginning of the list, as I showed you before. Removing
an element from a Singly Linked List has the same issue – it is possible, but generally
not very efficient. These operations get much easier, when you add a second link to each
node, pointing to the previous element. This way you can navigate in both directions of
the list. However the extra link comes at a cost, of extra memory, as well as time to
build the more complex structure. If this overhead is justified, I cannot generally
answer, as it will differ for each use case. If performance is an issue, I advise you to
test different options. Anyway, so a LinkedList that contains nodes that provide a link to
the next and the previous node is called a “Doubly Linked List”. For every element that
you add to a Doubly LinkedList, you need to create two links, so creating a Doubly Linked
List is somewhat more complicated. Navigation in both directions in a Doubly Linked List
is easier, but at the cost of a more complex structure. Based on the two way link structure
adding or removing an element before or after the current element is relatively easy. Here
we will add the element “17” before the current element “9”.
The back link from element “9” to element “3” is removed and replaced by a back link
to the new element “17”. From the new element “17” we link to the next element “9”. Next,
we place a back link from 17 to 3. The old link from element 3 to 9 is replaced by a
link from 3 to 17. Removing an element from a Doubly LinkedList has the same steps as
inserting an element to the list, just in reverse order. Let’s look at a code excerpt
of a Node in a Singly LinkedList. So you have a method to retrieve the item of a Node, and
a method to go to the next Node. The Node of a Doubly LinkedList is very similar, but
a bit more complex. Additionally, you have a reference to the previous Node. A LinkedList
usually contains a link to the head of the List. The methods of the Node class will be
used to navigate through the list. The concrete implementation of methods to get, add or remove
an element from the list, depends on the type of the node, but such an implementation detail
is usually hidden from a user of the list. Besides the direct link to the current node
of the list and the head of the list, a LinkedList may also provide a direct link to the tail
of the list. This is common for a Doubly Linked List, but may also be beneficial for a Singly
Linked List. Let’s have a look at different application scenarios for a LinkedList. A
LinkedList can be used to implement data structures like List, Queue, Stack or Double Ended Queue.
When comparing implementations based on a Singly- or a Doubly Linked List, there is
no overall winner. Both have advantages and disadvantages that make them useful for different
application scenarios. Using the example of List, Queue, Stack and Double Ended Queue
we will in each case decide for a Singly- or a Doubly Linked based implementation. An
implementation with other data structures, for example an array, is also possible, but
that’s a different story. A list usually requires random access to any element of the list,
so I would recommend an implementation based on a Doubly Linked List. In a so called “first
in first out” Queue, new elements are inserted at the tail of the queue and removed from
the head of the queue. Random access is not required, so I would recommend an implementation
based on a Singly Linked List. A Stack provides a so called “Last in First out” order. Elements
are added and removed from the head of the Stack, which makes it even more simple then
a Queue. Therefore a Singly Linked List is usually sufficient. A Double Ended Queue or
Deque is a very dynamic data structure. It allows to access, add or remove elements from
both ends. Therefore I would use a Doubly Linked List to implement a Deque. And that’s
it for this episode. If you enjoyed it, remember to give me a thumbs-up! You can leave your
questions as a comment below this video. Click on the yellow button to receive a free Java
bonus video and to subscribe to my newsletter. Thanks for watching, and see you next time.

Leave a Reply

Your email address will not be published. Required fields are marked *