ArrayList

// ── Internal structure: ──────────────────────────────────────────────
// ArrayList<E> {
//   transient Object[] elementData;   // the backing array
//   private int size;                  // number of elements stored
// }
//
// new ArrayList<>():
//   elementData = {}  (empty array, lazy-initialised to capacity 10 on first add)
//   size = 0
//
// After adding "Alice", "Bob", "Charlie":
//   elementData = ["Alice", "Bob", "Charlie", null, null, null, null, null, null, null]
//   size = 3   (capacity = 10)
//
// After adding 8 more elements (total 11):
//   grows: new capacity = 10 + (10 >> 1) = 15
//   elementData = new Object[15]
//   all 11 elements copied to new array

// ── Creating an ArrayList: ────────────────────────────────────────────
ArrayList<String> list1 = new ArrayList<>();          // default capacity
ArrayList<String> list2 = new ArrayList<>(50);        // initial capacity 50
ArrayList<String> list3 = new ArrayList<>(
    Arrays.asList("Alice", "Bob"));                   // from existing collection

// Preferred: declare as List interface:
List<String> names = new ArrayList<>();

// ── Capacity management: ──────────────────────────────────────────────
ArrayList<Integer> nums = new ArrayList<>(1000);  // pre-sized
for (int i = 0; i < 1000; i++) nums.add(i);
// No intermediate resizing occurred — capacity was sufficient from the start.

// trimToSize() — release unused capacity:
ArrayList<String> trimmed = new ArrayList<>(100);
trimmed.add("a"); trimmed.add("b"); trimmed.add("c");
trimmed.trimToSize();   // shrinks internal array to size 3

// ensureCapacity() — hint that we'll add many elements:
ArrayList<String> growing = new ArrayList<>();
growing.ensureCapacity(500);   // avoid resizing for up to 500 elements

List<String> list = new ArrayList<>(
    Arrays.asList("Alice", "Bob", "Charlie", "Dave", "Eve"));

// ── Positional access — O(1): ────────────────────────────────────────
System.out.println(list.get(0));         // Alice
System.out.println(list.get(4));         // Eve
list.set(1, "Barbara");                  // replace index 1
System.out.println(list.get(1));         // Barbara

// ── Adding elements: ──────────────────────────────────────────────────
list.add("Frank");                       // append — O(1) amortised
list.add(0, "Zara");                     // insert at start — O(n) shift
list.addAll(List.of("Grace", "Henry"));  // add all at end
list.addAll(2, List.of("X", "Y"));       // insert all at index 2

// ── Removing elements: ────────────────────────────────────────────────
list.remove(0);                          // remove by index — O(n) shift
list.remove("Frank");                    // remove first occurrence by value — O(n)
list.removeAll(List.of("X", "Y"));       // remove all occurrences of these values
list.removeIf(s -> s.startsWith("G"));   // remove all matching predicate

// ── Searching: ────────────────────────────────────────────────────────
System.out.println(list.indexOf("Alice"));     // first occurrence index, -1 if absent
System.out.println(list.lastIndexOf("Alice")); // last occurrence index
System.out.println(list.contains("Alice"));    // true/false

// ── Sorting: ─────────────────────────────────────────────────────────
list.sort(null);                              // natural order
list.sort(Comparator.reverseOrder());         // reverse order
list.sort(Comparator.comparing(String::length)
    .thenComparing(Comparator.naturalOrder())); // multi-criteria

// ── subList — view, not copy: ─────────────────────────────────────────
List<String> sub = list.subList(1, 4);    // [index 1, 4)
sub.set(0, "MODIFIED");                   // reflects in original list
sub.clear();                              // removes elements from original

// ── Iteration: ────────────────────────────────────────────────────────
for (String s : list) System.out.println(s);        // for-each
list.forEach(System.out::println);                   // forEach
for (int i = 0; i < list.size(); i++) {             // indexed
    System.out.println(i + ": " + list.get(i));
}

// ── Performance summary: ──────────────────────────────────────────────
//
// Operation                  ArrayList    LinkedList
// ─────────────────────────  ─────────    ──────────
// get(index)                 O(1)         O(n)
// set(index, value)          O(1)         O(n)
// add(value) — append        O(1)*        O(1)
// add(index, value)          O(n)         O(n)**
// remove(index)              O(n)         O(n)**
// remove(Object)             O(n)         O(n)
// contains(Object)           O(n)         O(n)
// size()                     O(1)         O(1)
// iterator.next()            O(1)         O(1)
//
// * amortised O(1) — occasional O(n) resize
// ** O(1) if using ListIterator at known position

// ── Avoid ConcurrentModificationException: ───────────────────────────
List<String> items = new ArrayList<>(
    Arrays.asList("a", "remove-me", "b", "remove-me", "c"));

// WRONG — throws ConcurrentModificationException:
// for (String s : items) {
//     if (s.equals("remove-me")) items.remove(s);
// }

// CORRECT 1 — iterator.remove():
Iterator<String> it = items.iterator();
while (it.hasNext()) {
    if (it.next().equals("remove-me")) it.remove();
}

// CORRECT 2 — removeIf() (cleanest):
items.removeIf(s -> s.equals("remove-me"));

// CORRECT 3 — backward index loop:
for (int i = items.size() - 1; i >= 0; i--) {
    if (items.get(i).equals("remove-me")) items.remove(i);
}

// ── Common conversions: ───────────────────────────────────────────────
List<Integer> nums = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6));

// Deduplicate (to Set and back):
List<Integer> unique = new ArrayList<>(new LinkedHashSet<>(nums)); // preserves order
List<Integer> uniqueUnordered = new ArrayList<>(new HashSet<>(nums));

// Sort a copy without modifying original:
List<Integer> sorted = new ArrayList<>(nums);
Collections.sort(sorted);

// Convert to array:
Integer[] array = nums.toArray(Integer[]::new);

// Stream operations:
List<Integer> filtered = nums.stream()
    .filter(n -> n > 3)
    .distinct()
    .sorted()
    .collect(Collectors.toList());
System.out.println(filtered);   // [4, 5, 6, 9]