List Interface

The List interface represents an ordered sequence of elements. Elements maintain insertion order, support index-based access, and duplicates are allowed.

Key Properties

• Ordered — elements stay in the order you insert them
• Indexed — access any element by position: list.get(2)
• Duplicates allowed — [a, b, a] is valid
• Null allowed — in most implementations

Implementation Comparison

Operation	ArrayList	LinkedList
Random access get(i)	O(1)	O(n)
Insert at end	O(1)*	O(1)
Insert at beginning	O(n)	O(1)
Insert at middle	O(n)	O(n)**
Delete at end	O(1)	O(1)
Delete at beginning	O(n)	O(1)
Search contains()	O(n)	O(n)
Memory per element	Low	High (prev/next pointers)
Thread-safe	No	No

*Amortized — O(n) during resize. **O(1) if you already have a reference to the node via Iterator.

Core List Methods

List<String> list = new ArrayList<>();

list.add("Apple");              // append
list.add(1, "Orange");          // insert at index
list.set(0, "Mango");           // replace at index

String item = list.get(0);      // access by index
int idx = list.indexOf("Mango"); // first occurrence

list.remove(0);                 // remove by index
list.remove("Orange");          // remove first occurrence of object

List<String> sub = list.subList(0, 2);  // view, not a copy

list.sort(Comparator.naturalOrder());
list.replaceAll(String::toUpperCase);

ArrayList

The go-to List implementation for most use cases. Backed by a dynamic array.

ArrayList<String> list = new ArrayList<>();         // default capacity 10
ArrayList<String> list = new ArrayList<>(100);      // pre-size if you know the count
ArrayList<String> list = new ArrayList<>(existing);  // copy from another collection

When to use: Almost always. Random access is O(1), appending is fast, and memory overhead is low. This should be your default unless you have a specific reason for LinkedList.

Resizing: When the internal array fills up, ArrayList allocates a new array ~1.5x the size and copies everything over. Pre-sizing avoids this if you know the approximate count.

LinkedList

A doubly-linked list that also implements Deque. Each element is a separate node with prev/next pointers.

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

// Deque methods — O(1) at both ends
list.addFirst("start");
list.addLast("end");
list.removeFirst();
list.removeLast();

// Also works as a Queue
list.offer("item");       // add to tail
list.poll();              // remove from head
list.peek();              // look at head

When to use: Only when you frequently insert/remove at the beginning of the list, or when you need Queue/Deque behavior. For almost everything else, ArrayList is faster in practice due to cache locality.

Avoid: list.get(500) on a LinkedList — it traverses from the head, making indexed access O(n).

Creating Immutable Lists

// Java 9+ — truly immutable, throws UnsupportedOperationException on mutation
List<String> immutable = List.of("a", "b", "c");

// Arrays.asList — fixed-size but elements are mutable
List<String> fixed = Arrays.asList("a", "b", "c");
// fixed.add("d");    // throws UnsupportedOperationException
// fixed.set(0, "x"); // works fine

// Unmodifiable wrapper
List<String> unmod = Collections.unmodifiableList(mutableList);

When to Use Which

Scenario	Use
General-purpose list	ArrayList
Frequent random access	ArrayList
Frequent insert/remove at head	LinkedList
Need Queue or Deque behavior	LinkedList or ArrayDeque
Thread-safe list	Collections.synchronizedList() or CopyOnWriteArrayList
Immutable list	List.of(...)