LinkedList

1 The story

Coaches of a train

At the railway yard near Panvel, Riya watches workers add an extra coach to the front of a train. They don't move all 20 coaches; they uncouple the engine, couple the new coach, and couple the engine back. Two links change. That's it.

Riya

Sir, an ArrayList would have shifted all 20 coaches to make room at the front. This is just two couplings!

Arjun Sir

That's exactly how a LinkedList works. Each element sits in a node that knows its previous and next node. Adding at either end, or next to a node you're already standing on, is a couple of pointer changes.

Riya

So LinkedList is always faster?

Arjun Sir

Not at all. To find coach number 15, you have to walk from the engine. An ArrayList jumps there in one step. And every node costs extra memory. Let's see both sides honestly.

2 Definition

What is a LinkedList?

Formal definition (write this in exams)

java.util.LinkedList<E> is a doubly linked list implementation of both the List and Deque interfaces. Each element is stored in a private Node object holding the element and references to the previous and next nodes; the list keeps references to its first and last nodes and its size. Insertion and removal at either end take constant time; access by index takes linear time, traversing from whichever end is closer. It permits duplicates and null, is not synchronised, and its iterators are fail-fast.

In simple words

A chain of small boxes, each pointing both ways. Cheap to add or remove at the ends; slow to jump to the middle.

Words you'll meet in this lesson

NodeA small object: item, prev, next.

Head / firstThe first node; its prev is null.

Tail / lastThe last node; its next is null.

Doubly linkedLinks in both directions, so you can walk forwards or backwards.

TraversalWalking node by node to reach a position.

DequeDouble-ended queue: add/remove at both ends (Lesson 11.1).

LinkedList vs ArrayList

Operation	ArrayList	LinkedList
`get(i)` / `set(i)`	O(1)	O(n) walk
Add/remove at the end	O(1) amortised	O(1)
Add/remove at the front	O(n) shift	O(1)
Add/remove in the middle by index	O(n) shift	O(n) walk, then O(1) relink
Add/remove at the iterator's position	O(n) shift	O(1)
Memory per element	one array slot	a whole node object (item + 2 links + header)

Exam tip: LinkedList implements both List and Deque, so it has get(i) and addFirst/addLast/pollFirst/push/pop. It is a doubly linked list (Java has no built-in singly linked list class). get(i) walks from the nearer end, so it's O(n/2), still O(n).

3 Types and ways to use it

Three ways to use a LinkedList

As a List

add, get(i), remove(i): works, but index access is slow.

List interface

As a queue

offer at the back, poll from the front: both O(1).

FIFO

As a stack

push and pop at the front: O(1).

LIFO

The Deque methods

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> train = new LinkedList<>();
        train.add("S1");
        train.add("S2");
        train.addFirst("ENGINE");             // O(1): new first node
        train.addLast("GUARD");               // O(1): new last node
        System.out.println(train);

        System.out.println(train.getFirst() + " … " + train.getLast());
        train.removeFirst();                  // O(1)
        train.add(1, "PANTRY");               // walks to index 1, then relinks
        System.out.println(train + " size " + train.size());
        System.out.println(train.get(2));     // walks from the nearer end
    }
}

[ENGINE, S1, S2, GUARD] ENGINE … GUARD [S1, PANTRY, S2, GUARD] size 4 S2

Queue and stack in one class

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> tokens = new LinkedList<>();
        tokens.offer("T1");
        tokens.offer("T2");
        System.out.println("Serve " + tokens.poll() + ", next " + tokens.peek());

        Deque<String> undo = new LinkedList<>();
        undo.push("typed A");
        undo.push("typed B");
        System.out.println("Undo " + undo.pop());
    }
}

Serve T1, next T2 Undo typed B

The trap: index loops over a LinkedList

for (int i = 0; i < list.size(); i++) {
    total += list.get(i);      // each get walks from an end: O(n) → the loop is O(n²)
}
for (int x : list) {
    total += x;                // the iterator just follows next links: O(n) total
}

Never loop over a LinkedList with get(i). With 100,000 elements that's billions of node hops. Use for-each or an iterator, which simply follows the next links.

