ArrayList & LinkedList

How ArrayList Works Inside

An ArrayList is not magic — it is an ordinary array with bookkeeping around it. Inside, it keeps a backing array plus a count of how many slots are actually in use. size() returns that count, not the length of the array underneath.

When you call add() and the backing array is full, the list creates a bigger array, copies everything across, and continues. This is why an ArrayList appears to grow without limit despite arrays being fixed. The growth is generous rather than one-at-a-time — each expansion adds roughly half the current capacity — so the copying happens rarely enough that appending is fast on average even though an individual add occasionally does real work.

Understanding this explains the performance characteristics you are expected to know. Reading by index is a single array access, so get(i) is instant regardless of size. Appending is almost always instant. But inserting or removing in the middle means every element after that position shifts by one, so it costs time proportional to how much is after it. And contains() or indexOf() must scan from the start, so they get slower as the list grows.

One small optimisation worth knowing: if you already know roughly how many elements you will add, pass that number to the constructor. new ArrayList<>(10000) allocates the space once rather than growing and copying repeatedly. It is not something to worry about for a list of twenty items, but it matters when loading large data.

import java.util.*;

List<String> fruits = new ArrayList<>();
// backing array capacity starts small; size() is 0

fruits.add("Apple");      // append — fast
fruits.add("Banana");
fruits.add("Cherry");
System.out.println(fruits.size());   // 3  — elements in use, not capacity

fruits.get(0);            // instant, whatever the size
fruits.add(1, "Blueberry");  // insert at index 1 — shifts Banana and Cherry along
System.out.println(fruits);  // [Apple, Blueberry, Banana, Cherry]

// Pre-sizing when you know the load ahead of time
List<Integer> big = new ArrayList<>(100_000);
for (int i = 0; i < 100_000; i++) {
    big.add(i);           // no repeated grow-and-copy
}

// A pattern that is quietly slow: contains() inside a loop
// for (String name : allNames) {
//     if (registered.contains(name)) { ... }    // scan inside a scan
// }
// If 'registered' is a HashSet instead of a List, each check is instant.

The Everyday API — and the remove() Trap

The methods you will use constantly are short in number: add, get, set, remove, size, contains, indexOf, isEmpty and clear. Note that set(i, value) replaces the element at that position while add(i, value) inserts and pushes everything along — mixing them up gives you a list of the wrong length.

Now the trap. List has two remove methods: remove(int index) removes by position, and remove(Object o) removes the first element equal to that object. For a List<String> they are easy to tell apart. For a List<Integer> they are not.

Write list.remove(1) on a List<Integer> and Java picks remove(int index), because 1 is an int and overload resolution prefers the exact match over boxing. So it removes the element at position 1, not the value 1. The code compiles, runs, and removes the wrong element. To remove by value you must force the object version: list.remove(Integer.valueOf(1)).

This is a favourite interview question precisely because it looks like nothing. It is also a real bug that ships. Whenever you have a list of numbers and you mean to remove a value, write Integer.valueOf(...) and leave a short comment.

Two more methods worth knowing early. indexOf() returns -1 when the element is absent — check that before using the result as an index. And subList(from, to) returns a view of a range, not a copy: changes to the sublist affect the original list, and modifying the original structurally invalidates the sublist.

import java.util.*;

List<String> fruits = new ArrayList<>(List.of("Apple", "Banana", "Cherry"));

fruits.set(0, "Avocado");         // REPLACE at index 0
System.out.println(fruits);       // [Avocado, Banana, Cherry]

fruits.add(1, "Blueberry");       // INSERT at index 1
System.out.println(fruits);       // [Avocado, Blueberry, Banana, Cherry]

fruits.remove("Banana");          // by value — unambiguous for Strings
fruits.remove(0);                 // by index
System.out.println(fruits);       // [Blueberry, Cherry]

System.out.println(fruits.indexOf("Cherry"));   // 1
System.out.println(fruits.indexOf("Mango"));    // -1  <- check before using

// ---- The Integer remove trap ----
List<Integer> marks = new ArrayList<>(List.of(10, 20, 30, 40));

marks.remove(1);                          // removes INDEX 1 -> the value 20
System.out.println(marks);                // [10, 30, 40]

marks.remove(Integer.valueOf(30));        // removes the VALUE 30
System.out.println(marks);                // [10, 40]

// subList is a VIEW, not a copy
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> middle = nums.subList(1, 4);   // [2, 3, 4]
middle.set(0, 99);
System.out.println(nums);                    // [1, 99, 3, 4, 5]  — original changed

LinkedList: a Chain of Nodes

A LinkedList stores its elements completely differently. There is no backing array. Each element sits in its own small object called a node, holding the value plus a reference to the previous node and a reference to the next. Java's implementation is doubly linked, so it can be walked in either direction, and it keeps direct references to the first and last nodes.

The consequence is a mirror image of ArrayList. Adding or removing at either end is instant, because it means redirecting two references and nothing shifts. But reading by index is slow: to reach element 500 the list must walk 500 links, since there is no arithmetic shortcut to a memory address.

