11.2 ArrayList and LinkedList

Let's take a deep look at the most widely used collection type: the List family. Think of a List just like an array that stores data sequentially with an order, except it's a smart array whose size changes dynamically.

1. ArrayList

ArrayList is internally built on top of a plain Array. When you add elements and the internal array fills up, it automatically expands to a larger array behind the scenes. It is highly optimized for situations where you need to ** quickly retrieve data by index (position)**.

import java.util.ArrayList;

ArrayList<String> fruits = new ArrayList<>();

// 1. add(): Add an element
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Strawberry");
System.out.println(fruits); // [Apple, Banana, Strawberry]

// 2. get(index): Retrieve element at a specific position
System.out.println(fruits.get(1)); // Banana

// 3. size(): Get the number of stored elements
System.out.println(fruits.size()); // 3

// 4. set(index, element): Update element at a specific position
fruits.set(0, "Mango");
System.out.println(fruits); // [Mango, Banana, Strawberry]

// 5. remove(index): Delete element at a specific position
fruits.remove(2);
System.out.println(fruits); // [Mango, Banana]

// 6. contains(): Check if a specific element exists
System.out.println(fruits.contains("Mango")); // true

Iterating an ArrayList (for-each loop)

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);

// for-each style (cleanest approach)
for (int num : numbers) {
    System.out.println(num); // Prints 10, 20, 30 in order
}

2. LinkedList

LinkedList is internally structured as a "chain (linked nodes)" where each data element remembers the memory addresses of its previous and next neighbors.

ArrayList vs LinkedList — Which to choose?

Operation	ArrayList	LinkedList
Retrieve by index (get)	⭐ Fast	Slow
Insert/Delete in the middle	Slow	⭐ Fast

• Many reads, few modifications → use ArrayList
• Frequent middle insertions/deletions → use LinkedList

(In real-world practice, ArrayList is overwhelmingly the default choice for most situations.)

import java.util.LinkedList;

LinkedList<String> queue = new LinkedList<>();

// Using LinkedList as a Queue: First in, First out (FIFO)
queue.add("First");
queue.add("Second");
queue.add("Third");

// Retrieve and remove from the front
System.out.println(queue.poll()); // First (removes it)
System.out.println(queue.poll()); // Second
System.out.println(queue);        // [Third]