When to choose LinkedList: rarely. For a queue or stack, ArrayDeque is usually faster and uses less memory (the Java docs say so). For a general list, ArrayList. LinkedList shines when you hold an iterator in the middle of a long list and insert or remove there repeatedly, or when you need a List and a Deque in one object.

4 Step by step

What `addFirst` and `get` do inside

An empty list
first and last are both null; size is 0. No array, no nodes.
add("S1"): the first node
A Node{prev=null, item="S1", next=null} is created. Both first and last point to it.
addFirst("ENGINE"): relink, don't shift
A new node is created with next = the old first node. The old first node's prev is set to the new node, and first moves to it. Three reference writes, whatever the list's length.
get(2): walk
node(2) checks whether 2 < size/2. If so, it starts at first and follows next twice; otherwise it starts at last and follows prev. Each hop is a memory read, often a cache miss, because nodes are scattered around the heap.
remove a node: unlink
The neighbours are joined: prev.next = next and next.prev = prev. The removed node is no longer reachable and the garbage collector frees it.

5 See it happen

Nodes linking and unlinking: both views

Left: the list as your code sees it. Right: the node objects on the heap and the first/last references.

A LinkedList is a chain of nodes 6 steps

What you see

Behind the screen

6 Real-world use

LinkedList and linked structures in real systems

The linked-node idea is everywhere, even when the class used isn't java.util.LinkedList.

Watch it with an example: browser back and forward

A browser's history behaves like a doubly linked list with a cursor. Watch Back and Forward follow the prev and next links.

History as linked pages 5 steps

Animated example

1. Browser and app history

Back and forward navigation is a doubly linked idea: each page knows the previous and next one. Undo/redo stacks in editors work the same way.

Back button→node.prev→previous page

2. LRU caches

LinkedHashMap links its entries in a doubly linked list. In access-order mode it moves a used entry to the end in O(1), so the least-recently-used entry is always first: the basis of many caches.

cache.get(k)→unlink + relink at tail→evict from head

3. Editing a long sequence in place

Text editors, playlist editors and route planners that insert and delete at a cursor position repeatedly benefit from linked structures and a ListIterator parked at the cursor.

cursor here→it.add(x)→O(1) insert

4. A frequent code-review finding

Reviewers often replace LinkedList with ArrayList or ArrayDeque after spotting index loops or measuring memory, a quick win in many services.

LinkedList + get(i)→ArrayList→O(n²) → O(n)

Examples are simplified; real browsers and editors use their own data structures.

7 Run the code

A playlist editor with a cursor

import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> playlist = new LinkedList<>();
        playlist.add("Intro");
        playlist.add("Song A");
        playlist.add("Song B");
        playlist.add("Outro");

        // put an ad after every song, using a cursor (ListIterator)
        ListIterator<String> it = playlist.listIterator();
        while (it.hasNext()) {
            String track = it.next();
            if (track.startsWith("Song")) {
                it.add("Ad");                     // O(1): links a node right here
            }
        }
        playlist.removeLast();                    // O(1)
        playlist.addFirst("Welcome");             // O(1)
        System.out.println(playlist);
        System.out.println("Now playing: " + playlist.getFirst());
    }
}

[Welcome, Intro, Song A, Ad, Song B, Ad] Now playing: Welcome

listIterator()A cursor that can move both ways and insert or remove at its position (Lesson 11.7).
it.add("Ad")Inserts after the current song by relinking two nodes: no shifting.
removeLast() / addFirst()The ends are always O(1) thanks to first and last.
No get(i) anywhereThat's how LinkedList should be used.

8 Line by line

The chain on the heap

This trace is recorded from the real JVM. The heap line shows the list's chain of elements (⇄ means linked both ways). Watch additions at the front and back, and a removal at the front: the other elements never move.

Worked examples: real problems, solved and traced in memory

Three tasks where LinkedList's ends and its List/Deque double life are useful, traced on the real JVM.

Example 1Customer service · deque

VIP tickets jump the queue

Problem statement

A support desk serves tickets in order, but VIP tickets go to the front. Tickets: T1, T2, VIP1, T3. Print the serving order.

