Java LinkedList

java.util.LinkedList<E> is one of those collections that every Java developer knows the name of but very few use in the right context. It is a doubly-linked list — each element lives in a Node object that holds the element itself plus references to the previous and the next node. Unlike ArrayList, there is no backing array, no capacity, and no resizing. The tradeoff is that random access by index is slow, but insertions and deletions at the head and tail are O(1).

Understanding when LinkedList is genuinely the right choice — and when it is not — is exactly the kind of reasoning that product company interviews test.

What Is Java LinkedList?

LinkedList<E> is a concrete class in java.util that implements two interfaces simultaneously: java.util.List<E> and java.util.Deque<E>. This dual implementation is what makes it unique — it is both an ordered sequence with index access and a double-ended queue with O(1) head and tail operations.

The diagram below shows where LinkedList sits in the Collections hierarchy.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            ├── java.util.List<E>           ← ordered, indexed, duplicates OK
            │       ├── ArrayList           (resizable array)
            │       └── LinkedList          ← implements BOTH List AND Deque
            │
            └── java.util.Queue<E>
                    └── java.util.Deque<E>  ← double-ended queue
                            ├── ArrayDeque  (resizable circular array — preferred)
                            └── LinkedList  ← also here, same class

KEY FACTS:
  Package   : java.util
  Since     : Java 1.2
  Interfaces: List<E>, Deque<E>, Queue<E>, Cloneable, Serializable
  Allows    : null elements, duplicate elements
  Order     : insertion order preserved
  Thread    : NOT thread-safe
  Backing   : doubly-linked Node chain — no array, no capacity

Basic Overview — Node Structure

Every element in a LinkedList is wrapped in an internal Node object. The class declaration looks like this conceptually:

LINKEDLIST NODE STRUCTURE:

  private static class Node<E> {
      E    item;   ← the actual element
      Node next;   ← reference to the next node (null at tail)
      Node prev;   ← reference to the previous node (null at head)
  }

LINKEDLIST WITH 4 ELEMENTS ["A", "B", "C", "D"]:

  LinkedList fields:
    first → Node("A")
    last  → Node("D")
    size  = 4

  Node chain:
  null ← [prev|"A"|next] ↔ [prev|"B"|next] ↔ [prev|"C"|next] ↔ [prev|"D"|next] → null
            ↑                                                           ↑
          first                                                        last

  No backing array. No capacity. Size grows and shrinks one Node at a time.
  Each Node is a separate heap object — allocated on add, eligible for GC on remove.

This node-based structure is what gives LinkedList its O(1) head and tail operations but its O(n) index-based access.

When to Use LinkedList

This is the section that most tutorials skip, which is why developers reach for LinkedList in the wrong places. The honest answer is that LinkedList has a narrow set of use cases where it genuinely outperforms ArrayList.

CHOOSE LinkedList WHEN:
  1. Frequent insertions and removals at the HEAD of a large list
     — addFirst() and removeFirst() are O(1) on LinkedList
     — addFirst() on ArrayList shifts all elements right — O(n)

  2. You need both List AND Deque interfaces on the same object
     — LinkedList implements both; ArrayDeque does not implement List

  3. You are implementing a queue or deque and also need List-level operations
     like get(index) on the same structure

CHOOSE ArrayList INSTEAD WHEN:
  - Random access by index is frequent — get(index) is O(1) on ArrayList, O(n) on LinkedList
  - Sequential iteration is the primary operation — ArrayList is cache-friendly
  - Memory is a concern — each LinkedList Node costs ~24-32 bytes of overhead

CHOOSE ArrayDeque INSTEAD WHEN:
  - Pure queue or deque operations (addFirst, addLast, removeFirst, removeLast)
  - No index-based access needed
  - ArrayDeque is faster than LinkedList for head/tail ops due to better cache locality

A mistake that appears often in fresher pull requests is using LinkedList
as a default list because "it's more efficient for insertions." This is
only true for HEAD and TAIL insertions. Mid-list insertions on LinkedList
still require O(n) traversal to find the position.

