Lesson 4 - Linked Lists in Java
In the previous lesson, Lists with arrays in Java, we introduced lists and described how
lists that use internal arrays work in detail. We also described the
ArrayList
class. In today's Java tutorial, we're going to focus on
the second type of lists, which are linked lists.
Linked lists
The second approach for creating lists with a variable number of elements is to create a linked list. This way of doing things doesn't incorporate arrays and uses a different principle instead. The individual elements of the linked list are placed randomly in memory (they are no longer in a sequence) and all consecutive elements refer to each other. You could see it as a chain where the first element is connected to the second one, the second one to the third one, and so on. Here's a visual representation of the elements from the last lesson in a linked list:

This type of list is referred to as a singly linked list. If there isn't a real reason to save memory, you would usually reference the consecutive elements in both directions, e.g. the second to the first, and so on. In which case, we'd be dealing with a doubly linked list. The list, in this case, would look something like this:

With linked lists, we lose the ability to access any given element quickly by its index due to the fact that the elements are no longer all in a row in memory. There's no way to effectively jump right to the 100th element and read its value. If we want to access a specific element, we'd have to go from the first element to the second, from the second to the third, and go on until we reach the element we need. The time complexity of reading and writing at a given index depends on the number of elements in the List.
However, sometimes we don't have the need to index elements and then this type of collection becomes very useful. A while back, we said that we wouldn't be using arrays at all. We're not limited by the length of the list anymore and we can add or remove the elements at runtime as long as we have enough memory. We are also able to remove elements in the middle of the list or to add new elements between the existing ones. When using arrays, adding a new element in the middle was only possible if we shifted all of the elements on the right in order to make space for the new element. This cost us a considerable amount of time which was dependent on the number of elements. As for linked lists, all we have to do is reference a new element between two existing elements (the other elements aren't affected).
Simply put, we have an efficient manner of inserting and removing elements
where the toll paid is inefficient access to indexes. This sort of thing is
common in regards to data structures and algorithms,
one thing in exchange for another
As you can tell, linked lists and lists that use internal arrays are very different. If we plan on accessing elements using random indexes often, choosing the linked list would be a disaster. On the contrary, if we needed to add or delete elements in the middle of the collection, it'd be a piece of cake for the linked list, but the list with an array would be extremely slow.
LinkedList
Linked lists are represented by the generic LinkedList
collection in Java. This class uses doubly linked lists, we won't find singly
linked lists in Java. We could program them, but it wouldn't be worth it since
it's harder to work with them and saving memory isn't very significant for our
intents and purposes.
Again, the complete hierarchy of the linked list classes is shown below:
LinekedList
doesn't contain our elements directly as
ArrayList
did. Instead, it stores elements of the Node
type. These are nodes which point to each other (or refer to, if you will) and
have the item
property. This is where our element (the value) is
stored, wrapped in the node. The nodes extend our items of the references to the
surrounding elements. Let's take a quick look at the other methods that the
LinkedList
provides compared to the previous
ArrayList
:
addFirst()
- Adds a new element at the beginning of the list.addLast()
- Adds a new element at the end of the list.getFirst()
- Returns the first element.getLast()
- Returns the last element.removeFirst()
- Removes the first element.removeLast()
- Removes the last element.
Example
Let's try a similar example to the one that we used for the
ArrayList
:
LinkedList<Integer> list = new LinkedList<>(); list.add(5); list.addFirst(6); list.addLast(10); System.out.println(list.getFirst()); System.out.println(list.getLast());
The program output:
6 10
We create a new linked list of the Integer
type and add the
first element using the standard add()
method. Then, we add the
number 6
using addFirst()
to get to the top of the
list. We use the addLast()
method to add a third element. Finally,
we list the first and last elements.
Let's also try how that quick adding and removing elements work:
// initializing and filling the linked list LinkedList<Integer> list = new LinkedList<>(); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); list.addLast(5); // adding and deleting in the middle of the list list.add(3, 32); list.add(3, 31); list.remove(2); // printing the list for (Integer i : list) { System.out.print(i + ", "); }
The output:
1, 2, 31, 32, 4, 5,
We mainly use linked lists when we want to add and delete elements in the
middle of the list, which would be very slow using the ArrayList
class.
Today's lesson was a bit shorter, but I didn't want to start off with a new topic and leave you hanging. Next time, Multidimentional arrays in Java, we'll take a look at multidimensional arrays.
Did you have a problem with anything? Download the sample application below and compare it with your project, you will find the error easily.
Download
By downloading the following file, you agree to the license terms
Downloaded 5x (19.83 kB)
Application includes source codes in language Java