Input

T1, T2, VIP1, T3

Expected output

VIP1 T1 T2 T3

Approach

Use a LinkedList as a Deque.
A helper arrive(desk, id): VIP tickets with addFirst, others with addLast.
Serve with pollFirst until empty.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 2Text editing · undo

Undo the last two edits

Problem statement

An editor records edits on a stack. After typing "Hello", " World" and "!", the user presses Undo twice. Print the text left.

Input

edits: Hello, ␠World, !; undo × 2

Expected output

Text: Hello

Approach

Push each edit with push (adds at the front).
Undo = pop, which removes the most recent edit.
Rebuild the text from the remaining edits, oldest first, using descendingIterator.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 3Logistics · route

Add a stop after a given stop

Problem statement

A delivery route is [Depot, Kharghar, Vashi, Depot]. Insert "Belapur" right after "Kharghar" using a ListIterator, without indexes.

Input

route, insert Belapur after Kharghar

Expected output

[Depot, Kharghar, Belapur, Vashi, Depot]

Approach

Walk the route with a ListIterator.
When the current stop is Kharghar, call it.add("Belapur"): an O(1) relink at the cursor.
Stop after inserting and print the route.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

9 Quiz and revision

Check yourself

Quick revision

Lesson 11.4 in one screen

LinkedList = doubly linked list of Node{prev, item, next} with first, last, size.
Implements List and Deque: get(i), addFirst/addLast, offer/poll, push/pop.
O(1): add/remove at either end, and at an iterator's position. O(n): get(i), set(i), contains.
Never loop with get(i) (O(n²)); use for-each or an iterator.
More memory per element than ArrayList; scattered nodes are slower to walk.
Usually prefer ArrayList (lists) and ArrayDeque (queues/stacks).

Interview and viva questions

ArrayList vs LinkedList: when would you use each?

ArrayList for most lists: O(1) random access, compact memory, fast iteration. LinkedList when you insert/remove at the ends or at an iterator's position very often and rarely access by index, or when you need List and Deque behaviour in one object. In practice ArrayList (or ArrayDeque) wins most benchmarks because arrays are cache-friendly.

How does LinkedList.get(index) work?

It calls node(index): if the index is in the first half, it starts at first and follows next; otherwise it starts at last and follows prev. So at most n/2 hops, which is still O(n).

Is inserting in the middle of a LinkedList O(1)?

Only if you already have a reference to the position (an iterator there). add(i, x) by index first walks to position i (O(n)), then relinks (O(1)).

Can LinkedList hold null? Is it thread-safe?

It allows nulls (though using null in a queue makes poll()'s null return ambiguous). It isn't thread-safe; use ConcurrentLinkedQueue/ConcurrentLinkedDeque or a BlockingQueue for concurrent work.

How would you reverse a linked list?

With Collections.reverse(list), or, in the classic interview version with your own singly linked nodes, by walking the list once and flipping each node's next pointer to the previous node, keeping three references: prev, current, next. O(n) time, O(1) extra space.

Practice problems

Use LinkedList through its List and Deque methods, and avoid its traps. The last three are business tasks.

P1Easy

Both ends

Start with [2, 3], add 1 at the front and 4 at the back, then print the first and last elements.

Input

[2, 3]

Expected output

[1, 2, 3, 4] first 1 last 4

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> l = new LinkedList<>(List.of(2, 3));
        l.addFirst(1);
        l.addLast(4);
        System.out.println(l + " first " + l.getFirst() + " last " + l.getLast());
    }
}

[1, 2, 3, 4] first 1 last 4

How it works: the list keeps direct references to its first and last nodes, so all four calls are O(1).

P2Easy

Safe peek on an empty list

Print the next ticket of an empty queue without crashing, then add one and peek again.

Input

empty, then T9

Expected output

Next: null
Next: T9

Show solution and explanation

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> q = new LinkedList<>();
        System.out.println("Next: " + q.peekFirst());
        q.offer("T9");
        System.out.println("Next: " + q.peekFirst());
    }
}

Next: null Next: T9

