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 nextCompare this with an ArrayList, which keeps all elements side by side in one array:
index: 0 1 2
[Mumbai | Pune | Delhi] ← one continuous blockBecause of this structure:
Adding or removing at the beginning or end of a
LinkedListis 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: 5Just 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
-1Step 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 |
|---|---|
| Adds at the end |
| Adds at the beginning |
| Inserts at a position |
| Returns the first / last element |
| Reads / replaces the element at a position |
| Removes and returns the first / last element |
| Removes by position / by value |
| Searches for a value |
| 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 |
|---|---|---|
| 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 |
| 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
ArrayListby default, especially when you read elements by index often.Use
LinkedListwhen 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)
trueThe 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, everyget(i)walks from an end of the list, so afor (int i = 0; i < list.size(); i++)loop withget(i)takes O(n²) time. Use the enhancedforloop instead, which moves from node to node in O(n) total.Choosing LinkedList "for faster inserts" without measuring. Unless you insert at the ends,
ArrayListis 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
prevandnextlinks.Which interfaces does LinkedList implement?
ListandDeque(and therefore alsoQueue).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.