I’ve seen this mistake more times than I can count in code reviews: a developer decides they need to do a lot of insertions and deletions, remembers a sentence from a CS101 textbook about LinkedList being "faster" for these operations, and swaps out their ArrayList. Then, the application slows to a crawl as the dataset grows. They're baffled because they did exactly what the textbook said.

The problem is that "faster" in a theoretical sense doesn't always translate to "faster" in a real-world JVM. To understand why, we need to look at how these two actually behave when you're treating them like a list.

The Trap of Index-Based Access

Imagine you're building a system to manage a queue of players in a competitive game lobby. You need to occasionally remove a player from the middle of the list when they disconnect. If you use a LinkedList, you might write something like this:

List<Player> lobby = new LinkedList<>();
// ... add players ...
for (int i = 0; i < lobby.size(); i++) {
    if (lobby.get(i).hasDisconnected()) {
        lobby.remove(i);
    }
}

On paper, LinkedList.remove() is O(1). But look closely at that lobby.get(i) call. A LinkedList isn't a contiguous block of memory; it's a chain of nodes. To get to the 500th element, Java has to start at the first node and follow the "next" pointer 499 times. By putting get(i) inside a loop, you've accidentally turned a linear operation into an O(n²) nightmare. You're walking the entire chain over and over again.

The Hidden Cost of Shifting

Now, let's look at the ArrayList. It's just a wrapper around a standard array. When you remove an element from the middle, Java has to shift every single element to the right of that gap one position to the left to keep the array contiguous. That sounds expensive—and it is. It's O(n).

But here is the secret: moving a block of memory (via System.arraycopy) is incredibly fast on modern hardware. Because ArrayList elements are right next to each other in memory, the CPU can use its cache effectively. A LinkedList, however, scatters its nodes all over the heap. Every time you follow a pointer to the next node, you're risking a "cache miss," which forces the CPU to wait for the slower main RAM.

When the Linked List Actually Wins

I'm not telling you LinkedList is useless; I'm telling you it's specialized. The only time I actually reach for a LinkedList is when I'm using it as a Queue or a Deque. If you are exclusively adding and removing from the very beginning or the very end of the list, LinkedList is great because it just updates two pointers and calls it a day.

If you find yourself needing to remove elements from the middle of a LinkedList, you must use an Iterator. An iterator keeps a reference to the current node, so the "removal" is truly O(1) because you're already standing at the spot that needs to be deleted. If you aren't using an iterator, you should probably just be using an ArrayList.

The Rule of Thumb

If you're undecided, just use ArrayList. It is the default for a reason. It's leaner on memory (no node objects), faster for reading, and surprisingly competitive for writes until your lists become massive. Only switch to LinkedList if you have a proven bottleneck and your access pattern is strictly "head" or "tail" operations.

📋 Practical Task

Refactoring the Music Playlist Shuffler

You have been handed a piece of code for a music app. The current implementation uses a LinkedList to store a playlist of songs. The developer tried to implement a "Clean Up" feature that removes songs that have been flagged as "unavailable" from the middle of the list. However, as the playlist grows to thousands of songs, the app freezes.

The Code:

List<Song> playlist = new LinkedList<>(); 
// Assume playlist is populated with thousands of songs

for (int i = 0; i < playlist.size(); i++) {
    if (playlist.get(i).isUnavailable()) {
        playlist.remove(i);
        i--; // adjust index after removal
    }
}

Your Task:

1. Rewrite this logic to fix the performance bottleneck. You have two choices: either change the List implementation to the more appropriate one for this access pattern, OR rewrite the loop to use an Iterator to maintain the LinkedList's efficiency.
2. Explain in a brief comment why your chosen solution prevents the "walking the chain" problem described in the lesson.