How it works: peekFirst returns null for an empty list; getFirst would throw NoSuchElementException.

P3Easy

Iterate backwards

Print the stations [Panvel, Kharghar, Belapur, Vashi] in reverse using descendingIterator.

Input

4 stations

Expected output

Vashi Belapur Kharghar Panvel

Show solution and explanation

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> st = new LinkedList<>(List.of("Panvel", "Kharghar", "Belapur", "Vashi"));
        Iterator<String> it = st.descendingIterator();
        while (it.hasNext()) System.out.print(it.next() + " ");
        System.out.println();
    }
}

Vashi Belapur Kharghar Panvel

How it works: the iterator starts at last and follows the prev links, possible because the list is doubly linked.

P4Medium

Rotate a list by one

Move the first element to the end three times: [A, B, C, D] → ?

Input

[A, B, C, D], 3 rotations

Expected output

[D, A, B, C]

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        LinkedList<String> l = new LinkedList<>(List.of("A", "B", "C", "D"));
        for (int i = 0; i < 3; i++) {
            l.addLast(l.removeFirst());
        }
        System.out.println(l);
    }
}

[D, A, B, C]

How it works: each rotation is two O(1) operations at the ends. On an ArrayList, removing the first element would shift everything.

P5Medium

Remove every other element

Remove elements at odd positions from [10, 11, 12, 13, 14] with an iterator.

Input

[10, 11, 12, 13, 14]

Expected output

[10, 12, 14]

Show solution and explanation

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> l = new LinkedList<>(List.of(10, 11, 12, 13, 14));
        Iterator<Integer> it = l.iterator();
        int pos = 0;
        while (it.hasNext()) {
            it.next();
            if (pos % 2 == 1) it.remove();
            pos++;
        }
        System.out.println(l);
    }
}

[10, 12, 14]

How it works: it.remove() unlinks the current node in O(1) and keeps the iterator valid. No ConcurrentModificationException.

P6Business problem

Last 3 notifications

A phone shows only the 3 most recent notifications, newest first. Add N1…N5 and print what's shown.

Input

N1, N2, N3, N4, N5

Expected output

[N5, N4, N3]

Show solution and explanation

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> shown = new LinkedList<>();
        for (int i = 1; i <= 5; i++) {
            shown.addFirst("N" + i);
            if (shown.size() > 3) shown.removeLast();
        }
        System.out.println(shown);
    }
}

[N5, N4, N3]

How it works: new items go to the front; the oldest drops off the back. Both ends are O(1).

P7Business problem

Token desk with no-shows

Tokens T1–T4 wait. T2 doesn't show up and is skipped (sent to the back once). Print the serving order.

Input

T1, T2(no-show once), T3, T4

Expected output

T1 T3 T4 T2

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        LinkedList<String> q = new LinkedList<>(List.of("T1", "T2", "T3", "T4"));
        boolean t2Skipped = false;
        StringBuilder served = new StringBuilder();
        while (!q.isEmpty()) {
            String t = q.pollFirst();
            if (t.equals("T2") && !t2Skipped) {
                t2Skipped = true;
                q.addLast(t);          // try again later
                continue;
            }
            served.append(t).append(" ");
        }
        System.out.println(served.toString().trim());
    }
}

T1 T3 T4 T2

How it works: a skipped token is moved from the front to the back in O(1), and served on its second turn.

P8Business problem

Merge two sorted delivery lists

Two drivers have delivery times sorted: [9, 12, 15] and [10, 11, 16]. Merge them into one sorted list.

Input

[9, 12, 15], [10, 11, 16]

Expected output

[9, 10, 11, 12, 15, 16]

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> a = new LinkedList<>(List.of(9, 12, 15));
        LinkedList<Integer> b = new LinkedList<>(List.of(10, 11, 16));
        LinkedList<Integer> merged = new LinkedList<>();
        while (!a.isEmpty() && !b.isEmpty()) {
            merged.addLast(a.peekFirst() <= b.peekFirst() ? a.pollFirst() : b.pollFirst());
        }
        merged.addAll(a);
        merged.addAll(b);
        System.out.println(merged);
    }
}

