User Vasyl Malik
Vasyl Malik
Senior Java Developer at CodeGym

LinkedList

Published in the Java Developer group
Hi! All the latest lessons have been devoted to ArrayList. This data structure is very convenient and useful. It can handle plenty of tasks. But Java has lots of other data structures.
LinkedList - 1
Why? Above all, because the range of tasks is enormous, and the most efficient data structures are different for different tasks. Today we'll meet a new structure: LinkedList, a doubly-linked list. Let's see how it's organized, why it's called doubly-linked, how it differs from ArrayList. The elements in a LinkedList are actually links in a single chain. In addition to data, each element stores references to the previous and next elements. These references let you move from one element to another. This is how you create one:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}
Output: [Hello World! My name is Earl, I love Java, I live in Canada] Here's what our list looks like: LinkedList - 2 Let's see how to add a new element. This is done using the add() method.

earlBio.add(str2);
At the point in the code, our list consists of one element: the String str1. Let's see what happens next in the picture: LinkedList - 3 As a result, str2 and str1 become linked via the next and previous links stored in this nodes of the list: LinkedList - 4 Now you should understand the main idea of a doubly-linked list. This chain of links is precisely what makes LinkedList elements a single list. Unlike ArrayList, LinkedList doesn't have an array or anything array-like inside. Any (well, most) work with ArrayList boils down to working with the internal array. Any work with LinkedList boils down to changing links. This can be seen very clearly by adding an element to the middle of the list:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}
As you can see, the overloaded add() method lets you specify a specific index for a new item. In this case, we want to add String str2 between str1 and str3. This is what will happen internally: LinkedList - 5 After changing the internal links, str2 has been successfully added to the list: LinkedList - 6 Now all 3 elements are connected. You can move via the next link from the first element on the chain to the last and back again. So, we're fairly comfortable with insertion, but what about removing elements? The principle is exactly the same. We just update the links in the two elements "to the left and the right" of the element being removed:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}
Here's what happens if we delete the item with index 1 (it's in the middle of the list): LinkedList - 7 After updating the links, we get the desired result: LinkedList - 8 Unlike the removal operation in ArrayList, here there is no need to shift array elements or do anything of the kind. We just update the links for str1 and str3. They now point to each other, and str2 has "dropped out" of the chain of links and is no longer part of the list.

Overview of methods

LinkedList has a lot of methods in common with ArrayList. For example, both classes have methods such as add(), remove(), indexOf(), clear(), contains() (indicates whether an item is in the list), set() (replaces an existing element), and size(). Although many of them work differently internally (as we found with add() and remove()), the end result is the same. However, LinkedList does have separate methods for working with the beginning and end of the list, which ArrayList does not have:
  • addFirst(), addLast(): These methods for adding an element to the beginning/end of the list

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}
Output: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] [Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] We end up with "Ford" at the top of the list, and "Fiat" at the end.
  • peekFirst(), peekLast(): The methods return the first/last element in the list. They return null if the list is empty.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}
Output: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'}
  • pollFirst(), pollLast(): These methods return the first/last element in the list and remove it from the list. They return null if the list is empty

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}
Output: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} What's left on the list? [Car{model='Bugatti Veyron'}]
  • toArray(): This method returns an array containing the list items

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}
Output: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Now we know how LinkedList works and how its organization differs from ArrayList. What are the benefits of using LinkedList? Above all, we benefit when working in the middle of the list. Insertion and removal operations in the middle of a LinkedList are much simpler than in an ArrayList. We simply update the links of neighboring elements, and the unwanted element "drops out" of the chain of links. But in an ArrayList, we must
  • check whether there is enough space (when inserting)
  • if not, then we create a new array and copy the data there (when inserting)
  • we remove/insert the element, and move all the other elements to the right/left (depending on the type of operation). And the complexity of this process depends heavily on the size of the list. It's one thing to copy/move 10 elements, and quite another to do the same with a million elements.
In other words, if your program insertion/removal operations in the middle of the list are most common in your program, LinkedList should be faster than ArrayList.

In theory


public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}
Output: Time taken by LinkedList (in milliseconds) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}
Output: Time taken by ArrayList (in milliseconds) = 181 That was unexpected! We performed an operation where LinkedList should be much more efficient: inserting 100 items in the middle of a list. And our list is huge: 5,000,000 elements. ArrayList had to shift a couple of million items with every insertion! How did it win? First, the time required for ArrayList to access elements is fixed (constant). When you write

