List
An ordered Collection that permits duplicates and supports positional access — with ArrayList and LinkedList as the two everyday implementations.
List is the Collections Framework interface for an ordered sequence of elements accessed by integer index, allowing duplicate values. ArrayList and LinkedList are its two most commonly used implementations, each with different performance trade-offs depending on how the list is used.
What Is List
java.util.List<E> extends Collection<E> and adds a defined iteration order matching insertion/positional order, indexed access (get(int), set(int, E)), and permission for duplicate elements — unlike Set. Elements are stored at zero-based positions 0..size()-1.
import java.util.*;
List<String> colors = new ArrayList<>();
colors.add("red");
colors.add("blue");
colors.add("red"); // duplicates allowed
System.out.println(colors); // [red, blue, red]
System.out.println(colors.get(0)); // red — indexed accessArrayList
ArrayList is backed by a resizable array. get(index) and set(index, value) are O(1) (constant time) because it's direct array indexing. Adding at the end is amortized O(1) (occasionally the internal array is reallocated larger); inserting or removing at an arbitrary middle position is O(n) because subsequent elements must shift.
List<Integer> nums = new ArrayList<>();
for (int i = 0; i < 5; i++) nums.add(i * 10);
nums.add(2, 999); // insert at index 2 — shifts elements right
System.out.println(nums); // [0, 10, 999, 20, 30, 40]LinkedList
LinkedList is backed by a doubly linked list of nodes. Adding or removing at either end is O(1); adding or removing given a known position near an end is efficient, but get(index) is O(n) because it must be reached by walking node-to-node from the nearer end — there's no direct indexing. LinkedList also implements Deque, giving it efficient addFirst/addLast/removeFirst/removeLast operations.
List<String> queue = new LinkedList<>();
queue.add("a");
queue.add("b");
((LinkedList<String>) queue).addFirst("start"); // Deque-specific method
System.out.println(queue); // [start, a, b]Vector: Historical Context
Vector predates the Collections Framework (it's from Java 1.0) and was later retrofitted to implement List. It behaves much like ArrayList but every method is synchronized, which adds locking overhead even in single-threaded code and still doesn't make compound operations (like check-then-add) atomic. Vector is considered legacy; ArrayList (optionally combined with explicit synchronization or a concurrent collection when thread-safety is genuinely needed) is preferred in modern code.
Ordering and Duplicates
A List's iteration order always matches its element order (which is insertion order unless explicitly reordered via sort, add(index,...), etc. — it is not automatically sorted). Duplicate values (by equals()) are fully permitted and each occupies its own index.
List<String> l = new ArrayList<>(List.of("b", "a", "b"));
System.out.println(l.indexOf("b")); // 0 — first occurrence
System.out.println(l.lastIndexOf("b")); // 2 — last occurrence
l.sort(Comparator.naturalOrder());
System.out.println(l); // [a, b, b] — now sorted, order changed explicitlyIndexed Access
The signature feature that distinguishes List from Set and Queue is direct positional access: get(int index), set(int index, E element), add(int index, E element), remove(int index). All throw IndexOutOfBoundsException if the index is out of the valid range for that operation.
List<String> l = new ArrayList<>(List.of("x", "y", "z"));
l.set(1, "Y"); // replace element at index 1
System.out.println(l); // [x, Y, z]
try {
l.get(10);
} catch (IndexOutOfBoundsException e) {
System.out.println("out of bounds: " + e.getMessage());
}Basic Syntax and Common Operations
For List<Integer>, remove(int) removes by index while remove(Object) removes by value — list.remove(1) removes the element at index 1, while list.remove(Integer.valueOf(1)) removes the value 1. This overload ambiguity is a well-known source of subtle bugs.
List<String> list = new ArrayList<>();
list.add("one"); // append
list.add(0, "zero"); // insert at index
list.remove("one"); // remove by value (first match)
list.remove(0); // remove by index — ambiguous with Integer values, be careful
boolean has = list.contains("zero");
int size = list.size();
List<String> copy = new ArrayList<>(list); // copy constructorPractical Selection: ArrayList vs LinkedList
In practice, ArrayList is the default choice for most List usage; its cache-friendly contiguous array storage often outperforms LinkedList even for some operations LinkedList is theoretically better suited to, due to memory locality — actual performance is JVM- and workload-dependent, so measure when it matters.
Operation ArrayList LinkedList
get(index) / set(index) O(1) O(n)
add at end amortized O(1) O(1)
add/remove at front O(n) O(1)
insert/remove in middle O(n) O(n) to find + O(1) to splice
Memory overhead lower higher (node objects, two refs each)
Default choice: ArrayList, for almost all use cases.
Use LinkedList (or ArrayDeque) mainly when you need frequent
insertion/removal at both ends and rarely need random access.Edge Cases
List.of(...) returns an immutable list that throws UnsupportedOperationException on any mutating call and NullPointerException if you attempt to include a null element; Arrays.asList(...) returns a fixed-size list backed by the original array — its size cannot change (add/remove throw), but set() is allowed and writes through to the underlying array.
Iterating and structurally modifying a List directly (not through the iterator) in the same loop throws ConcurrentModificationException; use Iterator.remove(), ListIterator, or removeIf() instead.
ArrayList permits null elements; be careful that contains(null) and indexOf(null) work correctly, but a null element can still cause a NullPointerException later if code assumes non-null.
Complete Example
import java.util.*;
public class ShoppingList {
public static void main(String[] args) {
List<String> items = new ArrayList<>();
items.add("milk");
items.add("eggs");
items.add("milk"); // duplicates are fine in a List
System.out.println("Items: " + items);
System.out.println("Count of milk entries: "
+ Collections.frequency(items, "milk"));
items.removeIf(item -> item.equals("eggs"));
System.out.println("After removing eggs: " + items);
Collections.sort(items);
System.out.println("Sorted: " + items);
}
}Mental Model
Think of ArrayList as a row of numbered mailboxes bolted to a wall — jumping straight to box #47 is instant, but inserting a new box in the middle means physically sliding every box after it over by one. Think of LinkedList as a chain of people holding hands in a line — reaching person #47 means walking the chain from one end, but slipping a new person into the middle (once you're standing next to the right spot) is just re-linking two hands.
Quick Reference
List<E> — ordered, duplicates allowed, indexed access
ArrayList<E> — array-backed, fast get/set, default choice
LinkedList<E> — node-backed, fast at both ends, implements Deque
Vector<E> — legacy, synchronized, prefer ArrayList instead
List.of(...) — immutable, no null
Arrays.asList(...) — fixed-size, backed by the array, set() writes through
Collections.unmodifiableList(list) — mutable-backing, read-only viewKey Takeaways
List is an ordered Collection with indexed access that permits duplicate elements; order follows insertion unless explicitly changed.
ArrayList offers O(1) indexed access and is the right default choice for most use cases; LinkedList offers O(1) operations at either end but O(n) indexed access.
Vector is a legacy, synchronized alternative to ArrayList and is rarely the right choice in new code.
List.of(...) is immutable and rejects null; Arrays.asList(...) is fixed-size but writes through to the backing array on set().
Modify a List safely during iteration via Iterator.remove() or removeIf(), not by calling list methods directly inside a for-each loop.
List<Integer> nums = new ArrayList<>(List.of(10, 20, 30)); nums.remove(1); // removes the VALUE 1? or the index 1?
nums.remove(Integer.valueOf(1)); // remove the value 1, if present nums.remove(1); // remove the element AT index 1
For List<Integer>, remove(int) is interpreted as remove-by-index, not remove-by-value; use Integer.valueOf(...) to force the remove(Object) overload when you mean to remove by value.
for (String s: list) { if (s.startsWith("x")) list.remove(s); // ConcurrentModificationException } list.removeIf(s -> s.startsWith("x"));
Structurally modifying a List directly during a for-each loop throws ConcurrentModificationException; removeIf (or an explicit Iterator) is the safe way to remove matching elements.
List<String> l = Arrays.asList("a", "b", "c"); l.add("d"); // throws UnsupportedOperationException — fixed-size
List<String> l = new ArrayList<>(Arrays.asList("a", "b", "c")); l.add("d"); // fine, backed by a real resizable ArrayList
Arrays.asList returns a fixed-size list; add/remove throw UnsupportedOperationException. Wrap it in a real ArrayList first if you need a resizable, independent copy.
What two capabilities does List add on top of the base Collection interface?
Indexed (positional) access via get/set/add/remove by index, and a guaranteed iteration order matching element order, including permission for duplicate elements.
Why is get(index) O(1) for ArrayList but O(n) for LinkedList?
ArrayList is backed by a real array, so get(index) is direct array indexing; LinkedList is backed by linked nodes with no direct indexing, so reaching a given index requires walking node-to-node from the nearer end.
What is the main historical reason Vector is now considered legacy?
It predates the Collections Framework and synchronizes every method, adding locking overhead even in single-threaded use without making compound operations atomic; ArrayList (with explicit synchronization when needed) is now preferred.
What does Arrays.asList(...) return, and what operations does it not support?
A fixed-size List backed directly by the given array; it does not support add or remove (they throw UnsupportedOperationException) because the list's size cannot change, though set() is allowed and writes through to the array.
What is the difference between list.remove(1) and list.remove(Integer.valueOf(1)) for a List<Integer>?
list.remove(1) resolves to the remove(int index) overload, removing the element at index 1; list.remove(Integer.valueOf(1)) resolves to remove(Object), removing the first element equal to the value 1.
Interview: Given ArrayList's O(n) middle insertion versus LinkedList's O(1) splice-once-positioned, why is ArrayList still usually the better default?
Reaching the insertion point in a LinkedList itself costs O(n) (no random access), and ArrayList's contiguous memory layout is typically much more cache-friendly than scattered linked nodes, so in practice ArrayList often performs as well or better for many workloads; the theoretical Big-O advantage of LinkedList rarely pays off unless insertions/removals happen almost exclusively at the ends.
Write a method that takes a List<String> and returns a new List containing only the unique elements, preserving first-occurrence order.
static List<String> distinctPreserveOrder(List<String> input) { List<String> result = new ArrayList<>(); for (String s : input) { if (!result.contains(s)) { result.add(s); } } return result; }
Checking contains() before adding filters duplicates while iterating in original order; for large lists a LinkedHashSet would be more efficient than this O(n^2) approach.
What does this print?
[5, 15] — remove(1) with an int literal resolves to remove(int index), removing the element at index 1 (the value 10), not the value 1.
Write a program that builds an ArrayList of 1,000,000 integers and a LinkedList of the same size, then times how long get(size/2) takes on each, printing which is faster.
import java.util.*; public class ListTiming { public static void main(String[] args) { List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < 1_000_000; i++) { arrayList.add(i); linkedList.add(i); } int mid = 500_000; long t1 = System.nanoTime(); arrayList.get(mid); long arrayTime = System.nanoTime() - t1; long t2 = System.nanoTime(); linkedList.get(mid); long linkedTime = System.nanoTime() - t2; System.out.println("ArrayList get: " + arrayTime + "ns"); System.out.println("LinkedList get: " + linkedTime + "ns"); } }
ArrayList.get is expected to be dramatically faster since it's direct array indexing, while LinkedList.get(500_000) must walk half a million node links to reach the middle element.
List<Integer> nums = new ArrayList<>(List.of(5, 10, 15));
nums.remove(1);
System.out.println(nums);