Lists Module
Learn how List data structures work internally. Understand the mechanics of ArrayList, Singly Linked List, and Doubly Linked List implementations.
What You'll Learn
Internal Implementation
- - How ArrayList uses a backing array
- - How LinkedList uses nodes and pointers
- - Memory layout differences
- - Dynamic resizing strategies
Operations
- - add, get, set, remove at any index
- - addFirst, addLast, removeFirst, removeLast
- - Step-by-step visualization of each operation
- - Java code and pseudocode
ArrayList
Dynamic array implementation with automatic resizing
Key Concepts
- - Backing array storage
- - Capacity vs size
- - Dynamic resizing (doubling)
- - Element shifting on insert/remove
Time Complexity
access: O(1)
insert End: O(1) amortized
insert Middle: O(n)
remove: O(n)
Singly Linked List
Linear collection of nodes connected by next pointers
Key Concepts
- - Node structure (data + next)
- - Head reference
- - Sequential traversal
- - Pointer manipulation
Time Complexity
access: O(n)
insert Front: O(1)
insert End: O(1) with tail
remove: O(n)
Doubly Linked List
Nodes connected by both next and previous pointers
Key Concepts
- - Node structure (data + next + prev)
- - Head and tail references
- - Bidirectional traversal
- - Complex pointer updates
Time Complexity
access: O(n)
insert Front: O(1)
insert End: O(1)
remove End: O(1)
Compare All List Types
See ArrayList vs LinkedList side-by-side with interactive performance demos
Visual Guide: Memory Layout
ArrayList - Contiguous Memory
data[]:
10
20
30
40
size=4, capacity=6Singly Linked List - Nodes with Next Pointers
head→→→→→ null
10
next
20
next
30
next
40
next
Doubly Linked List - Bidirectional Pointers
head→⇄⇄→ null← tail
prev
10
next
prev
20
next
prev
30
next