List Interface in Java: ArrayList vs LinkedList vs Vector (A Complete Deep Dive)

A deep dive into the List interface in Java, comparing ArrayList, LinkedList, and Vector — internals, performance, and when to use each.

• 1. Introduction
• 2. The List Contract: Ordered, Index-Based, Allows Duplicates
• 3. ArrayList Internals: The Resizable Array
• 4. LinkedList Internals: Doubly-Linked Nodes
• 5. Vector and Legacy Synchronization
• 6. Performance Comparison: get / add / remove / insert
• 7. When to Use Which Implementation
• 8. Structure at a Glance: Array vs Nodes
• 9. Real-World Scenarios
• 10. Common Mistakes and Edge Cases
• 11. Side-by-Side Code Example
• 12. Interview Questions and Insights
• 13. Conclusion

1. Introduction

The List interface in Java is one of the most widely used parts of the Java Collections Framework. Almost every real application keeps data in some kind of ordered sequence — a list of users, a queue of pending tasks, rows fetched from a database, or items in a shopping cart. Whenever order matters and duplicates are allowed, a List is usually the right tool for the job.

Java gives you three classic implementations of this interface: ArrayList, LinkedList, and Vector. They all honor the same contract, so you can swap one for another without changing the code that calls them. Underneath, however, they behave very differently. One is backed by a resizable array, another by a chain of nodes, and the third is a synchronized relic from the earliest days of Java.

In this deep dive, we will study the List contract, look inside each implementation, compare their performance for common operations, and finish with a practical decision guide and an interview question section. By the end, you will know not just what to pick, but why.

1.1 A Little History: Why Three Implementations Exist

It might seem odd that Java ships three classes that do almost the same thing. The reason is historical. Vector arrived first, in Java 1.0, long before anyone designed a unified collections library. It came bundled with its sibling Hashtable, and both were synchronized by default because early Java leaned heavily on built-in thread safety.

When Java 1.2 introduced the Collections Framework, the designers wanted clean, fast, unsynchronized building blocks. ArrayList became the modern array-backed list, and LinkedList offered a node-based alternative for end-heavy workloads. Vector was retrofitted to implement List, so the old code kept working, but it was effectively superseded. Understanding this timeline explains why Vector feels like an outlier: it is.

2. The List Contract: Ordered, Index-Based, Allows Duplicates

Before comparing implementations, it helps to understand what every List promises. The java.util.List interface extends Collection and adds the idea of positional access. This is the contract that ArrayList, LinkedList, and Vector all agree to follow.

2.1 Three Core Guarantees

A List provides three defining behaviors:

• Ordered. Elements keep their insertion order. The element you add first stays at index 0 unless you explicitly move or remove it.
• Index-based. Every element has a numeric position, starting from 0. You can read, replace, insert, or remove an element by its index.
• Allows duplicates. Unlike a Set, a List can hold the same value many times. Adding “apple” three times produces three separate entries.

Because of positional access, the List interface adds methods that Collection alone does not have, such as get(int index), set(int index, E e), add(int index, E e), and remove(int index).

Here is the contract in action, using a List reference so the same code works for any implementation:

import java.util.ArrayList;
import java.util.List;
 
public class ListContractDemo {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<>();
 
        fruits.add("Apple");   // index 0
        fruits.add("Banana");  // index 1
        fruits.add("Apple");   // duplicate allowed -> index 2
 
        System.out.println(fruits.get(1));   // Banana (index-based access)
        fruits.set(1, "Mango");              // replace at index 1
        fruits.add(1, "Orange");             // insert at index 1, shifts rest
 
        System.out.println(fruits);          // [Apple, Orange, Mango, Apple]
        System.out.println(fruits.size());   // 4 (duplicates counted)
    }
}

Notice that we declared the variable as List<String> rather than ArrayList<String>. Programming to the interface is a best practice: it lets you change the implementation later by editing just one line.

2.2 Views and subList

The List interface also offers subList(from, to), which returns a view onto a portion of the original list rather than a fresh copy. Changes to the sublist write straight through to the parent, and structural changes to the parent can invalidate the view. This is powerful for working on a slice without copying, but it surprises developers who expect an independent list.

Equality follows the contract, too. Two lists are equal when they contain the same elements in the same order, regardless of implementation. An ArrayList and a LinkedList holding identical elements in identical order are considered equal by equals(), which again shows that the contract, not the class, defines the behavior callers rely on.

3. ArrayList Internals: The Resizable Array

ArrayList is the implementation most developers reach for first, and for good reason. It is backed by a plain Java array and offers extremely fast random access. The word “resizable” is the key idea: a normal array has a fixed length, but an ArrayList grows automatically as you add elements.

