Java LinkedList Tutorial with Examples
Tags: beginners, java, coding, learning
Published: 2019-03-04 14:34:00

---
title: Java LinkedList Tutorial with Examples
published: true
description: All the latest Codegym 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.
tags: beginners, java, coding, learning
---
![LinkedList](https://thepracticaldev.s3.amazonaws.com/i/a9xj96a85mays1lbon0u.png)

All the latest CodeGym 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: `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 1](https://codegym.cc/api/1.0/rest/images/10000017/ddb43f41-c7d3-4504-85c3-04f45043744b?size=0)

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 2](https://codegym.cc/api/1.0/rest/images/10000017/9859bb21-3f24-4e34-b033-1931836a7a8f?size=0)

As a result, `str2` and `str1` become linked via the **`next`** and **`previous`** links stored in this nodes of the list:

![LinkedList 3](https://codegym.cc/api/1.0/rest/images/10000061/72466dc5-c916-41d2-9a1a-be26e1b86a29?size=0)

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](https://codegym.cc/quests/lectures/questsyntax.level07.lecture05) 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 4](https://codegym.cc/api/1.0/rest/images/10000017/50c60ece-dd95-49c9-a00b-5092460d057d?size=0)

After changing the internal links, `str2` has been successfully added to the list:

![LinkedList 5](https://codegym.cc/api/1.0/rest/images/10000061/4bdfd57b-29a2-43d7-8592-495953c798a8?size=0)

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 6](https://codegym.cc/api/1.0/rest/images/10000061/6351bbad-4ace-46ef-84e3-fe1b92fd0b56?size=0)

After updating the links, we get the desired result:

![LinkedList 7](https://codegym.cc/api/1.0/rest/images/10000061/315aa18f-7717-4155-9495-612b55f8b374?size=0)

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 Modneo");
       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 Modneo'}, 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. :)

Previously was published on [CodeGym blog](https://codegym.cc/groups/posts/23-linkedlist).