[9, 10, 11, 12, 15, 16]

How it works: always take the smaller front element; every step is O(1) at the ends, so the merge is O(n + m).

Real-world scenario questions (asked in company interviews)

LinkedList questions in interviews often test whether you can resist the textbook answer and reason about real costs.

Backend · code reviewFresher

“LinkedList because we insert a lot”

A teammate chose LinkedList for a list of 200,000 transactions “because we insert a lot”. Inserts are always at the end, and the screen reads rows by index for paging. What do you say?

The interviewer is checking: matching the data structure to the actual access pattern.

Show a strong answer

Appending is O(1) amortised on ArrayList too, so LinkedList brings no benefit for these inserts.
Paging uses get(i)/subList, which is O(n) per access on LinkedList but O(1) on ArrayList.
LinkedList also costs much more memory per element (a node object each). Switch to ArrayList and measure.

Avoid: “LinkedList is always better for inserts.” Only inserts at the front or at an iterator's position are cheaper.

Ride-hailing · queueJunior

Pending ride requests

A service keeps pending ride requests in a queue: new ones at the back, drivers take from the front, sometimes a request is cancelled from the middle. LinkedList, ArrayDeque or something else?

The interviewer is checking: trade-offs between deque implementations.

Show a strong answer

For offer/poll alone, ArrayDeque is the best fit: O(1) and compact.
Cancelling from the middle is O(n) in both. If cancellations are frequent, keep a LinkedHashMap<RequestId, Request>: O(1) removal by ID and insertion-order iteration for “oldest first”.
If several threads take requests, use a concurrent queue (Module 12).

Avoid: picking LinkedList only because it has remove(Object). It still searches linearly.

Classic DSAFresher

Find the middle in one pass

Given the head of a singly linked list of unknown length, return its middle node in one pass without counting first.

The interviewer is checking: the slow/fast pointer technique.

Show a strong answer

Two references start at the head: slow moves one node, fast moves two nodes per step.
When fast reaches the end (null or last node), slow is at the middle. O(n) time, O(1) space.
The same idea detects cycles (if fast ever meets slow, there's a loop).

Avoid: copying the nodes into an ArrayList. It works, but uses O(n) extra memory and misses the point of the question.

Caching · designMid

Build an LRU cache

Design a cache of fixed capacity where get and put are O(1) and the least-recently-used entry is evicted when full.

The interviewer is checking: combining a hash map with a doubly linked list.

Show a strong answer

A HashMap from key to node for O(1) lookup, plus a doubly linked list ordered by recency: move a node to the tail on every access, evict from the head.
In Java, LinkedHashMap with accessOrder = true and an overridden removeEldestEntry gives exactly this in a few lines.
For multi-threaded use, add locking or use a library cache.

Avoid: a plain list scanned for the oldest entry: O(n) per operation.

Coaches of a train

What is a LinkedList?

Words you'll meet in this lesson

LinkedList vs ArrayList

Three ways to use a LinkedList

As a List

As a queue

As a stack

The Deque methods

Queue and stack in one class

The trap: index loops over a LinkedList

What addFirst and get do inside

An empty list

add("S1"): the first node

addFirst("ENGINE"): relink, don't shift

get(2): walk

remove a node: unlink

Nodes linking and unlinking: both views

LinkedList and linked structures in real systems

Watch it with an example: browser back and forward

1. Browser and app history

2. LRU caches

3. Editing a long sequence in place

4. A frequent code-review finding

A playlist editor with a cursor

The chain on the heap

Worked examples: real problems, solved and traced in memory

VIP tickets jump the queue

Undo the last two edits

Add a stop after a given stop

Check yourself

Quick revision

Lesson 11.4 in one screen

Interview and viva questions

Practice problems

Both ends

Safe peek on an empty list

Iterate backwards

Rotate a list by one

Remove every other element

Last 3 notifications

Token desk with no-shows

Merge two sorted delivery lists

Real-world scenario questions (asked in company interviews)

“LinkedList because we insert a lot”

Pending ride requests

Find the middle in one pass

Build an LRU cache

What `addFirst` and `get` do inside