list.add(2_000_000, new Integer(Integer.MAX_VALUE));
then ArrayList [2_000_000] is a specific memory address (after all, the list has an internal array). But, a LinkedList does not have an array. It will search for element number 2_000_000 along the chain of links. For LinkedList, this is not a memory address, but a link that still needs to be reached: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… As a result, during each insertion (removal) in the middle of the list, ArrayList already knows the exact memory address to access, but LinkedList still needs to "get there". Second, there is the structure of the ArrayList itself. A special internal function (System.arrayCopy()) expands the internal array, and copies and shifts all the elements. It is very fast, because it is optimized for this specific work. But when you don't have to "get to" a particular index, LinkedList is the winner. Suppose we insert at the very beginning of the list. Let's try inserting a million elements there:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}
Output: The result in milliseconds: 43448 The result in milliseconds: 107 Now we get an entirely different result! ArrayList spent more than 43 seconds inserting a million items at the front of the list took, while LinkedList managed to do it in 0.1 seconds! LinkedList benefited here, because it did not have to run through the chain of links to the middle of the list every time. It immediately finds the needed index at the beginning of the list, so the different algorithm is already an advantage. :) In fact, the "ArrayList versus LinkedList" discussion is very widespread, and we won't dive deep into it at the current level. The main thing that you need to remember is this:
  • Not all of the theoretical advantages any particular collection always work in reality (we saw this with the example involving the middle of the list)
  • Don't adopt an extreme position when it comes to choosing a collection ("ArrayList is always faster. Use it and you can't go wrong. Nobody has been using LinkedList for a long time").
Although even LinkedList's author, Joshua Bloch, says this is the case. :) Still, this perspective is far from 100% correct, and we've convinced ourselves of this. In our previous example, LinkedList was 400 (!) times faster. Another thing is that there really are few situations where LinkedList is the best choice. But they do exist, and at the right moment LinkedList can reward you handsomely. Don't forget what we said at the beginning of the lesson: the most efficient data structures are different for different tasks. It's impossible to be 100% sure which data structure will be best until you know all the conditions of your task. You'll know more about these collections later, which will make the choice easier. But the simplest and most effective option is always the same: try both on the actual data used in your program. Then you will be able to see for yourself how both types of lists perform and you definitely won't go wrong. :)

More reading:

Comments (30)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
Sakka Mouid Level 19, Hannover, Deutschland
23 March 2022
i really don´t get here . I need help ! In the previous lessons we learned that in the add() function LinkedList are faster . Now we see the opposite!
Jonaskinny Level 25, Redondo Beach, United States
20 February 2022
Caching is a candidate for LinkedList, particularly if you are replacing items in the cache (like Least Recently Used aka LRU)
Martin Steinmassl Level 11, Feldkirch, Germany
8 April 2021
When to insert elements in the middle of a List? I do not know a convenient example.
TaoLu Level 20, 泾县, China
12 March 2021
Hello
Andrei Level 41
5 November 2020
Please correct the output for "System.out.println(earlBio);" in the first code bit, it is not "[Hello World! My name is Earl, I love Java, I live in Canada]" . Or so I believe.
Jonathan Level 12, Esslingen, Germany
19 October 2020
I've got one question: does this make a difference?: 1.

String s = "Hello";
2. String s = new String("Hello");
Agent Smith Level 38
17 August 2020
If you are curious about this notation:

5_000_000
It is the same as:

5000000
It just improves readability. Underscores are ignored by the Java compiler in such context. You can place underscores only between digits, but you cannot place underscores in the following places: 1) At the beginning or end of a number. 2) Adjacent to a decimal point in a floating point literal. 3) Prior to an F or L suffix. 4) In positions where a string of digits is expected. Underscores in Numeric Literals (Oracle Java Documentation)
Pawel Level 22, Austin, TX, USA
21 March 2020
First example output should be Output:

[Hello World!, My name is Earl, I love Java, I live in Canada]
"Hello World!" and "My name is Earl" are separate strings
Fadi Alsaidi Level 31, Carrollton, TX, USA
1 December 2019
is this suppose to be smaller than 5 million? I don't get those underscores? i < 5_000_000
Siaro Level 8, Prague, Czech Republic
1 October 2019
Output for first example is incorrect, the correct one: [Hello World!, My name is Earl, I love Java, I live in Canada]