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.