LinkedList

What if objects were linked together?

Let's move on to the next, quite interesting data structure - LinkedList.

Let's look at the syntax and the operation scheme of LinkedList:

As you can see, the syntax is absolutely identical to declaring an ArrayList. In general, any list can be declared in this way.

But the interesting part begins when we try to understand how LinkedList works.

How is LinkedList structured?

Inside, LinkedList works with Nodes. A Node is an object that is stored inside LinkedList. It is implemented inside LinkedList like this:

main


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Let's break down what this class consists of. First, we need to answer the main question that arises: What does <E> mean? This is a generic. In simple terms, here, we leave a placeholder for the data type that will be specified during initialization. We use this placeholder in the code, which the user's specified data type will later replace.

This can be compared to overloading.

Let's see how it works:

So, instead of overloading this method for each data type, we use a generic into which we insert the data type the method will work with. The letter E will simply be replaced with the required data type. In our case, it's Integer.

Next, let's pay attention to the E item field. This is the object's value that will be stored in this Node. So, if we create a list like {0, 1, 2, 3}, the first node will store item 0, the second node will store item 1, and so on.

Next, we see references to other Node objects: Node<E> next and Node<E> prev. This is the main feature of a linked list. In one Node, there is a reference to the next Node and the previous one. This is how we iterate through the list. Let's take a closer look at the iteration through a LinkedList.

Looking at such a scheme, we can conclude that iterating through such a list will work a bit differently. In ArrayList<>(), under the hood, the program uses an array that doubles in size when the number of elements takes up 3/4 of the array's size. In a LinkedList<>(), we don't need to recreate an array because there is no array in a LinkedList. Instead, a new Node object will be created when adding a new element, linked by references to the old last element.

I understand it looks and sounds a bit complicated, but you won't have to set all this up as a programmer. The methods for LinkedList are the same as those for ArrayList because they both inherit from the List interface, which defines the methods that all its descendants must implement.

So, why do we need to know about different types of lists?

The answer is:

Algorithmic Complexity

In the Collection framework, there are many different data structures, and each of them has its algorithmic complexity.

Algorithmic complexity is denoted using big O notation (e.g., O(n), O(n^2)), where "O" stands for "big O" and indicates an upper bound on the growth of the running time as a function of the input size. Here are the main types of algorithmic complexity:

O(1) (constant time): Time complexity does not depend on the size of the input data. For example, accessing an element in an array by index;
O(log n) (logarithmic time): Time complexity grows logarithmically with the size of the input data. Example: binary search in a sorted array;
O(n) (linear time): Time complexity grows linearly with the size of the input data. Example: iterating through all elements in an ArrayList;
O(n^2) (quadratic time): Time complexity is proportional to the square of the size of the input data. Example: bubble sort.

These are basic categories, and there are many other types of algorithmic complexity, such as O(n log n), O(2^n), O(n!), and others, characterizing more complex algorithms. Choosing an efficient algorithm, considering its complexity, is a crucial aspect of software development.

Now, let's return to data structures in Java. Each data structure has its algorithmic time complexity depending on the operation that needs to be performed. Let's take a look at the table:

Note

As you can see in this table, we will explore many other data structures later. For now, you should take a look at ArrayList and LinkedList.

You can see that searching for an element by index in ArrayList has constant complexity since we simply access the index in the array.

Meanwhile, in LinkedList, searching by index takes much more time because we have to traverse all the nodes and find the object we need by index.

On the other hand, if you look at the insertion of an element, LinkedList has constant complexity, while ArrayList has linear complexity. This happens because to insert an element into a LinkedList, we just need to change the links in the nodes to new ones, inserting the element between them. For ArrayList, we need to recreate the array with the new element, which involves copying the old array and inserting the element, taking much more time.

Let's look at an example:

main


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

We created two lists: one is an ArrayList, and the other is a LinkedList. Then, we populated them with 1,000,000 random integers. The lists have the same contents, each containing a million numbers from 1 to 100.

Next, we measured the time it takes to add an element at the thousandth index with the value 50. We used the System.nanoTime() method to measure time, which shows the current time in nanoseconds. Then, for each list, we subtracted the start time from the end time, thus determining how much time was spent adding an element to the middle of the list.

You can see that the LinkedList performed significantly faster, as evident in the table. LinkedList has constant algorithmic complexity, while ArrayList has linear complexity.

This is why we need different types of lists. If your project deals with a large amount of data where optimization is crucial, reconsidering which type of list the program will perform faster in certain cases is worthwhile. But I'll tell you a secret: I almost always use ArrayList.

SinglyLinkedList

There is another undisclosed data structure called SinglyLinkedList. As the name suggests, this data structure uses iteration in only one direction. While the LinkedList class Node has fields: item, next, and prev, the SinglyLinkedList class Node has only 2 fields: item and next.

main


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

This data structure is used in structures such as maps, where iteration is needed in only one direction. We will learn about maps, especially HashMap, in future sections. In the next chapter, we will write an implementation of SinglyLinkedList to better understand how this interesting data structure works.

1. Which data structure will perform faster if we want to find an element by index?

2. Which data structure will perform faster when performing a deletion operation?

3. How does the `Node` class participate in the operation of `LinkedList`?

Everything was clear?

Thanks for your feedback!

Section 1. Chapter 5