3.1 The Backing Array

Internally, ArrayList stores its elements in an Object[] array called elementData. A separate size field tracks how many slots are actually used. The array capacity is usually larger than the size, leaving spare room for future additions, so the list does not have to grow on every single insert.

3.2 Default Capacity

When you create an ArrayList with the no-argument constructor, the backing array starts empty. On the first add call, it is lazily initialized to a default capacity of 10. This lazy initialization, introduced to save memory, means an unused ArrayList costs almost nothing until you actually add something to it.

If you already know roughly how many elements you will store, you can set the initial capacity up front and avoid repeated growth:

import java.util.ArrayList;
import java.util.List;
 
public class CapacityDemo {
    public static void main(String[] args) {
        // Default capacity (becomes 10 on first add)
        List<Integer> a = new ArrayList<>();
 
        // Pre-sized for ~1000 elements -> avoids repeated resizing
        List<Integer> b = new ArrayList<>(1000);
 
        for (int i = 0; i < 1000; i++) {
            b.add(i);   // no growth needed, capacity already reserved
        }
        System.out.println(b.size());  // 1000
    }
}

3.3 How Growth Works

When the backing array fills up, the ArrayList must grow. It creates a new, larger array and copies the existing elements into it. The growth formula increases capacity by roughly 50% (the new capacity is the old capacity plus half of it). So a list that starts at 10 typically grows to 15, then 22, then 33, and so on.

The copy step uses System.arraycopy, which is fast but still proportional to the number of elements. Most individual add calls are O(1), but the occasional resize is O(n). Averaged over many additions, this gives amortized O(1) appends — a phrase worth remembering for interviews.

Random access is the real strength here. Because the data lives in a contiguous array, get(index) is a single arithmetic operation and runs in constant time (O(1), no matter how large the list is.

3.4 Why Contiguous Memory Matters

There is a subtle reason ArrayList performs so well in practice, and it goes beyond Big-O. Modern CPUs read memory in blocks called cache lines. When elements sit next to each other in a contiguous array, reading one element pulls its neighbors into the cache for free. Iterating an ArrayList, therefore, enjoys excellent cache locality, and the processor can prefetch the next elements before you even ask for them.

A LinkedList cannot offer this. Its nodes are separate objects scattered around the heap, so walking the list means following references to unpredictable memory locations. Each hop risks a cache miss. This is why ArrayList frequently outruns LinkedList even in scenarios where the textbook Big-O looks identical, and it is an insight that impresses interviewers.

3.5 Reclaiming Unused Space with trimToSize

After growth, an ArrayList may hold a backing array larger than it needs. If a list grew to thousands of elements and then shrank, the spare capacity stays allocated. You can explicitly release it with trimToSize(), which shrinks the backing array to its current size. This is rarely necessary but useful for long-lived lists that have shed most of their elements.

import java.util.ArrayList;
 
public class TrimDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(10000);
        for (int i = 0; i < 5; i++) list.add(i);
 
        // Backing array can still hold 10000 elements internally
        list.trimToSize();   // shrink capacity down to size (5)
 
        // ensureCapacity does the opposite: pre-grow before a big batch
        list.ensureCapacity(2000);
        System.out.println(list); // [0, 1, 2, 3, 4]
    }
}

The companion method ensureCapacity(int) pre-grows the array before a known bulk insert, avoiding several intermediate resizes.

4. LinkedList Internals: Doubly-Linked Nodes

LinkedList takes a completely different approach. Instead of a single big array, it stores each element in a small object called a node. Every node stores the value and two references: one to the previous node and one to the next. This makes LinkedList a doubly-linked list.

4.1 The Node Structure

Conceptually, each node looks like the snippet below. A linked list keeps references to the first and last nodes, so it can access either end instantly.

