Chapter 53 of 77

LinkedList in Java

In the previous chapter, we learned about ArrayList, which stores elements in a resizable array. Java provides another very common list: LinkedList.

From the outside, both look almost the same. You can add(), get(), set(), and remove() elements in both. The difference is how they store the elements inside, and that changes which operations are fast and which are slow.

Imagine a train. Each coach is connected to the coach in front of it and the coach behind it. Adding a coach at the front or the back is easy: just attach it. But to reach the 10th coach, you have to walk through the first nine. A LinkedList works exactly like this train.

How a LinkedList Stores Data

A LinkedList stores each element in a separate node. Each node holds the value plus links to the previous node and the next node.

Java's LinkedList is a doubly linked list, because every node links in both directions. The list also remembers its first node (head) and last node (tail):

  head                                         tail
   ↓                                            ↓
[ null | Mumbai | • ] ⇄ [ • | Pune | • ] ⇄ [ • | Delhi | null ]
  prev   value   next

Compare this with an ArrayList, which keeps all elements side by side in one array:

index:   0        1      2
       [Mumbai | Pune | Delhi]   ← one continuous block

Because of this structure:

  • Adding or removing at the beginning or end of a LinkedList is very fast: just change a couple of links. Nothing needs to shift.

  • Getting the element at an index is slow: Java must walk node by node from the head (or from the tail, if the index is in the second half) until it reaches that position.

You saw a tiny hand-made version of this idea, with a Node class, in the Inner Classes chapter. Java's LinkedList does all of that work for you.

Creating a LinkedList and Adding Elements

LinkedList is in the java.util package. Along with the usual add(), it has special methods for both ends:

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {

        LinkedList<String> cities = new LinkedList<>();

        cities.add("Pune");          // adds at the end
        cities.add("Delhi");
        cities.addFirst("Mumbai");   // adds at the beginning
        cities.addLast("Chennai");   // adds at the end
        cities.add(2, "Jaipur");     // adds at index 2

        System.out.println(cities);
        System.out.println("First: " + cities.getFirst());
        System.out.println("Last: " + cities.getLast());
        System.out.println("Index 2: " + cities.get(2));

        cities.set(1, "Bengaluru");  // replaces the element at index 1
        System.out.println(cities);
        System.out.println("Size: " + cities.size());
    }
}

Output:

[Mumbai, Pune, Jaipur, Delhi, Chennai]
First: Mumbai
Last: Chennai
Index 2: Jaipur
[Mumbai, Bengaluru, Jaipur, Delhi, Chennai]
Size: 5

Just like ArrayList, a LinkedList keeps elements in insertion order, uses indexes starting at 0, allows duplicate values, and can store null. And just like ArrayList, it stores objects, so for numbers you use LinkedList<Integer>, not LinkedList<int>.

Removing and Searching

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {

        LinkedList<String> cities = new LinkedList<>();
        cities.add("Mumbai");
        cities.add("Pune");
        cities.add("Jaipur");
        cities.add("Delhi");
        cities.add("Chennai");
        cities.add("Kolkata");

        cities.removeFirst();          // removes "Mumbai"
        cities.removeLast();           // removes "Kolkata"
        System.out.println(cities);

        cities.remove(1);              // removes the element at index 1
        cities.remove("Delhi");        // removes the first "Delhi"
        System.out.println(cities);

        System.out.println(cities.contains("Pune"));
        System.out.println(cities.indexOf("Chennai"));
        System.out.println(cities.indexOf("Delhi"));
    }
}

Output:

[Pune, Jaipur, Delhi, Chennai]
[Pune, Chennai]
true
1
-1

Step by step: after removing the first and last elements, the list is [Pune, Jaipur, Delhi, Chennai]. Then remove(1) removes Jaipur (index 1), and remove("Delhi") removes Delhi. indexOf() returns -1 when the value is not found.

Here is a summary of the most useful methods:

Method

What it does

add(e) / addLast(e)

Adds at the end

addFirst(e)

Adds at the beginning

add(index, e)

Inserts at a position

getFirst() / getLast()

Returns the first / last element

get(index) / set(index, e)

Reads / replaces the element at a position

removeFirst() / removeLast()

Removes and returns the first / last element

remove(index) / remove(object)

Removes by position / by value

contains(e) / indexOf(e)

Searches for a value

size() / isEmpty() / clear()

Size, empty check, remove everything

One thing to watch out for: getFirst(), getLast(), removeFirst(), and removeLast() throw a NoSuchElementException if the list is empty. Check isEmpty() first when the list might be empty.

LinkedList also has queue-style methods such as offer(), poll(), and peek(), because it can work as a queue. We will learn those in the Queue, Deque & PriorityQueue chapter.

A Common Trap: remove() with Integers

For a list of Integer, remove() has two versions that are easy to mix up. This applies to ArrayList too:

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {

        LinkedList<Integer> numbers = new LinkedList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);

        numbers.remove(1);                    // removes INDEX 1 (the value 20)
        System.out.println(numbers);

        numbers.remove(Integer.valueOf(10));  // removes the VALUE 10
        System.out.println(numbers);
    }
}

Output:

[10, 30]
[30]

remove(1) passes an int, so Java chooses remove(int index). To remove by value, pass an Integer object, using Integer.valueOf(10).

ArrayList vs LinkedList

This is one of the most frequently asked Java interview questions. Here, n is the number of elements:

