You need the third line item, a page of orders, or the last matching SKU. Collection can tell you size and membership. It cannot tell you “element at i.” That extra is List.
List is an indexed Collection: duplicates allowed, encounter order is position, get / set / add(index) / remove(index) are the verbs. The class you new is how cheap those verbs are.
The Collections Roadmap owns optional operations, views vs copies, RandomAccess, and sequenced as a name. This post is the indexed contract, subList as a live window, and why LinkedList is still a List you should almost never index.
A List is a sequence you can address by index. RandomAccess is the marker that addressing is cheap.
List is Collection plus a position
List extends Collection and, on Java 21, SequencedCollection. First / last / reversed are the sequenced names; Sequenced Collections owns that vocabulary. This post owns indexes.
List<Order> open = new ArrayList<>();
open.add(placed); // append — Collection.add
open.add(0, rush); // insert at index — List only
Order first = open.get(0);
open.set(0, first);
Order removed = open.remove(0); // by index
int where = open.indexOf(placed);
int last = open.lastIndexOf(placed);add(e) appends. add(index, e) inserts and shifts. remove(index) returns the element that lived there. remove(Object) is the Collection method and returns boolean. Those two overloads collide on List<Integer> — more below.
| Method | Job |
|---|---|
get(i) / set(i, e) | Read or replace at an index |
add(i, e) / remove(i) | Insert or drop at an index (shifts neighbors) |
indexOf / lastIndexOf | First / last position, or -1 |
listIterator() / listIterator(i) | Bidirectional walk; set / add at the cursor |
subList(from, to) | Live view of [from, to) |
sort(comparator) | In-place stable sort |
replaceAll(operator) | In-place map over each index |
Indexes are zero-based. Out of range throws IndexOutOfBoundsException, not NoSuchElementException. getFirst() on an empty sequenced list throws NoSuchElementException — different method, different empty story; the sequenced post covers the ends.
List<LineItem> items = order.items();
LineItem second = items.get(1);
int giftAt = items.indexOf(new LineItem("SKU-GIFT", 1, BigDecimal.ZERO));indexOf uses equals. Two line items with the same components match even if they were not the same object. lastIndexOf is the same scan from the other end — useful when the same SKU can appear twice, which a List allows and a Set does not.
List<LineItem> items = new ArrayList<>();
items.add(new LineItem("SKU-A", 1, new BigDecimal("10.00")));
items.add(new LineItem("SKU-B", 2, new BigDecimal("4.00")));
items.add(new LineItem("SKU-A", 1, new BigDecimal("10.00")));
int firstA = items.indexOf(new LineItem("SKU-A", 1, new BigDecimal("10.00")));
int lastA = items.lastIndexOf(new LineItem("SKU-A", 1, new BigDecimal("10.00")));
// firstA == 0, lastA == 2 — two members, not oneDuplicates are not a bug on a List. Two identical line items are two rows in the basket. If that is not what you meant, you wanted a Set.
subList is a view
subList(from, to) is a window on the same storage, not a new ArrayList. Structural changes through the view write through to the parent.
List<Order> open = new ArrayList<>(allOrders);
List<Order> firstPage = open.subList(0, 2);
firstPage.clear(); // those two orders are gone from open
firstPage.add(replacement); // inserted into open at the windowsubList.clear() is the honest way to drop a range. You do not walk indexes backward deleting one by one. The roadmap named views vs copies; this is the list view you will actually ship wrong.
Need a copy? Allocate one:
List<Order> snapshot = new ArrayList<>(open.subList(0, 2));
snapshot.clear(); // open is unchangedsubList is a view, not a copy. Mutate the parent structurally (an add / remove that is not through the sublist) and the view fail-fasts.
List<Order> open = new ArrayList<>(allOrders);
List<Order> page = open.subList(0, 2);
open.add(rush); // structural change on the parent
page.get(0); // ConcurrentModificationExceptionset on the parent at an index inside the window is not a structural change; it writes through and the view stays valid. add / remove / clear on the parent are structural. The window is defined only as long as the parent’s structure stays still except via that window.
Note: from is inclusive, to is exclusive, and from == to is an empty view. subList(0, open.size()) is the whole list as a view — still not a copy. Out-of-range from / to throws IndexOutOfBoundsException at creation.
sort, replaceAll, listIterator
List.sort sorts in place. It is stable. Collections.sort(list, cmp) delegates here.
List<Order> open = new ArrayList<>(orders);
open.sort(Comparator.comparing(Order::total));
open.sort(Comparator.comparing(Order::customerEmail)
.thenComparing(Order::id));replaceAll writes a new value into every index. It is the in-place cousin of a stream map that you intend to keep as this same list.
List<String> skus = new ArrayList<>();
for (LineItem item : order.items()) {
skus.add(item.sku());
}
skus.replaceAll(String::toUpperCase);listIterator is how you rewrite or insert while you walk. Collection and Iterator introduced it as the list-only extra; the indexed form starts at i.
List<LineItem> items = new ArrayList<>(order.items());
ListIterator<LineItem> it = items.listIterator(items.size());
while (it.hasPrevious()) {
LineItem item = it.previous();
if (item.quantity() <= 0) {
it.remove();
}
}Walking backward from listIterator(size) is the cursor sitting past the last element, so previous() is the last item.
RandomAccess is a type, not a vibe
RandomAccess is a marker: get(i) is cheap. ArrayList implements it. LinkedList does not. The roadmap defined the word; the decision it changes is whether an index loop is honest.
void printIds(List<Order> orders) {
if (orders instanceof RandomAccess) {
for (int i = 0; i < orders.size(); i++) {
System.out.println(orders.get(i).id());
}
} else {
for (Order order : orders) {
System.out.println(order.id());
}
}
}On an ArrayList, get(i) is an array load. On a LinkedList, get(i) walks i nodes. A nested get(i) loop on a linked list is O(n²). JDK algorithms (Collections.binarySearch, Collections.sort on older paths) branch on this marker. Your code should too — or accept ArrayList and stop pretending every List is one.
LinkedList is a List. get(i) is still O(n). That is legal. It is also why LinkedList is almost never the default list. ArrayList owns growth and ensureCapacity. LinkedList owns the rare splice story. ArrayDeque owns ends.
Factories and Arrays.asList, only as far as List needs
List.of and List.copyOf are unmodifiable copies. They reject null. The factories post owns the catalog. Here you only need: they implement List, mutation throws UnsupportedOperationException, and they are not a view of a later-mutated source (copyOf copies).
Arrays.asList is a fixed-size view of the array: set writes through, add / remove throw. Collections and Arrays owns the rest of Arrays / Collections.
String[] ids = { "o-1", "o-2" };
List<String> view = Arrays.asList(ids);
view.set(0, "o-9"); // ids[0] is now "o-9"
view.add("o-3"); // UnsupportedOperationException — fixed size
List<String> of = List.of("o-1", "o-2");
of.set(0, "o-9"); // UnsupportedOperationException — unmodifiableList.of forbids nulls. Arrays.asList allows them. Both are List. Neither is new ArrayList<>().
Nulls are allowed by the interface
The List contract permits null elements. ArrayList and LinkedList accept them; List.of and List.copyOf do not.
List<Order> open = new ArrayList<>();
open.add(null); // legal for ArrayList
Order missing = open.get(0); // null — the next NPE is yoursNote: indexOf(null) is defined (it finds the first null). Code that assumes get(i) is a live Order still needs a null policy. Prefer keeping nulls out of domain lists; do not assume the interface did that for you.
Internals that change a decision
ArrayList is a growable array: get / set are O(1), insert or remove at i shifts the tail (O(n)), append is amortized O(1). LinkedList is nodes: ends are O(1), get(i) is O(n), and you only win when you already hold the node — which the List interface never hands you.
That shift is the decision. Inserting a rush order at index 0 on an ArrayList of ten thousand open orders copies every slot one to the right. The same insert on a LinkedList is a pointer swing — and then the next get(i) in a page renderer walks from the head again. Pick the class whose hot operation is cheap, not the class whose insert is cheap in isolation. ArrayList is the default because index and append dominate real list code.
subList on ArrayList stores an offset and a length into the parent array. That is why clear on the view can compact the parent in one shift, and why a parent add invalidates the view. new ArrayList<>(parent.subList(...)) copies those slots into new storage.
sort on ArrayList sorts the backing array (TimSort). sort on a non-RandomAccess list copies to an array, sorts, and writes back — because indexing the nodes would be the O(n²) path. The marker is the branch.
When List is the wrong type
- Uniqueness of SKUs or emails →
Set.list.containson thousands of ids is a scan. - Work handed to the next worker → Queue / Deque. Ends, not indexes.
- Lookup by order id →
Map. A list of pairs is a linear search. - “I need a list because I need a stack / queue” →
ArrayDeque, notLinkedListas aList. - A
LinkedListyou onlyget(i)→ you wantedArrayList.
Program to List on fields and parameters. new ArrayList<>() unless you have a measured reason not to. Do not use List as a parameter if the method will only contains for uniqueness — that method wanted a Set.
Interview lens
Interviewers want the view, the overload trap, and why LinkedList still implements List. Draw Collection → List, put subList as a window on the same array, put RandomAccess on ArrayList only.
Whiteboard one-liner. subList is a view; structural changes write through. Arrays.asList is fixed-size. LinkedList.get(i) is O(n) even though it is a List.
| Operation | ArrayList | LinkedList |
|---|---|---|
get(i) / set(i) | O(1) | O(n) |
add at end | amortized O(1) | O(1) |
add(0, e) | O(n) | O(1) |
remove(i) | O(n) shift | O(n) to find |
indexOf | O(n) | O(n) |
subList | O(1) view | O(1) view |
RandomAccess | yes | no |
| Question | Honest answer |
|---|---|
Is subList a copy? | No. It is a view. subList.clear() removes from the parent. Copy with new ArrayList<>(list.subList(...)). |
Arrays.asList vs List.of? | asList is a fixed-size view of an array (set ok, add not, nulls ok). List.of is unmodifiable, rejects nulls, not a view of a later-mutated array. |
Why is LinkedList a List if get(i) is O(n)? | List is the indexed contract, not a promise that indexing is O(1). RandomAccess is that promise. LinkedList does not implement it. |
What is RandomAccess? | A marker that get(i) is cheap. Algorithms (and you) should branch on it or require ArrayList. |
remove(int) vs remove(Object) on List<Integer>? | list.remove(1) removes index 1. list.remove(Integer.valueOf(1)) removes the element 1. Autoboxing does not save you — the int overload wins. |
| Do all lists allow null? | The interface allows them. ArrayList does. List.of does not. |
Does List.equals ignore order? | No. Same size, same elements, same order. Set.equals is the contract that ignores order. |
Wrong answer: “subList returns a new independent ArrayList.” It returns a window. If it allocated, clear on the result would not delete from the parent.
The overload trap in code:
List<Integer> quantities = new ArrayList<>(List.of(2, 1, 2));
quantities.remove(1); // removes index 1 → [2, 2]
quantities.remove(Integer.valueOf(2)); // removes the first 2 → [2]Cheat sheet
List indexed Collection; duplicates ok; order is position
Java 21 also SequencedCollection — ends live in the sequenced post
get/set address by index
add(i)/remove(i) shift neighbors on ArrayList
subList VIEW of [from, to); write-through; clear drops from parent
sort in-place, stable
replaceAll in-place per index
RandomAccess get(i) is cheap — ArrayList yes, LinkedList no
List.of unmodifiable, no nulls — factories post
Arrays.asList fixed-size view of an array; set ok, add not
nulls allowed by List; not by every impl
Do ArrayList as the default List
copy a subList when you need independence
Don't index a LinkedList in a loop
treat subList or Arrays.asList as new ArrayList
list.remove(1) on List<Integer> when you meant the value 1Do:
- Use
Listwhen position matters: pages, line items, stable encounter order. - Treat
subListas a window; copy when the parent must keep the range. - Check
RandomAccess(or requireArrayList) beforeget(i)in a hot loop.
Don’t:
- Assume every
Listis anArrayList. - Use
List.containsas uniqueness. - Call
addonArrays.asListorsetonList.of.
Wrap-up
List adds a position to Collection: get / set, index insert and remove, subList, in-place sort / replaceAll. subList and Arrays.asList are views. RandomAccess is the type-level hint that get(i) is cheap — ArrayList has it, LinkedList does not. Nulls are legal on the interface and rejected by List.of.
When the job is “is this SKU already here?” you are no longer indexing. That job is Set.