// Simplified view of the internal node used by LinkedList
private static class Node<E> {
    E item;        // the stored value
    Node<E> next;  // reference to the next node
    Node<E> prev;  // reference to the previous node
 
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

4.2 Why There Is No Resizing

Because nodes are created one at a time, LinkedList never needs a capacity or a resize step. Adding an element simply means creating a node and updating a couple of references. There is no array copy, so adding or removing at the ends is genuinely O(1).

The trade-off is random access. To reach index i, the LinkedList must walk the chain node by node. It is slightly smart about this — it starts from whichever end is closer — but the work is still proportional to the distance, making get(index) an O(n) operation. Each node also carries memory overhead for its two references, so a LinkedList uses more memory per element than an ArrayList.

4.3 LinkedList Also Implements Deque

A detail many developers miss: LinkedList implements not only List but also Deque (a double-ended queue). That means it can act as a stack or a queue, with handy methods such as addFirst, addLast, peekFirst, pollLast, and offer.

import java.util.LinkedList;
 
public class DequeDemo {
    public static void main(String[] args) {
        LinkedList<String> dq = new LinkedList<>();
 
        dq.addFirst("B");      // [B]
        dq.addFirst("A");      // [A, B]
        dq.addLast("C");       // [A, B, C]
 
        System.out.println(dq.peekFirst()); // A
        System.out.println(dq.peekLast());  // C
 
        dq.pollFirst();        // removes A -> [B, C]
        System.out.println(dq); // [B, C]
    }
}

Because of this dual role, LinkedList is a reasonable choice when you need queue or stack behavior at the ends, even though it is rarely the best choice for a plain List.

4.4 How Traversal and Insertion Actually Work

To appreciate the trade-offs, picture inserting an element in the middle of a LinkedList. First, the list must locate the target index by walking from the nearest end — that traversal is the O(n) part. Once it arrives, the actual insertion is cheap: create a new node, point it to its two neighbors, and update those neighbors to point back to it. No elements move, no array is copied.

Contrast this with ArrayList, where accessing an index is instant, but the insertion itself shifts every subsequent element one slot to the right. The two classes essentially swap which half of the operation is expensive. This is why blanket statements like “LinkedList is faster for inserts” are misleading: it is only faster when you already hold a position, such as during iteration with a ListIterator, or when working at the ends.

A practical consequence is that calling get(index) inside a loop over a LinkedList is a classic performance trap. A loop that indexes 0, 1, 2, … turns an O(n) traversal into an O(n²) disaster because each gets restarted. Always iterate a LinkedList with an enhanced for loop or an iterator, never with an index counter.

import java.util.LinkedList;
import java.util.List;
 
public class TraversalTrap {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < 100_000; i++) list.add(i);
 
        // BAD: O(n^2) on a LinkedList -- each get() walks the chain
        // for (int i = 0; i < list.size(); i++) { use(list.get(i)); }
 
        // GOOD: O(n) -- single pass with the iterator
        for (int value : list) {
            // process value
        }
        System.out.println("Iterated " + list.size() + " items efficiently");
    }
}

5. Vector and Legacy Synchronization

Vector is the oldest of the three. It existed before the Collections Framework was introduced in Java 1.2 and was later retrofitted to implement the List interface. Like ArrayList, it is backed by a resizable array, so its access characteristics are similar. The big difference is that Vector is synchronized.

5.1 What Synchronization Means Here

Almost every public method on Vector is marked synchronized. This makes a single Vector operation thread-safe — two threads cannot run add on the same Vector at exactly the same moment. The downside is that this locking happens on every call, even in single-threaded code, which adds overhead and slows things down compared to ArrayList.

Another small difference is growth. By default Vector doubles its capacity when it runs out of space (100% growth) rather than growing by 50% like ArrayList, though you can tune this with a capacity increment.

5.2 Why It Is Considered Legacy

Per-method synchronization is rarely what you actually want. Locking each call individually does not make a sequence of calls safe. For example, checking isEmpty() and then calling get(0) are two separate locked operations; another thread can change the Vector in between. So Vector gives you the cost of locking without solving the harder concurrency problems.

Modern code prefers an unsynchronized ArrayList for single-threaded use, and proper concurrent tools when threads are involved. If you truly need a synchronized List, the recommended approach is to wrap an ArrayList:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class SyncListDemo {
    public static void main(String[] args) {
        // Preferred over Vector for a synchronized list today
        List<String> safeList =
            Collections.synchronizedList(new ArrayList<>());
 
        safeList.add("one");
        safeList.add("two");
 
        // Still must lock manually when iterating
        synchronized (safeList) {
            for (String s : safeList) {
                System.out.println(s);
            }
        }
    }
}

For high-concurrency scenarios where reads vastly outnumber writes, CopyOnWriteArrayList from the java.util.concurrent package is usually a better fit than Vector.

6. Performance Comparison: get / add / remove / insert

The clearest way to choose between these classes is to compare the time complexity of common operations. The table below summarises the typical Big-O behaviour. Remember that Big-O describes how cost grows with size, not the absolute speed — a constant-factor difference still matters in practice.

Operation	ArrayList	LinkedList	Vector
get(index)	O(1)	O(n)	O(1)
add(end) / append	O(1)*	O(1)	O(1)*
add(index) / insert	O(n)	O(n)**	O(n)
remove(index)	O(n)	O(n)**	O(n)
remove from front	O(n)	O(1)	O(n)
contains / search	O(n)	O(n)	O(n)
Thread-safe	No	No	Yes (per method)

