Java LinkedList

In the last lesson you learned about ArrayList. Java has another List called the LinkedList, built in a completely different way inside. That structure makes it faster at some jobs and slower at others, so picking the wrong one can quietly slow your program down.

🤔 The problem LinkedList solves

You are handling people standing in a line. New people join the back. The front person keeps getting served and leaving. So you constantly add at one end and remove at the other.

Now picture an ArrayList doing this:

• It keeps everything in one solid block, like seats bolted in a row.
• Removing the front person makes every other person shuffle forward to fill the gap.
• Do that a thousand times a second and the shuffling adds up.

A LinkedList fixes this. It is built so adding or removing at the ends is cheap. The pain is “shuffling everything on every front change”. The cure is “a list that only touches the ends”.

🤔 Two lists, two inner designs

Both ArrayList and LinkedList are Lists, so they share methods like add, get, and remove. The real difference is how they store data inside:

• An ArrayList stores items in one continuous block. Reaching index 5 is instant, but inserting or removing in the middle means shifting every item after it.
• A LinkedList stores items as separate nodes, each holding a value and links to its neighbors. Inserting just relinks a few nodes, but reaching index 5 means walking from the start.

The structure decides what each is fast at. Neither is “better” overall. Let’s picture the LinkedList properly.

🔗 How a LinkedList is built

A LinkedList is a chain of nodes. Think of a train. Each car holds cargo and is coupled to the car in front and behind. A node is one car. It holds its value plus a link to the next node and the previous one. That is why it is called a doubly linked list. Each node points both ways.

This is the picture in memory:

null <- [Alex] <-> [Riya] <-> [Arjun] -> null
         head                   tail

The list keeps a direct grip on two nodes:

• The head is the first node, the front of the line.
• The tail is the last node, the back of the line.
• Nodes can sit anywhere in memory. They only find each other through their links.

So to reach the third item, the list walks from the head following links. That walking is why index access is slow. But to insert a node, it changes just a couple of links. No other car moves. Cheap relinking, slow walking. That is the heart of LinkedList.

🧩 Using a LinkedList as a list

You use a LinkedList almost exactly like an ArrayList, because both are Lists. Import it, create it with a type, and use the methods you already know. This example builds a list of names and reads from it.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        names.add("Alex");
        names.add("Riya");
        names.add("Arjun");

        System.out.println(names.get(1));     // ✅ same get as ArrayList
        System.out.println("Size: " + names.size());
        System.out.println(names);
    }
}

What each line does:

• add("Alex") puts a new node at the back of the chain.
• get(1) walks from the head and returns the second item, Riya.
• size() reports how many nodes are in the chain.
• Printing the list shows all items in order.

This is identical to ArrayList code. Only the type changed. That is the point of the List interface. You can swap one List type for another without rewriting how you call it.

Riya
Size: 3
[Alex, Riya, Arjun]

⚡ Extra methods for the ends

Because LinkedList knows its head and tail directly, it offers methods that work on both ends quickly. These come from a second interface called Deque, meaning “double-ended queue”. A LinkedList implements both List and Deque, so it can act like a list and like a thing you push and pull from either end.

The end methods you will use most:

• addFirst and addLast add a value to the front or the back.
• removeFirst and removeLast take a value off the front or the back.
• getFirst and getLast read the front or back value without removing it.
• peekFirst and peekLast also read the ends, but they return null if the list is empty instead of throwing an error.
• offer adds to the back, and poll removes from the front. These two are the classic queue pair.

This example mixes a few so you can see how the ends behave.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> line = new LinkedList<>();
        line.addLast("First in line");
        line.addLast("Second");
        line.addFirst("VIP");          // ✅ jumps straight to the front

        System.out.println(line.getFirst());   // peek at the front
        line.removeFirst();                     // serve and remove the front
        System.out.println(line);
    }
}

Walking through it:

• addLast puts each name at the back, so the line grows in order.
• addFirst("VIP") slips a name in at the front, ahead of everyone.
• getFirst reads the front item without removing it, here VIP.
• removeFirst serves the front person and drops them.

All these end operations are fast, because LinkedList never shifts other nodes. That is why it is the natural pick for queues and stacks. An ArrayList does the same things, but slower at the front.

VIP
[First in line, Second]

🚦 Using a LinkedList as a queue

