LinkedList

📋 Quick Reference

Property	Value
Type	Doubly-linked node sequence
Access	O(n) - must traverse from head/tail
Insert/Delete at Ends	O(1)
Insert/Delete at Middle	O(1) with iterator, O(n) to find position
Memory	Extra overhead per node (prev + next pointers)
Best For	Frequent insertions/deletions at known positions

One-liner: Doubly-linked list with O(1) add/remove at ends, but O(n) random access.

🎮 Interactive Visualizer

Watch how LinkedList manages node connections for insertions and deletions:

LinkedList Operations
Ends: O(1)Index: O(n)
1 / 14
Initialize empty LinkedList (doubly-linked). O(1) for add/remove at ends, O(n) for indexed access.
🔗 LinkedList vs ArrayList
Operation
LinkedList
ArrayList
add/remove (ends)
O(1)
O(1)*
add/remove (middle)
O(1)**
O(n)
get(index)
O(n)
O(1)
* amortized | ** if you have the node reference
Best for:Frequent insertions/deletions, implementing stacks/queues/deques
Avoid for:Random access by index, when cache locality matters
Doubly-Linked List
Empty list (head = tail = null)
head = tail = null, size = 0
Pseudocode
1class Node { value, next, prev }
2 
3addFirst(value):
4  node = new Node(value)
5  node.next = head
6  head.prev = node
7  head = node
8 
9addLast(value):
10  node = new Node(value)
11  tail.next = node
12  node.prev = tail
13  tail = node
14 
15get(index):
16  node = head
17  for i = 0 to index:
18    node = node.next
19  return node.value
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Node
Node
Active
Active
P · [ ] · R
Loading visualizer...

Try these operations:

Add at head/tail - see O(1) pointer updates
Insert in middle - observe node linking
Remove a node - watch pointer rewiring
Traverse the list - see the step-by-step access

🔧 Key Operations

Creating

JAVA(8 lines)
Code
Loading syntax highlighter...

Adding Elements

JAVA(8 lines)
Code
Loading syntax highlighter...

Accessing

JAVA(7 lines)
Code
Loading syntax highlighter...

Removing

JAVA(8 lines)
Code
Loading syntax highlighter...

Iteration

JAVA(16 lines)
Code
Loading syntax highlighter...

📊 Complexity Analysis

Operation	Time	Notes
`addFirst/Last`	O(1)	Just update pointers
`removeFirst/Last`	O(1)	Just update pointers
`get(i)`	O(n)	Must traverse from head or tail
`add(i, e)`	O(n)	Find position + O(1) insert
`remove(i)`	O(n)	Find position + O(1) remove
`contains(e)`	O(n)	Linear search
`size()`	O(1)	Stored as field

Memory Layout

Head → [prev|data|next] ⟷ [prev|data|next] ⟷ [prev|data|next] ← Tail
        null←─┘     └─────────────────────────────→ null

Each node: ~24 bytes overhead (object header + 2 references)
vs ArrayList: ~4 bytes per element (just the reference)

✅ When to Use LinkedList

Good Use Cases

Queue/Deque operations - frequent add/remove at both ends
Iterator-based modifications - O(1) insert/delete during iteration
Large elements - moving pointers is cheaper than copying
Frequent splicing - merging lists is O(1)

Avoid When

Random access needed - use ArrayList instead
Memory is tight - node overhead is significant
Cache performance matters - non-contiguous memory
Small elements - overhead dominates actual data

🔄 LinkedList as Queue/Stack

JAVA(16 lines)
Code
Loading syntax highlighter...

⚠️ Common Pitfalls

1. Using get() in Loops

JAVA(9 lines)
Code
Loading syntax highlighter...

2. Wrong Data Structure Choice

JAVA(7 lines)
Code
Loading syntax highlighter...

3. Ignoring ArrayDeque Alternative

JAVA(5 lines)
Code
Loading syntax highlighter...

🎤 Interview Tips

Q: When would you use LinkedList over ArrayList?

"

When you need frequent insertions/deletions at both ends (as Deque), or when modifying during iteration using ListIterator. In practice, ArrayList is usually better due to cache locality and lower memory overhead.

Q: What's the time complexity of get(n/2)?

"

O(n), specifically O(n/2). Java's LinkedList optimizes by starting from the closer end (head or tail), but it's still linear. For index n/2, it traverses n/2 nodes.

Q: How does LinkedList implement List and Deque?

"

It's a doubly-linked list where each node has prev/next references. Head and tail references enable O(1) operations at both ends, satisfying Deque. The List interface is satisfied by traversing to any index.

Q: ArrayList vs LinkedList for a queue?

"

Neither is ideal. Use ArrayDeque - it has O(1) operations at both ends like LinkedList, but with ArrayList's cache locality and lower memory overhead.

Previous: Part 1: ArrayList

Next: Part 3: HashMap

Visualizer: LinkedList from @tomaszjarosz/react-visualizers