How LinkedList Works Internally

addFirst() and addLast() — O(1)

Both head and tail operations are O(1) because LinkedList holds direct references to both ends via the first and last fields.

ADDLAST("E") on ["A","B","C","D"]:

  Before:
  null ← [A|next] ↔ [B|next] ↔ [C|next] ↔ [D|null] → null
              ↑                                  ↑
            first                               last

  Steps:
  1. Create newNode("E")
  2. newNode.prev = last  (points to D's node)
  3. last.next    = newNode
  4. last         = newNode
  5. size++

  After:
  null ← [A|next] ↔ [B|next] ↔ [C|next] ↔ [D|next] ↔ [E|null] → null
              ↑                                               ↑
            first                                           last

  O(1) — exactly 4 pointer updates + 1 Node allocation regardless of list size.


ADDFIRST("Z") on ["A","B","C","D"]:

  Steps:
  1. Create newNode("Z")
  2. newNode.next = first  (points to A's node)
  3. first.prev   = newNode
  4. first        = newNode
  5. size++

  O(1) — same cost as addLast. ArrayList equivalent shifts all elements — O(n).

get(index) — O(n)

There is no array to jump into. LinkedList must traverse from the closer end.

get(2) on ["A","B","C","D","E"] (size=5):

  index 2 < size/2 (2.5)  → traverse from first
  Step 0: current = first  (A)
  Step 1: current = current.next  (B)
  Step 2: current = current.next  (C)  ← return this

  get(3) — index 3 > size/2 (2.5) → traverse from last
  Step 0: current = last  (E)
  Step 1: current = current.prev  (D)  ← return this

  Java's optimization: always starts from the closer end.
  Worst case: the middle element — O(n/2) traversals, still O(n).

  A for(int i=0; i<list.size(); i++) loop on a LinkedList is O(n²) total
  because each get(i) traverses from the start or end — O(n) per call.
  This is a real performance bug that appears in production code.

removeFirst() and removeLast() — O(1)

REMOVEFIRST() on ["A","B","C","D"]:

  Steps:
  1. save result = first.item  ("A")
  2. next = first.next
  3. first.item = null  (help GC)
  4. first.next = null  (help GC, detach node)
  5. first = next
  6. if (first == null) last = null  (list is now empty)
  7. else first.prev = null
  8. size--

  O(1) — no shifting, no copying. Node is detached and eligible for GC.

Memory Cost Per Element

MEMORY COMPARISON (64-bit JVM, compressed references):

  ArrayList entry:
    Object reference: 4 bytes in the backing Object[]
    Total overhead per element: ~4 bytes

  LinkedList Node:
    Object header:   16 bytes
    item reference:   4 bytes
    next reference:   4 bytes
    prev reference:   4 bytes
    Total per Node:  ~28 bytes

  For 10,000 elements:
    ArrayList overhead:  ~40 KB  (just references)
    LinkedList overhead: ~280 KB (node objects)

  LinkedList uses roughly 7× more memory overhead per element than ArrayList.
  For GC-sensitive or memory-constrained paths, this matters significantly.

Core Operations with Examples

Adding Elements — List and Deque APIs

LinkedList exposes both List.add() and Deque.addFirst()/addLast(). Knowing both APIs and when each is appropriate is an interview expectation.

Output:
After add() (List API): [Task-1, Task-2, Task-3]
After addFirst + addLast: [URGENT-Task, Task-1, Task-2, Task-3, Task-4]
After add(2, Task-1.5): [URGENT-Task, Task-1, Task-1.5, Task-2, Task-3, Task-4]
After offer(): [URGENT-Task, Task-1, Task-1.5, Task-2, Task-3, Task-4, Task-5]
After push(): [CRITICAL, URGENT-Task, Task-1, Task-1.5, Task-2, Task-3, Task-4, Task-5]
Size: 8

Accessing and Removing Elements

Output:
=== Peek — read without removing ===
peekFirst() : Page-A
peekLast()  : Page-E
peek()      : Page-A
List unchanged: [Page-A, Page-B, Page-C, Page-D, Page-E]

=== Poll — remove and return ===
pollFirst() : Page-A
pollLast()  : Page-E
After polls : [Page-B, Page-C, Page-D]

=== pop / remove — throw if empty ===
pop()       : Page-B
removeLast(): Page-D
After removes: [Page-C]

=== get(index) — O(n) traversal ===
get(0) : Alpha
get(4) : Epsilon
get(2) : Gamma

=== poll on empty list returns null, not exception ===
poll()   on empty : null
peek()   on empty : null
remove() on empty : throws NoSuchElementException

Iterating LinkedList

Output:
for-each: 88 45 92 67 78 55 95
descendingIterator: 95 55 78 67 92 45 88

Removing scores below 70 (safe via iterator):
After removing below 70: [88, 92, 78, 95]
After removeIf(< 70): [88, 92, 78, 99, 87]

Using LinkedList as a Queue and Stack

Output:
=== Queue (FIFO) ===
Queue   : [Customer-Priya, Customer-Rohan, Customer-Ananya]
Serving : Customer-Priya
Next    : Customer-Rohan
Remaining: [Customer-Rohan, Customer-Ananya]

=== Stack (LIFO) — browser back button ===
History : [/checkout, /cart, /products, /home]
Back    : /checkout
Back    : /cart
Current : /products
Remaining: [/products, /home]

Real-World Example — Swiggy Order Priority Queue Manager

A food delivery platform like Swiggy needs to manage incoming orders with different priorities. Express orders go to the front of the queue; standard orders join the back. The dispatcher always processes the next order from the front. LinkedList as a Deque makes both operations O(1) — no shifting, no copying — while preserving the order in which orders were received within each priority tier.

Output:
--- Incoming orders ---
  STANDARD queued at tail: [ORD-001] Priya K.    → Burger King         Rs.389.00  (STANDARD)
  STANDARD queued at tail: [ORD-002] Rohan M.    → Dominos             Rs.549.00  (STANDARD)
  EXPRESS queued at head: [ORD-003] Ananya S.    → KFC                 Rs.749.00  (EXPRESS)
  STANDARD queued at tail: [ORD-004] Karan P.    → Pizza Hut           Rs.899.00  (STANDARD)
  EXPRESS queued at head: [ORD-005] Divya R.     → McDonald's          Rs.349.00  (EXPRESS)

--- Current queue ---
======================================================================
  ORDER QUEUE (5 orders)
======================================================================
  1. [ORD-005] Divya R.     → McDonald's          Rs.349.00  (EXPRESS)
  2. [ORD-003] Ananya S.    → KFC                 Rs.749.00  (EXPRESS)
  3. [ORD-001] Priya K.     → Burger King         Rs.389.00  (STANDARD)
  4. [ORD-002] Rohan M.     → Dominos             Rs.549.00  (STANDARD)
  5. [ORD-004] Karan P.     → Pizza Hut           Rs.899.00  (STANDARD)
======================================================================

--- Dispatching ---
  DISPATCHING: [ORD-005] Divya R.     → McDonald's          Rs.349.00  (EXPRESS)
  DISPATCHING: [ORD-003] Ananya S.    → KFC                 Rs.749.00  (EXPRESS)
  DISPATCHING: [ORD-001] Priya K.     → Burger King         Rs.389.00  (STANDARD)

--- Remaining queue ---
======================================================================
  ORDER QUEUE (2 orders)
======================================================================
  1. [ORD-002] Rohan M.     → Dominos             Rs.549.00  (STANDARD)
  2. [ORD-004] Karan P.     → Pizza Hut           Rs.899.00  (STANDARD)
======================================================================

Performance Considerations

Thread safety: LinkedList is not thread-safe. Two threads modifying the same LinkedList concurrently can corrupt the node chain. For concurrent queue operations, use ConcurrentLinkedQueue or LinkedBlockingQueue from java.util.concurrent.

The O(n²) trap: Using get(i) in a loop on a LinkedList is O(n²) because each get() traverses from the closest end. The fix is to always use an iterator or for-each for sequential traversal on LinkedList. This is a real performance bug that appears in production code and is noticeable at 10,000+ elements.

Best Practices

Declare the variable type as the narrowest useful interface, not LinkedList. Write Deque<String> queue = new LinkedList<>() or Queue<String> queue = new LinkedList<>() rather than LinkedList<String> queue = new LinkedList<>(). This makes the intent clear and lets you swap to ArrayDeque (usually faster) without changing any other code. During code reviews, LinkedList on the left side is a signal to discuss whether ArrayDeque would be a better fit.

Always iterate LinkedList with for-each or an explicit iterator — never with an index loop. An index loop on LinkedList that calls get(i) per iteration is O(n²). The iterator uses node.next pointers directly and is O(n) total. For descending traversal, use descendingIterator() rather than iterating backwards by index.

Pre-consider ArrayDeque before choosing LinkedList for queue and stack use. For pure FIFO queues and LIFO stacks, ArrayDeque is almost always faster than LinkedList — it uses a resizable circular array that is cache-friendly, allocates no per-element objects, and has lower GC pressure. LinkedList is the right choice when you genuinely need both the List and Deque interfaces on the same object in the same method.

Common Mistakes

Mistake 1 — Using get(index) in a Loop

Mistake 2 — Choosing LinkedList When ArrayDeque Is Sufficient

Mistake 3 — Assuming Mid-List Insertion Is O(1)

Mistake 4 — Using LinkedList in a Multi-threaded Context Without Synchronisation

Interview Questions

Q1. What is LinkedList in Java and how does it differ from ArrayList?

LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It stores each element in a Node object with prev and next references — no backing array, no capacity. ArrayList stores elements in a contiguous Object[]. The core difference: ArrayList provides O(1) random access via get(index) and O(n) head insertions due to array shifting. LinkedList provides O(1) head and tail insertions via addFirst() and addLast() but O(n) get(index) because it must traverse from the nearest end. For most real-world use cases, ArrayList is faster due to cache locality and lower memory overhead.

Q2. Why is LinkedList also a Deque?

LinkedList implements both List<E> and Deque<E> because the doubly-linked node structure naturally supports both interfaces. The first pointer enables O(1) addFirst(), removeFirst(), and peekFirst(). The last pointer enables O(1) addLast(), removeLast(), and peekLast(). This makes LinkedList the only standard Java class that is simultaneously an ordered indexed sequence and a double-ended queue. The practical implication: LinkedList can serve as a List, a Queue, a Deque, or a Stack using one object — though for pure Deque use, ArrayDeque is generally preferred.

Q3. When is LinkedList genuinely faster than ArrayList?

LinkedList.addFirst() and removeFirst() are O(1), while ArrayList.add(0, element) and ArrayList.remove(0) are O(n) because all elements must shift. For large lists where head insertions and removals are the dominant operation — for example, a priority queue that always inserts at the front or a scheduler that always dispatches from the front — LinkedList is genuinely faster. For all other access patterns — random access, sequential iteration, appending to the tail, sorting — ArrayList is faster. The crossover where LinkedList wins is narrower than most beginners assume.

Q4. What is the time complexity of iterator traversal on LinkedList vs ArrayList?

Both are O(n) for a full sequential traversal, but for very different reasons. ArrayList's iterator advances an integer index and reads elementData[cursor] — extremely cache-friendly because array elements are contiguous in memory. LinkedList's iterator follows node.next pointers — each pointer jump accesses a different heap location, causing more cache misses. In practice, sequential iteration on ArrayList is measurably faster than on LinkedList for large lists, even though both are O(n). The difference becomes significant at hundreds of thousands of elements.

Q5. What is the difference between poll() and remove() on LinkedList?

Both retrieve and remove the head element. remove() (and removeFirst()) throws NoSuchElementException if the list is empty. poll() (and pollFirst()) returns null if the list is empty. The null-returning methods form a trio: offer() for add, poll() for remove, peek() for read without removing — all return null rather than throwing on failure. These are part of the Queue interface contract. In production code, poll() is preferred for queue processing because it avoids exception handling when the queue might legitimately be empty between polling intervals.

Q6. Can LinkedList contain null elements?

Yes. LinkedList allows null elements at any position, and allows multiple nulls. This is different from ArrayDeque, which explicitly rejects null and throws NullPointerException on addFirst(null) or push(null). The reason ArrayDeque rejects null: since peek() returns null when the deque is empty, allowing null elements would create ambiguity. LinkedList has no such issue because size() and isEmpty() provide an unambiguous emptiness check. However, using null elements in a LinkedList is generally a design smell — consider using Optional or a sentinel value instead.

FAQs

Is LinkedList thread-safe in Java?

No. LinkedList is not thread-safe. Concurrent modification by multiple threads can corrupt the doubly-linked node chain — the first, last, prev, and next pointers can get into inconsistent states. For thread-safe queue operations, use ConcurrentLinkedQueue or LinkedBlockingQueue from java.util.concurrent. For thread-safe deque operations, use ConcurrentLinkedDeque or LinkedBlockingDeque.

Does LinkedList maintain insertion order?

Yes. LinkedList preserves insertion order exactly — elements are iterated in the order they were added. addLast() and add() append to the tail; addFirst() inserts at the head. This is unlike HashSet or HashMap, which make no ordering guarantee. If insertion-order preservation is the only requirement (not head insertions), ArrayList is a better choice.

What is the default initial capacity of LinkedList?

LinkedList has no initial capacity — it has no backing array. It starts with first = null, last = null, and size = 0. Each add() allocates one new Node object. This is why LinkedList never needs resizing (unlike ArrayList), but also why it allocates a separate heap object per element, increasing GC pressure.

When should I use LinkedList over ArrayDeque?

Use LinkedList over ArrayDeque when you need both the List interface (index-based access, get(i), set(i, e), subList()) and the Deque interface on the same object. If your code only uses queue or stack operations (addFirst, addLast, removeFirst, removeLast, peek, poll), ArrayDeque is faster, uses less memory, and is the recommended default per the Java documentation.

What is LinkedList.descendingIterator() used for?

descendingIterator() returns an Iterator<E> that traverses the list from tail to head using node.prev pointers. It is the idiomatic way to iterate a LinkedList in reverse without reversing the list itself or using an index loop. A ListIterator started at list.listIterator(list.size()) achieves the same effect with more control (hasPrevious(), previous(), set(), add()).

What happens if you call get(index) on a very large LinkedList?

get(index) traverses the node chain from the closer end — first if index < size/2, last otherwise. For a LinkedList of 1,000,000 elements, get(500_000) (the middle) requires 500,000 node-pointer traversals. Calling get(i) inside a loop over all n elements produces O(n²) total operations — which can be seconds of delay on a list that ArrayList would iterate in milliseconds. This is the most critical performance pitfall with LinkedList, and it appears regularly in fresher code.

Summary

LinkedList is a doubly-linked list that implements both List and Deque. Its defining characteristic: every element lives in a separate Node object with prev and next pointers. This gives O(1) head and tail insertions and removals — addFirst(), addLast(), removeFirst(), removeLast() — but O(n) random access via get(index) because there is no backing array to jump into.

The practical guidance: use LinkedList when addFirst() or removeFirst() on large lists is the dominant operation and you need List-level operations on the same object. For pure queue and stack use, ArrayDeque is faster and more memory-efficient. For most List use cases, ArrayList is faster due to O(1) get() and cache-friendly memory layout.

For interviews: know the Node structure and why get(index) is O(n), explain why an index loop on LinkedList is O(n²), contrast head-insertion cost between LinkedList (O(1)) and ArrayList (O(n)), and describe the ArrayDeque vs LinkedList tradeoff for queue use.

What to Read Next