Author
Vasyl Malik
Senior Java Developer at CodeGym

Java LinkedList

Published in the Java Collections group
members
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. 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: Java LinkedList, a doubly-linked list.
LinkedList - 1
Let's see how it's organized, why it's called doubly-linked, how it differs from ArrayList. The elements in a Java 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 Java 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 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. :)To reinforce what you learned, we suggest you watch a video lesson from our Java Course

More reading:

Comments (34)
  • Popular
  • New
  • Old
You must be signed in to leave a comment
Andreas Blank
Level 8 , Germany, Germany
17 May 2023, 11:30
I wonder why in in level 8 lesson 5 in the summary it is clearly said that linked list would be the better choice over arraylist when you need to frequently insert data in the middle of the collection. This article says the contrary and gives good explanation and testing for it. So, I assume the info from this article is right, while the info from level 8 lesson 5 was a mistake!
Fadhil Radhian Software Engineer at Accenture
27 March 2023, 06:23
Interesting insight
Vadim “迪姆哥”
Level 35 , Kazakhstan
24 October 2022, 16:07
One important addition down here. LinkedList could perform better insertion in the middle of the list, if you will insert with ListIterator. For example, lets fill List with 10_000_000 elements, then try to insert 100 new elements in the middle of the List. Results without ListIterator, will be:
The result of java.util.ArrayList in milliseconds: 286 ms
The result of java.util.LinkedList in milliseconds: 2943 ms
Then with ListIterator.add method, results will be:
The result of java.util.ArrayList in milliseconds: 284 ms
The result of java.util.LinkedList in milliseconds: 32 ms
So, When using ListIterator, LinkedList wins arrayList in both - inserting in the middle, or inserting at the beginning....
Vadim “迪姆哥”
Level 35 , Kazakhstan
24 October 2022, 16:10
for whom want to try it by them own, insertion in middle of List with using ListIterator will be:
public static void insertValues(List list) {
    int half = list.size() / 2;
    var iterator = list.listIterator(half);
    for (int i = 0; i < 100; i++) {
        iterator.add(i);
    }
}
Sakka Mouid
Level 19 , Hannover, Deutschland
23 March 2022, 00:53
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!
5 June 2022, 18:22
It's because when they were adding to the LinkedList in this article they were inserting it in the middle of the list so the LinkedLast had to use Node.next hundreds of times to first get to the place that it would be inserted at, where as the ArrayList knows exactly in memory where it is since it has an internal array.
Jonaskinny Java Developer at Sandmedia
20 February 2022, 03:00
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, 14:20
When to insert elements in the middle of a List? I do not know a convenient example.
TaoLu
Level 20 , 泾县, China
12 March 2021, 07:31
Hello
Andrei
Level 41
5 November 2020, 10:23
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, 14:22
I've got one question: does this make a difference?: 1.
String s = "Hello";
2. String s = new String("Hello");
Anonymous #10615509
Level 5
Expert
9 November 2020, 21:24
Hey, Yes there is a Diffrent in String s = "Hello" ; Your word Hello go into a pool of constant with strings in it, when your create another string with the same content, you make a ref on the "Hello" Object String in the pool. And in case you make a String like Option 2. you create each time a Object of string whatever is inside. for e.x Option 1 String a = "Hello" ; you think you create 2 objects String b = "Hello"; but What really happend is -------------------------- String b = a ; Option 2 String a = new String("Hello"); first object String b = new String("Hello"); Second object German: Jedes mal wenn du ein String mit der new methode erstellst wird ein neues Sring objekt erstellt was auch immer deren Inhalt ist. Ohne dem new wird einmal ein String Objekt erstellt und der Inhalt wird in einen sogenannten String Pool geschmissen jedes mal wenn du dann einen String ohne new erstellst wird im pool nach einem String geguckt ob es diesen schon gibt. zum beispiel dein code beinhaltet 10 x String s = "Hello "{s ändert sich natürlich ;-) } somit hast du nur ein String Objekt aber 9 Referenzen auf dieses. if I am wrong improves me
Khongpak Phupkdee
Level 15 , Chiangrai, Thailand
8 May 2021, 02:01
It different at pool address
Jonaskinny Java Developer at Sandmedia
20 February 2022, 02:59
See String.intern() re String pool vs Heap
Agent Smith
Level 38
17 August 2020, 15:38
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)
Andrei
Level 41
5 November 2020, 10:33
Nice, thank you!