* Appending is amortized O(1) for array-backed lists because of the occasional resize.

** For LinkedList, the actual node relinking is O(1), but reaching the target index first costs O(n), so insert and remove by index are O(n) overall. Inserting at the head or tail, by contrast, is O(1).

6.1 Reading the Table Carefully

ArrayList wins decisively on random access. LinkedList wins when you constantly add or remove at the front. For insert or remove in the middle, both are O(n) — ArrayList because it shifts array elements, and LinkedList because it must first traverse to the position. In real benchmarks, ArrayList often still beats LinkedList in the middle because array copying via System.arraycopy is extremely cache-friendly, while pointer chasing across scattered nodes is not.

7. When to Use Which Implementation

Big-O tables are useful, but day-to-day decisions are simpler than they look. Here is a practical guide grounded in how these classes actually perform.

7.1 Choose ArrayList When…

• You need fast random access by index (the most common case).
• You mostly add elements at the end and read them back.
• Memory efficiency matters — it has no per-node pointer overhead.
• In short: make ArrayList your default List unless you have a clear reason not to.

7.2 Choose LinkedList When…

• You frequently add or remove elements at the beginning or both ends.
• You need queue, stack, or deque behavior, since it implements Deque.
• You rarely access elements by a random index.

7.3 Choose Vector (Rarely) When…

• You are maintaining old code that already depends on it.
• You need a quick synchronized list and cannot use modern alternatives — though Collections.synchronizedList or CopyOnWriteArrayList is usually better.

As a rule of thumb: reach for ArrayList first, switch to LinkedList only when your access pattern is dominated by end operations, and treat Vector as legacy.

8. Structure at a Glance: Array vs Nodes

It helps to picture the two underlying structures. An ArrayList is one continuous block of slots, indexed by position. A LinkedList is a chain where each link knows only its neighbors. The table below contrasts them across the dimensions that actually drive your choice.

Aspect	ArrayList	LinkedList
Underlying structure	Resizable array	Doubly-linked nodes
Memory per element	Low (value only)	Higher (value + 2 refs)
Cache locality	Excellent	Poor
Random access	O(1)	O(n)
Add/remove at ends	O(1) amortized	O(1)
Resize cost	Occasional array copy	None
Extra interfaces	RandomAccess	Deque, Queue

Notice the RandomAccess marker interface on ArrayList. It carries no methods; it is simply a flag that tells algorithms “indexed access on this list is cheap.” Some library methods check for it and switch strategy accordingly, preferring index loops for ArrayList and iterators for LinkedList.

9. Real-World Scenarios

Theory becomes clearer with concrete situations. Here are common patterns and the implementation that fits each.

9.1 Rendering a Table of Database Rows

Suppose you fetch 5,000 order rows and display them in a paginated table, jumping to page 40 on demand. This is read-heavy with frequent indexed access and few insertions. ArrayList is the clear winner because page lookups translate directly into O(1) index access.

9.2 A Task Queue Processed in Order

Imagine a background worker that pulls jobs from the front of a queue and accepts new jobs at the back. Constant removal from the head is exactly where ArrayList struggles, since every removal shifts the remaining elements. A LinkedList used as a Deque, or better still the purpose-built ArrayDeque, handles this gracefully.

import java.util.LinkedList;
import java.util.Queue;
 
public class TaskQueueDemo {
    public static void main(String[] args) {
        Queue<String> jobs = new LinkedList<>();
        jobs.offer("email");   // enqueue at tail
        jobs.offer("report");
        jobs.offer("backup");
 
        while (!jobs.isEmpty()) {
            String job = jobs.poll();  // O(1) dequeue from head
            System.out.println("Processing: " + job);
        }
    }
}

9.3 A Shared List Across Threads

If several threads append to and read from one list, a raw ArrayList is unsafe, and a Vector is slow and only partially helpful. For mostly-read workloads, CopyOnWriteArrayList lets readers proceed without locking while writers copy the array. For balanced read/write, a Collections.synchronizedList wrapper with manual locking during iteration is appropriate.

10. Common Mistakes and Edge Cases

A few traps catch developers regardless of which implementation they choose.

10.1 Modifying a List While Iterating

Removing elements during a for-each loop throws a ConcurrentModificationException. The List detects structural changes through a modCount field and fails fast to protect you from unpredictable behavior. Use the iterator’s own remove() method instead.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
 
