Quick Recap: Internal Working of Lists in Java

Java provides multiple List implementations — each with different internal mechanisms and performance trade-offs. Choosing the right one based on use case is important for performance.

---

Most Common List Implementations

List Type	Main Feature	Use Case
ArrayList	Fast reads	General-purpose
LinkedList	Fast insert/delete	Frequent add/remove
Vector	Synchronized ArrayList	Legacy thread-safe code
CopyOnWriteArrayList	Thread-safe & immutable copy on write	Concurrent reads, few writes

---

1. ArrayList (Most Used)

• Backed by dynamic array (Object[])
• Fast random access — O(1) using index
• When full → grows by 50% (in newer JDKs)
• Not thread-safe

Internal Resize Logic:

newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x growth

Best For: Read-heavy operations & small modifications

Avoid When: Frequent insert/delete from middle → O(n) shifts

---

2. LinkedList

• Doubly Linked List internally (prev, next pointers)
• No index-based access → O(n)
• Insertion & deletion = O(1) (if position known)
• More memory overhead (storing pointers)

Node Structure:

class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;
}

Best For: Queue/Deque, frequent add/remove

Avoid When: Random access & large data reads

---

3. Vector (Legacy Thread-Safe)

• Same as ArrayList but synchronized
• Grows by 100% (double size)
• Old and not used in modern apps

Resize Logic:

newCapacity = oldCapacity * 2;

Best For: Legacy apps with single-threaded logic

Avoid When: Modern concurrency → use ArrayList + sync or CopyOnWriteArrayList

---

4. CopyOnWriteArrayList

• Used in concurrent environments
• On every write → creates new copy of array
• No locks during read → very fast reads
• Write operations = expensive (copy on each change)

Internal Write Logic:

public boolean add(E e) {
synchronized (lock) {
Object[] newArr = Arrays.copyOf(oldArr, oldArr.length + 1);
newArr[last] = e;
array = newArr;
}
}

Best For: Many reads, very few writes

Avoid When: Write-heavy operations (slow performance)

---

Performance Comparison

Operation	ArrayList	LinkedList	CopyOnWriteArrayList
Read by index	🚀 Fast	❌ Slow	🚀 Fast
Insert/Delete middle	❌ Slow	🚀 Fast	❌ Very slow
Thread safety	No	No	Yes
Memory usage	Low	High	Medium–High

---

When to Use What?

Scenario	Recommended List
Random access	ArrayList
Frequent insert/delete	LinkedList
Legacy sync code	Vector
Concurrent reads, few writes	CopyOnWriteArrayList
Queue / Deque	LinkedList

---

Summary

List Type	Backed By	Best Use
ArrayList	Dynamic array	Fast lookup
LinkedList	Doubly linked list	Frequent addition/removal
Vector	Dynamic array (synchronized)	Legacy systems
CopyOnWriteArrayList	Dynamic array clone	Concurrent reads