Operation

ArrayList

LinkedList

get(i) / set(i, e)

O(1), direct index

O(n), must walk the nodes

Add at the end

O(1) on average (occasionally resizes)

O(1)

Add / remove at the beginning

O(n), all elements shift

O(1)

Add / remove in the middle by index

O(n), elements shift

O(n), walking to the position

contains() / indexOf()

O(n)

O(n)

Memory per element

Low (just the reference in the array)

Higher (a node object with two extra links)

A common myth is that LinkedList is always better for inserting in the middle. Inserting is just a link change, but finding the middle position still takes O(n) steps. In practice, ArrayList is faster for most programs, because computers are very good at reading continuous memory and shifting array elements quickly.

When to use which:

  • Use ArrayList by default, especially when you read elements by index often.

  • Use LinkedList when you mostly add and remove at the beginning or end of the list, such as a history of recent items or a queue.

Program to the List Interface

Both ArrayList and LinkedList implement the List interface. As we learned in the Interfaces chapter, we can use the interface as the variable type:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Main {

    static void printAll(List<String> items) {
        for (String item : items) {
            System.out.print(item + " ");
        }
        System.out.println("(" + items.size() + " items)");
    }

    public static void main(String[] args) {

        List<String> a = new ArrayList<>();
        List<String> b = new LinkedList<>();

        a.add("Red");
        a.add("Green");
        b.add("Red");
        b.add("Green");

        printAll(a);
        printAll(b);
        System.out.println(a.equals(b));
    }
}

Output:

Red Green (2 items)
Red Green (2 items)
true

The method printAll() works with any kind of list. If you later decide to switch from LinkedList to ArrayList, you only change one line: the new expression. Also notice that a.equals(b) is true: two lists are equal if they contain the same elements in the same order, whatever their implementation.

What about addFirst(), getFirst(), and removeLast()? In LinkedList they come from the Deque interface it also implements. Since Java 21, the List interface also has these methods (a feature called sequenced collections), so they work on a List variable too. Before Java 21 (for example, on Java 17), you need a LinkedList variable to call them. Remember that on an ArrayList, addFirst() and removeFirst() are still O(n), because all the other elements must shift.

A Complete Example

Let's build a "Recently Played" list for a music app. New songs go to the front, the oldest song falls off the end, and playing a song again moves it to the front. All of these are operations at the ends of the list, which is exactly where LinkedList shines.

import java.util.LinkedList;

class MusicPlayer {
    private static final int MAX_RECENT = 3;
    private final LinkedList<String> recentlyPlayed = new LinkedList<>();

    void play(String song) {
        System.out.println("Playing: " + song);

        recentlyPlayed.remove(song);       // if already present, move it to the front
        recentlyPlayed.addFirst(song);     // newest song goes to the front

        if (recentlyPlayed.size() > MAX_RECENT) {
            recentlyPlayed.removeLast();   // drop the oldest song
        }
    }

    void showRecent() {
        System.out.println("Recently played: " + recentlyPlayed);
    }
}

class Main {
    public static void main(String[] args) {

        MusicPlayer player = new MusicPlayer();

        player.play("Kesariya");
        player.play("Tum Hi Ho");
        player.play("Naatu Naatu");
        player.showRecent();

        player.play("Apna Bana Le");
        player.showRecent();

        player.play("Tum Hi Ho");
        player.showRecent();
    }
}

Output:

Playing: Kesariya
Playing: Tum Hi Ho
Playing: Naatu Naatu
Recently played: [Naatu Naatu, Tum Hi Ho, Kesariya]
Playing: Apna Bana Le
Recently played: [Apna Bana Le, Naatu Naatu, Tum Hi Ho]
Playing: Tum Hi Ho
Recently played: [Tum Hi Ho, Apna Bana Le, Naatu Naatu]

When "Apna Bana Le" was played, the list had 4 songs, so the oldest one, "Kesariya", was removed from the end. When "Tum Hi Ho" was played again, it was removed from the middle and added back at the front. (remove(song) is still O(n), because it has to search for the song, but our list is tiny.)

Common Mistakes

  • Looping with get(i). In a LinkedList, every get(i) walks from an end of the list, so a for (int i = 0; i < list.size(); i++) loop with get(i) takes O(n²) time. Use the enhanced for loop instead, which moves from node to node in O(n) total.

  • Choosing LinkedList "for faster inserts" without measuring. Unless you insert at the ends, ArrayList is usually faster.

  • Calling getFirst() or removeFirst() on an empty list. This throws NoSuchElementException.

  • Mixing up remove(int) and remove(Object) on a list of Integer.

  • Removing elements inside an enhanced for loop. This usually throws a ConcurrentModificationException. We will see the correct way in the Iterator chapter.

Interview Tips

  • Is Java's LinkedList singly or doubly linked? Doubly linked: each node has prev and next links.

  • Which interfaces does LinkedList implement? List and Deque (and therefore also Queue).

  • Why is get(i) O(n) in a LinkedList? There is no array, so Java must follow links from the head or tail, whichever is closer.

  • Is LinkedList thread-safe? No. Neither is ArrayList.

The Main Idea

LinkedList and ArrayList offer the same List operations but store data differently, so they have different speeds.

ArrayList → fast access by index. LinkedList → fast add and remove at both ends.

Start with ArrayList, and reach for LinkedList when your program mainly works with the front and back of a list.