A queue is a “first in, first out” line. The first item you add is the first to come out, like people waiting for coffee. LinkedList makes a clean queue, because adding at the back and removing from the front are both cheap. This example models a support desk where the agent always handles the oldest ticket first.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> tickets = new LinkedList<>();

        // ✅ new tickets join the back of the queue
        tickets.offer("Reset password");
        tickets.offer("Refund request");
        tickets.offer("Login error");

        System.out.println("Waiting: " + tickets);

        // ✅ handle tickets oldest first
        while (!tickets.isEmpty()) {
            String next = tickets.poll();   // takes from the front
            System.out.println("Handling: " + next);
        }

        System.out.println("Queue empty? " + tickets.isEmpty());
    }
}

The flow:

• offer adds each ticket to the back of the queue.
• The while loop runs as long as the queue is not empty.
• poll pulls the oldest ticket off the front each time.
• After the loop, the queue is empty, so isEmpty() is true.

“Reset password” came first, so it is handled first. That is first in, first out. You could swap offer/poll for addLast/removeFirst and get the same result. The queue names just read more clearly.

Waiting: [Reset password, Refund request, Login error]
Handling: Reset password
Handling: Refund request
Handling: Login error
Queue empty? true

The same LinkedList can act as a stack too, “last in, first out”. You push with addFirst and pop with removeFirst. One structure, three roles: list, queue, and stack.

⚖️ ArrayList vs LinkedList: which to choose

Match the list to what your program does most. This table lines up the common operations.

The simple guidance:

• Use ArrayList for most cases, especially when you read by index a lot.
• Reach for LinkedList when you do many adds and removes at the front or ends, like a queue or deque.
• In everyday code, ArrayList wins most of the time, because reading by index is common and it is unbeatable at it.

One honest note on the middle. The relinking is fast, but finding the middle node still means walking the chain. So the saving only shows up when you are already sitting at that spot, like while looping with an iterator.

⚠️ Common Mistakes

A few LinkedList slip-ups trip people up again and again.

Using get(i) in a loop and expecting array speed. On a LinkedList, every get(i) starts at the head and walks to position i. So a loop over n items walks again and again, and gets painfully slow as the list grows.

// ❌ Slow on a LinkedList: each get(i) walks from the head
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// ✅ Fast: a for-each walks the chain just once
for (String item : list) {
    System.out.println(item);
}

A for-each loop uses an iterator, so it moves node to node in one pass instead of restarting from the head. Always loop a LinkedList this way.

Choosing LinkedList by default. It is not a smarter ArrayList. It only wins for front and end work. For most everyday code, ArrayList is faster and lighter.

Calling getFirst on a possibly empty list. getFirst and removeFirst throw an exception when the list is empty. If it might be empty, use peekFirst or poll and check for null.

Forgetting the import. You need import java.util.LinkedList; before you can use it. Leaving it out gives a “cannot find symbol” error.

✅ Best Practices

Build these habits and you will rarely pick the wrong list.

• Default to ArrayList. It fits most situations and is fast at reading by index. Only move to LinkedList when you have a clear reason.
• Use LinkedList for queue or deque work. Lots of adding and removing at the ends is exactly its strength.
• Never use index loops on a LinkedList. Prefer a for-each, which walks the chain once.
• Use the queue names when you mean a queue. offer and poll read more clearly than addLast and removeFirst when the list is acting as a queue.
• Program to the List type. Declaring the variable as List<String> instead of LinkedList<String> lets you swap implementations later without touching the rest of your code.
• Prefer peek and poll when the list can be empty. They return null instead of throwing, so your code stays calm.

🧩 What You’ve Learned

Nicely done. Let’s recap LinkedList in plain words.

• ✅ A LinkedList stores items as connected nodes, each linking to the next and previous, like coupled train cars.
• ✅ It is doubly linked, so it can move both forward and backward through the chain.
• ✅ It implements List and Deque, so it works as a list, a queue, or a stack.
• ✅ It is fast at adding and removing at the ends, with helpers like addFirst, addLast, removeFirst, offer, and poll.
• ✅ It is slow at index access, because get(i) has to walk the chain from the head.
• ✅ ArrayList is fast at index access and uses less memory, so it is the better default.
• ✅ Choose LinkedList for queue-like work, ArrayList for most everything else.

🚀 What’s Next?

There is one more classic List worth knowing. The Vector works much like an ArrayList, but it was designed to be thread-safe. Let’s see how it compares and when it still shows up.

Java Vector