public class SafeRemoveDemo {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5));
 
        Iterator<Integer> it = nums.iterator();
        while (it.hasNext()) {
            if (it.next() % 2 == 0) {
                it.remove();   // safe removal during iteration
            }
        }
        System.out.println(nums); // [1, 3, 5]
    }
}

10.2 Fixed-Size Lists from Arrays

The list returned by Arrays.asList(…) is fixed-size. Calling add or remove on it throws UnsupportedOperationException. Wrap it in a new ArrayList if you need a mutable copy: new ArrayList<>(Arrays.asList(…)).

10.3 Boxing Overhead with Primitives

All List implementations store objects, not primitives. A List<Integer> autoboxes every int into an Integer object, which adds memory and CPU cost. For large numeric datasets, a primitive array or a specialized library can be far more efficient.

11. Side-by-Side Code Example

Because all three implement the same interface, the calling code is identical. Only the constructor changes:

import java.util.*;
 
public class ListSwapDemo {
    public static void main(String[] args) {
        List<String> a = new ArrayList<>();
        List<String> l = new LinkedList<>();
        List<String> v = new Vector<>();
 
        for (List<String> list : List.of(a, l, v)) {
            list.add("x");
            list.add("y");
            list.add(0, "head");   // insert at front
            System.out.println(list.getClass().getSimpleName()
                               + " -> " + list);
        }
    }
}

This interchangeability is exactly why coding to the List interface pays off: you can benchmark different implementations by changing a single line.

12. Interview Questions and Insights

List internals are a favorite interview topic because they reveal whether you understand data structures, not just API names. Here are common questions with concise, accurate answers.

12.1 Why is ArrayList faster than LinkedList for get(index)?

ArrayList stores elements in a contiguous array, so it can access elements directly at O(1) time. A linked list must walk node by node from the nearest end, which is O(n).

12.2 What is the default capacity of ArrayList, and when is it set?

The default capacity is 10. With the no-arg constructor, the backing array starts empty and is initialized to 10 only on the first add call — lazy initialization to save memory.

12.3 How does ArrayList grow?

When full, it allocates a new array that is about 50% larger and copies the elements using System.arraycopy. Appends are therefore amortized O(1).

12.4 Is Vector still recommended? What replaces it?

No. Vector synchronizes every method, which is slow and does not ensure the safety of compound operations. Use ArrayList for single-threaded code, Collections.synchronizedList for a simple synchronized wrapper, or CopyOnWriteArrayList for read-heavy concurrent access.

12.5 What is the difference between ArrayList and LinkedList for inserting in the middle?

Both are O(n). ArrayList shifts subsequent elements in the array; LinkedList first traverses to the index, then relinks nodes. In practice, ArrayList is often faster due to cache-friendly array copying.

12.6 Why does removing during a for-each loop throw an exception?

The list is fail-fast: it tracks structural changes via modCount and throws ConcurrentModificationException when the iterator detects an unexpected change. Use the iterator’s remove() method to delete safely.

12.7 Does LinkedList implement any interface besides List?

Yes. It also implements Deque, so it can be used as a queue or a stack with methods like addFirst, addLast, peekFirst, and pollLast.

12.8 What is the RandomAccess interface?

RandomAccess is a marker interface with no methods. ArrayList and Vector implement it to signal that indexed access is fast. Generic algorithms can test for it and choose an index-based loop for these lists, falling back to an iterator for sequential-access lists like LinkedList.

12.9 Why might ArrayList beat LinkedList even for middle inserts?

ArrayList shifts elements with System.arraycopy, a tight, cache-friendly block move. LinkedList must first traverse to the position, chasing scattered pointers and incurring cache misses. The constant factors usually favor ArrayList despite both being O(n).

12.10 How can you make an ArrayList thread-safe?

Wrap it with Collections.synchronizedList(new ArrayList<>()), and still synchronize manually while iterating. For read-heavy concurrency, prefer CopyOnWriteArrayList. Plain Vector is discouraged in new code.

13. Conclusion

The List interface in Java gives you an ordered, index-based, duplicate-friendly collection, and its three classic implementations each make a different trade-off. ArrayList is the all-around default, backed by a resizable array with O(1) random access and amortized O(1) appends. LinkedList shines when you work at the ends or need deque behavior, at the cost of slow indexed access and higher memory use. Vector offers the same array model as ArrayList, but with per-method synchronization that is now considered legacy.

If you remember one thing, let it be this: default to ArrayList, switch to LinkedList only when your access pattern truly favors end operations, and avoid Vector in new code. Understanding the internals — capacity, growth, nodes, and locking — turns that rule of thumb into a confident, informed decision.