Lesson 24 • Advanced
Collections Internals & Performance
How ArrayList, LinkedList, and HashSet work under the hood.
Before You Start
You should be comfortable with Collections (Lesson 13) and Generics (Lesson 14). Understanding basic data structures (arrays, linked lists, hash tables) will help you follow the internal implementations.
What You'll Learn
- ✅ ArrayList: dynamic array resizing strategy
- ✅ LinkedList: node-based doubly-linked structure
- ✅ HashSet/HashMap: hashing, buckets, and collisions
- ✅ Big-O complexity for each operation
- ✅ Choosing the right collection for your use case
1️⃣ ArrayList Internals
💡 Analogy: Storage Systems
ArrayList is like a filing cabinet with numbered drawers — instant access by drawer number, but inserting in the middle means sliding everything down. It starts with capacity 10, and when full, creates a new array 1.5x larger and copies everything over. This results in amortized O(1) for add operations.
Try It: ArrayList Resizing Internals
// ArrayList Internals — Dynamic Resizing
console.log("=== ArrayList Internals ===\n");
class SimpleArrayList {
constructor() { this.data = new Array(4); this.size = 0; this.capacity = 4; }
add(item) {
if (this.size === this.capacity) {
let oldCapacity = this.capacity;
this.capacity = Math.floor(this.capacity * 1.5);
let newData = new Array(this.capacity);
for (let i = 0; i < this.size; i++) newData[i] = this.data[i];
t
...2️⃣ LinkedList Internals
LinkedList is like a chain of train cars — adding/removing a car is easy if you're already at that car, but finding car #47 means walking from the front. Each node holds a value plus pointers to the previous and next nodes. Java's LinkedList is doubly-linked, so it can traverse from either end.
Try It: LinkedList vs ArrayList
// LinkedList Internals & Comparison
console.log("=== LinkedList Internals ===\n");
class Node {
constructor(val) { this.val = val; this.prev = null; this.next = null; }
}
class SimpleLinkedList {
constructor() { this.head = null; this.tail = null; this.size = 0; }
addFirst(val) {
let node = new Node(val);
node.next = this.head;
if (this.head) this.head.prev = node;
this.head = node;
if (!this.tail) this.tail = node;
this.size++;
...3️⃣ HashMap: Buckets, Hashing & Collisions
HashMap uses an array of "buckets." Each key's hashCode() determines which bucket it goes in. When multiple keys land in the same bucket (collision), they form a linked list. Since Java 8, when a bucket exceeds 8 entries, it converts to a red-black tree for O(log n) lookups instead of O(n).
Try It: HashMap Bucket Simulation
// HashMap Internals — Hashing & Buckets
console.log("=== HashMap Internals ===\n");
class SimpleHashMap {
constructor(capacity = 8) {
this.buckets = new Array(capacity).fill(null).map(() => []);
this.capacity = capacity;
this.size = 0;
this.collisions = 0;
}
hash(key) {
let h = 0;
for (let c of String(key)) h = (h * 31 + c.charCodeAt(0)) % this.capacity;
return h;
}
put(key, value) {
let idx = this.hash(key);
...Common Mistakes
Pro Tips
💡 Pre-size your ArrayList when you know the expected size: new ArrayList<>(10000) avoids multiple resize copies.
💡 HashMap load factor defaults to 0.75. Lower values use more memory but fewer collisions. Higher values save memory but slow lookups.
💡 In 99% of cases, use ArrayList over LinkedList. The CPU cache performance of contiguous memory beats LinkedList's scattered nodes.
📋 Quick Reference
| Collection | Backed By | Best For |
|---|---|---|
| ArrayList | Dynamic array | Random access, iteration |
| LinkedList | Doubly-linked nodes | Queue/deque operations |
| HashMap | Hash table + buckets | Key-value lookups |
| TreeMap | Red-black tree | Sorted key-value pairs |
🎉 Lesson Complete!
You understand the internals of Java's core collection types!
Next: Advanced HashMap, TreeMap & LinkedHashMap.
Sign up for free to track which lessons you've completed and get learning reminders.