Java Collections

LinkedList

Complete lesson for LinkedList using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with Java OOP and Collections where relevant.

Basics — LinkedList

Section: Java Collections. LinkedList as a doubly linked list and Deque — complexity, node cost, and when not to use it.

A doubly linked list that implements List and Deque

Each node stores prev, item, next. There is no random-access array.
get(i) walks from the nearer end — O(n). addFirst / addLast / removeFirst / removeLast are O(1).
Because it implements Deque, you can use it as a stack or queue — but ArrayDeque is usually faster.

import java.util.LinkedList;

public class LinkedListBasics {
    public static void main(String[] args) {
        LinkedList<String> dq = new LinkedList<>();
        dq.addLast("b");
        dq.addFirst("a");
        dq.addLast("c");
        System.out.println(dq.removeFirst()); // a
        System.out.println(dq.get(1));        // c  (O(n) walk)
        System.out.println(dq);
    }
}

When LinkedList looks good vs when it is not

Use case	LinkedList?	Better default
Lots of `get(i)` / loops by index	No — O(n) each	`ArrayList`
Queue / stack (ends only)	Works	`ArrayDeque`
Frequent insert in the middle via List index	Still O(n) to find the node	Usually `ArrayList` anyway
Insert via `ListIterator` at current cursor	O(1) splice	Valid niche
Memory-tight large lists	Poor (3 refs/node)	`ArrayList`

ListIterator advantage

A ListIterator sitting on a node can add/remove in O(1) once you are there. Getting the iterator to index i is still O(n).

Advanced — LinkedList

Complexity details and pitfalls

size is stored — size() is O(1), unlike a hand-rolled list that recounts.
LinkedList is fail-fast and not thread-safe. It allows null elements.
Interview myth: “insert in the middle is O(1)”. Only the pointer update is O(1); finding the index is O(n).
Cache locality: chasing next pointers misses cache. For n in the thousands, ArrayList add/remove in the middle can still win.
Do not use LinkedList just because the problem statement says “linked list” — interviewers may want *your* Node class, not java.util.LinkedList.

Tricky Interview Points

Q1) Is LinkedList.get(i) O(1)?

Answer No. It walks nodes from the closer end. O(n).

Q2) Does LinkedList implement Deque?

Answer Yes. It is both a List and a Deque (double-ended queue).

Q3) Why is ArrayDeque preferred over LinkedList as a queue?

Answer ArrayDeque is a resizable circular array: better locality, fewer objects, no node wrappers. LinkedList pays an object header per element.

Q4) When is middle insert O(1)?

Answer When you already hold a ListIterator (or node). From an index alone, LinkedList is O(n).

Q5) Can LinkedList hold null?

Answer Yes. ArrayDeque does not allow null (null is a special empty marker).

Q6) ArrayList vs LinkedList for contains?

Answer Both O(n) linear scans. If you need contains a lot, use a HashSet (possibly in addition to a list).

Simple Programs

Use LinkedList only as a Deque demo

import java.util.LinkedList;

public class LinkedQueue {
    public static void main(String[] args) {
        LinkedList<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
}

Problem Solving Tricks

If you wrote new LinkedList<>() out of habit, switch to ArrayList unless you need node splicing or Deque-on-list.
For a queue, type the variable as Queue or Deque and construct ArrayDeque.
Never call get(i) in a loop on LinkedList — that is O(n²). Use for-each or an iterator.
Interview coding: implement reverse, detect cycle, merge on your own Node class.

Practice Programs List

Build a list of 10 elements and print get(i) in a loop — then rewrite with for-each.
Use ListIterator to insert "x" after the first "b".
Compare addFirst on LinkedList vs add(0, e) on ArrayList for 50_000 inserts (think, or time it).
Implement a palindrome check using LinkedList as a deque (pollFirst vs pollLast).
Write your own singly linked Node reverse (do not use java.util.LinkedList).