That last point produces a specific performance disaster worth flagging. A counted for loop calling get(i) on a LinkedList walks from the start on every single iteration, turning a linear job into a quadratic one. Always iterate a LinkedList with the enhanced for loop or an iterator, which walks the chain once.

LinkedList also implements Deque, so it has methods for working at both ends — addFirst, addLast, getFirst, removeLast — plus the queue-style offer, poll and peek. That is genuinely its most common practical use.

import java.util.*;

LinkedList<String> tasks = new LinkedList<>();
tasks.add("Write report");
tasks.add("Email team");

tasks.addFirst("URGENT: fix build");     // instant
tasks.addLast("Update docs");            // instant

System.out.println(tasks.getFirst());    // URGENT: fix build
System.out.println(tasks.getLast());     // Update docs
tasks.removeFirst();
tasks.removeLast();
System.out.println(tasks);               // [Write report, Email team]

// As a queue (first in, first out)
Queue<String> tokenQueue = new LinkedList<>();
tokenQueue.offer("T-101");
tokenQueue.offer("T-102");
System.out.println(tokenQueue.peek());   // T-101 — look without removing
System.out.println(tokenQueue.poll());   // T-101 — remove and return

// ---- The performance mistake ----
List<Integer> ll = new LinkedList<>();
for (int i = 0; i < 50_000; i++) ll.add(i);

// SLOW: walks from the start on every iteration
// for (int i = 0; i < ll.size(); i++) {
//     process(ll.get(i));
// }

// FAST: walks the chain exactly once
for (int value : ll) {
    // process(value);
}

Which One Should You Actually Use?

The textbook answer is that ArrayList is better for random access and LinkedList is better for insertion and deletion. That is correct about the algorithms and misleading about real programs.

In practice ArrayList wins far more often than the theory suggests, even for middle insertions, up to surprisingly large sizes. Two reasons. The shifting is done by a highly optimised bulk memory copy rather than an element-by-element loop. And an ArrayList's elements sit next to each other in memory, which modern processors handle dramatically faster than chasing scattered references — a LinkedList defeats the CPU cache on every step.

There is also a hidden cost people forget. To insert into the middle of a LinkedList you must first find the middle, which means walking there. So the theoretical constant-time insertion only applies when you are already positioned there, typically at an end.

The honest guidance is below. If you are unsure, use ArrayList. Reach for LinkedList when you specifically need queue or deque behaviour — and even then ArrayDeque is usually faster for that job.

• Reading by index frequently — ArrayList, without question
• Mostly appending and then iterating — ArrayList
• Heavy adding and removing at the front of a large list — LinkedList
• A queue or a stack — ArrayDeque first, LinkedList if you also need List methods
• Memory matters — ArrayList, which stores no per-element overhead
• You genuinely do not know — ArrayList. It is the right default about ninety percent of the time.
• Either way, declare the variable as List so you can change your mind by editing one line

Sorting Lists and Writing Comparators

Sorting a list of Strings or numbers needs nothing extra, because those classes already know how to order themselves — they implement Comparable, and list.sort(null) or Collections.sort(list) uses that natural ordering.

For your own classes there is no natural order until you supply one, and you have two ways to do it. Implement Comparable on the class itself when there is one obvious default ordering — sorting students by roll number, say. Its compareTo must return a negative number when this object comes first, zero when they tie, and a positive number when it comes second.

Supply a Comparator when the ordering is a decision made by the caller, or when you need several different orderings of the same class. Since Java 8 you rarely write one by hand: Comparator.comparing(Student::getName) builds one from a getter, thenComparing adds a tie-breaker, and reversed() flips the direction. These read almost like English and are much harder to get wrong than a hand-written comparison.

One warning: do not implement compareTo for integers as a - b. It looks neat and it overflows for large values — subtracting a large negative from a large positive wraps around and produces the wrong sign, which corrupts the sort. Use Integer.compare(a, b), which is both correct and clearer.

import java.util.*;

// Natural ordering works out of the box for Strings and numbers
List<String> names = new ArrayList<>(List.of("Rahul", "Ananya", "Meera"));
Collections.sort(names);
System.out.println(names);        // [Ananya, Meera, Rahul]

class Student {
    private final String name;
    private final int marks;

    Student(String name, int marks) { this.name = name; this.marks = marks; }
    public String getName()  { return name; }
    public int    getMarks() { return marks; }

    @Override public String toString() { return name + "(" + marks + ")"; }
}

List<Student> batch = new ArrayList<>(List.of(
    new Student("Rahul", 92),
    new Student("Ananya", 87),
    new Student("Meera", 92)
));

// Sort by marks, ascending
batch.sort(Comparator.comparingInt(Student::getMarks));
System.out.println(batch);        // [Ananya(87), Rahul(92), Meera(92)]

// Highest marks first, ties broken alphabetically by name
batch.sort(Comparator.comparingInt(Student::getMarks).reversed()
                     .thenComparing(Student::getName));
System.out.println(batch);        // [Meera(92), Rahul(92), Ananya(87)]

// Writing one by hand — use Integer.compare, never a - b
Comparator<Student> byMarks = (s1, s2) -> Integer.compare(s1.getMarks(), s2.getMarks());
// (a, b) -> a.getMarks() - b.getMarks()   <- can overflow, avoid