Java.Collections.What is the difference between ArrayList and LinkedList? When is it better to use the former and when is it better to use the latter?

✅ ArrayList

• Underlying Structure: Dynamic array.
• Access Time (get/set): O(1) – Direct access via index.
• Insert/Delete at End: O(1) amortized – Fast unless the array needs to resize.
• Insert/Delete in Middle/Beginning: O(n) – Requires shifting elements.
• Memory Usage: Less overhead, just a resizable array.

👉 Use ArrayList when:

• You need fast random access (e.g., accessing elements by index often).
• You mostly add/remove elements at the end of the list.
• Memory is a concern (less overhead compared to LinkedList).

---

✅ LinkedList

• Underlying Structure: Doubly-linked list.
• Access Time (get/set): O(n) – Have to traverse the list.
• Insert/Delete at Beginning or Middle: O(1) if you have a reference to the node.
• Insert/Delete at End: O(1) with tail reference.
• Memory Usage: More memory (each element stores pointers to next and previous nodes).

👉 Use LinkedList when:

• You need fast insertion/deletion in the middle or beginning of the list.
• You’re building queues or stacks.
• You don’t need random access.

---

🧪 Real-World Example:

Scenario	Preferred
Lookup by index (e.g., list.get(i))	✅ ArrayList
Frequent additions/removals at the beginning	✅ LinkedList
Memory-efficient list	✅ ArrayList
Implementing a queue (FIFO)	✅ LinkedList

In Java, ArrayList implements the List interface. That means:

public class ArrayList<E> implements List<E> {
    // implementation...
}

The magic of ArrayList is in how it automatically resizes itself when needed. Let’s break it down:

---

🧠 When does an ArrayList resize?

An ArrayList resizes when you try to add an element and there’s no more room in the internal array.

Internally:

• ArrayList uses a regular array to store elements (e.g., Object[] elementData).
• When you add more elements than the current array can hold, it creates a new, bigger array and copies the old elements over.

---

🔧 How much does it grow by?

By default (in Java 8+), when resizing is needed, it grows by 50% of the old capacity:

newCapacity = oldCapacity + (oldCapacity >> 1);  // same as oldCapacity * 1.5

So if current capacity is 10:

• It resizes to 15
• Then 22, 33, 49, and so on…

---

📦 Example:

List<String> list = new ArrayList<>(2); // initial capacity = 2
list.add("one");   // OK
list.add("two");   // OK
list.add("three"); // 🚨 Resize happens here

⚠️ Performance Note:

Resizing is costly, because:

1. A new array is allocated.
2. All old elements are copied to the new array.

So if you know in advance how many elements you’ll have, it’s a good idea to set the initial capacity:

List<Integer> list = new ArrayList<>(1000);

When you create an ArrayList without specifying capacity, like this:

List<String> list = new ArrayList<>();

Java still gives it an internal default behavior—but there’s a twist. Let’s dive into it 👇

---

🛠️ What actually happens?

When you call new ArrayList<>():

• The internal array (elementData) is created with zero capacity — it’s just an empty array:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

But Java defers the allocation of actual memory until you add the first element.

📈 Then what?

• When you add the first element, it resizes to the default capacity, which is 10:

private static final int DEFAULT_CAPACITY = 10;

So this:

List<String> list = new ArrayList<>();
list.add("one"); // 🚀 Capacity becomes 10 here

Before that add(), the internal array has length 0.

Summary:

How you create it	Initial capacity
new ArrayList<>()	0 (becomes 10 on first add)
new ArrayList<>(20)	20
new ArrayList<>(someCollection)	Based on size of collection