1. Introduction to the Java List Interface
The List<E> interface is part of the Java Collections Framework. It represents an ordered sequence of elements in which each element occupies a position identified by a zero-based index. Unlike a Set, a list can contain duplicate elements.
A list is useful whenever both the order of elements and their positions matter. Examples include a shopping cart, a recently viewed products history, a playlist, a sequence of tasks, or a list of order line items. If the same product appears twice in a list, both occurrences can remain because each occupies its own position.
The <E> notation is a generic type parameter. It means a list can be declared to store elements of a chosen type, such as List<String> for strings or List<Integer> for integer wrapper objects. Generics help the compiler catch incompatible element types and make collection code safer.
Main characteristics of a List
- Ordered: A list maintains a defined sequence. Standard list implementations preserve positional order as elements are inserted or rearranged.
- Indexed: The first position is index
0, the second is index1, and so on. - Duplicates allowed: Equal values can occur at multiple positions.
- Positional modification: Elements can be inserted, replaced, or removed using an index.
- Iteration support: Lists can be traversed with loops and iterators.
2. Where List Fits in the Collections Hierarchy
List extends Collection, and Collection extends Iterable. Each level adds a different set of capabilities.
Iterable<E>provides the foundation for obtaining an iterator and supports enhancedforloops.Collection<E>defines general collection operations such as adding, removing, checking membership, measuring size, and clearing elements.List<E>adds the concept of position: get or replace an element at an index, insert at a position, remove by index, search for positions, and obtain a bidirectionalListIterator.- Concrete classes provide different storage strategies and performance characteristics.
A Map<K, V> is also part of the Java Collections Framework, but it does not extend Collection. A map stores key-value associations rather than a sequence of elements. This distinction matters when selecting the right data structure.
3. How Indexing Works
List indexes begin at zero. For a list containing five items, valid indexes range from 0 through 4; the final index is generally size() - 1.
| Index | Item |
|---|---|
| 0 | Notebook |
| 1 | Pen |
| 2 | Eraser |
| 3 | Pen |
| 4 | Stapler |
The two occurrences of Pen are allowed. They are equal values at separate positions. An index identifies a slot, not a unique value.
This leads to two useful distinctions:
- Position and value are different concepts. A list can contain the same value at more than one index.
- Changing a position can affect later indexes. Inserting an element in the middle shifts following elements to the right; removing one shifts later elements to the left.
Attempting to access an index outside the valid range generally causes IndexOutOfBoundsException. For an empty list, there is no valid element index.
4. Methods Added by List
The following methods distinguish List from a general Collection.
| Method | Purpose | Important detail |
|---|---|---|
get(int index) | Reads the element at a position | Does not modify the list |
set(int index, E element) | Replaces an element | Returns the previous element; size stays the same |
add(int index, E element) | Inserts at a position | Existing elements at and after that position shift right |
remove(int index) | Removes the element at a position | Returns the removed element; later elements shift left |
indexOf(Object o) | Finds the first matching position | Returns -1 when no match exists |
lastIndexOf(Object o) | Finds the last matching position | Useful when values repeat |
subList(int from, int to) | Produces a range view | Start is inclusive; end is exclusive |
listIterator() | Creates a list-specific iterator | Supports forward/backward traversal and controlled changes |
List also inherits general methods from Collection, including add(E), remove(Object), contains(Object), size(), isEmpty(), and clear().
General insertion versus positional insertion
add(element) appends an element according to the implementation's list behavior, normally at the end. add(index, element) inserts it at a specified position. If the index is already occupied, the existing element is not overwritten; it and subsequent elements move right.
Replacement versus insertion
set(index, element) replaces the existing element at that index. It does not increase the list size. By contrast, add(index, element) inserts an additional element and increases the size by one.
Removing by index versus removing by value
List inherits remove(Object) from Collection and also defines remove(int index). These overloads are particularly easy to confuse with numeric wrapper types.
For a List<Integer>, remove(1) selects remove(int) and removes the element at index 1. To remove the integer value 30, use remove(Integer.valueOf(30)), which selects remove(Object). The compiler selects an overload according to the argument's type, not the programmer's intended meaning.
This overload issue most commonly affects List<Integer>, List<Long>, and other lists of numeric wrapper types. It does not arise in the same way with List<String> because a string argument cannot be interpreted as an integer index.
5. Searching for Elements
indexOf(value) searches from the beginning and returns the first matching index. lastIndexOf(value) searches from the end and returns the final matching index. If the value is absent, both methods return -1.
The comparison is based on equals, not simply whether two references point to the same object. For strings and standard wrapper classes, equality behavior is already defined. For custom classes, implementing equals correctly is important if list searches are expected to identify logically equivalent objects.
Searching a list is generally a linear operation: in the worst case, Java must examine many or all elements. If an application repeatedly needs to test membership, a Set may be a better fit. If it repeatedly retrieves a value using a key, a Map is often more suitable.
6. Understanding subList: A View, Not a Copy
subList(from, to) represents a portion of the original list. The from index is included, while the to index is excluded. For example, subList(1, 4) covers the original positions 1, 2, and 3.
A crucial detail is that subList returns a view, not an independent copy. Replacing an element through the view is reflected in the backing list. This is convenient when working with a range without copying all its elements.
However, the view remains connected to the original list. Structural changes to the backing list made outside the view while the view is in use can make subsequent view operations fail with ConcurrentModificationException. Avoid independently changing the structure of the parent list while relying on a sub-list view.
When an independent list is required, copy the range into a new list, for example:
The new ArrayList has its own list structure. The elements themselves are not automatically deep-copied; if they are mutable objects, both lists may still refer to the same objects.
7. The Four Classic List Implementations
List is an interface, so application code normally creates an instance of a class that implements it. The standard implementations differ in how they store elements and what operations they make efficient.
| Implementation | Internal approach | Strengths | Limitations and modern guidance |
|---|---|---|---|
ArrayList | Resizable array | Fast indexed access; efficient append in typical use | Insertions/removals near the beginning or middle require shifting elements |
LinkedList | Doubly linked nodes | Efficient operations at the ends; can insert/remove through an already-positioned iterator | Finding an index requires traversal; indexed loops can be slow |
Vector | Resizable array with synchronized methods | Legacy thread-synchronized collection | Usually not the first choice for new code |
Stack | Extends Vector and adds stack operations | Legacy push, pop, and peek API | Prefer ArrayDeque for typical new stack implementations |
ArrayList
ArrayList is backed by a resizable array. It is generally the default choice when an application needs a list because indexed reads are fast and appending is efficient on average. It is suitable for displaying records, retaining ordered results, and maintaining a sequence that is read frequently.
Inserting or removing in the middle can require moving later elements to preserve the sequence. This is why frequent positional edits can cost more than reads.
LinkedList
LinkedList stores elements in linked nodes. It can perform operations at the ends efficiently, and inserting or removing through a ListIterator at a known position avoids shifting an array. However, finding an arbitrary index requires walking through nodes.
Choosing LinkedList solely because an application inserts or removes elements frequently is not enough. If the application repeatedly asks for get(i), the traversal cost can dominate. The actual access pattern should drive the choice.
Vector
Vector is an older resizable-array implementation whose methods are synchronized. It remains available for compatibility with older Java code, but it is rarely the preferred option in new designs. Synchronizing individual methods does not automatically make a larger multi-step workflow atomic.
Stack
Stack extends Vector and provides last-in, first-out operations such as push, pop, and peek. For new code that needs a stack, ArrayDeque is usually preferred because it offers a modern deque API without inheriting the legacy Vector design.
8. Declare Variables Using the List Interface
A common Java practice is to declare a variable using the interface type while creating an instance of a concrete implementation. For example:
The declared type is List<String>, while the actual object is an ArrayList<String>. This separates the program's dependency on the list contract from the implementation choice.
If the requirements later favor another implementation, the construction line may be changed while most code using standard List methods remains the same. This flexibility works best when the rest of the program does not rely on implementation-specific behavior.
9. List vs Set vs Map
List, Set, and Map all organize data, but each expresses a different relationship.
| Feature | List<E> | Set<E> | Map<K, V> |
|---|---|---|---|
| Main purpose | Ordered sequence | Collection of unique elements | Key-value associations |
| Duplicates | Allowed | Duplicate elements not allowed | Keys unique; values may repeat |
| Typical access | By index or value search | Membership by value | By key |
| Ordering | Positional order is part of the contract | Depends on implementation | Depends on implementation |
| Common example | Recently viewed products | Unique wishlist product IDs | Product ID mapped to product details |
Choose a List when order and repeated entries matter. Choose a Set when uniqueness or membership checks are central. Choose a Map when each item needs to be found through a key, such as a product ID, email address, or coupon code.
A HashSet does not promise a particular iteration order. If order is important, select a suitable ordered implementation or use a List, depending on whether duplicates should be allowed. Likewise, not every Map implementation preserves insertion order; ordering behavior depends on the concrete type.
10. Iterating Over a List
Iteration means visiting the elements of a collection one by one. Java offers several patterns, and the best choice depends on whether the code needs indexes, only values, reverse traversal, or safe modification while traversing.
10.1 Index-based for loop
An index-based loop provides direct access to the current position. It is useful when the index is part of the output, when comparing neighboring elements, or when the algorithm needs positional operations.
For an ArrayList, indexed reads are efficient. For a LinkedList, repeatedly calling get(i) walks through nodes; doing this for every index can make a full loop take quadratic time, often described as O(n²). Therefore, avoid a get(i) loop for a LinkedList when a sequential traversal would suffice.
10.2 Enhanced for-each loop
The enhanced for loop is usually the clearest choice when code only needs each element's value. It works efficiently across list implementations because it uses iteration rather than repeatedly requesting each index.
A limitation is that the loop does not expose an index variable. Also, structurally modifying the list directly from inside a for-each loop—for example, calling cart.remove(item)—can cause ConcurrentModificationException for standard fail-fast implementations. Use an iterator's supported removal operation or another appropriate approach instead.
10.3 ListIterator
ListIterator is a list-specific iterator with more capabilities than a basic Iterator. It supports:
- Forward traversal using
hasNext()andnext(). - Backward traversal using
hasPrevious()andprevious(). - Position information through methods such as
nextIndex()andpreviousIndex(). - Replacing the last returned element with
set(). - Inserting with
add()and removing withremove()through the iterator's supported protocol.
This is especially useful when a list must be edited as it is traversed. Use the iterator's own modification methods rather than independently changing the list during iteration.
11. Performance: Choose Based on the Operation
Big-O notation describes how an operation's cost grows as the list grows. These are typical characteristics, not guarantees for every possible workload.
| Operation | ArrayList | LinkedList |
|---|---|---|
| Get by index | O(1) | O(n) in the general case |
| Append at end | Amortized O(1) | O(1) |
| Insert/remove at front | O(n) due to shifting | O(1) once the end position is available |
| Insert/remove at a known iterator position | May require shifting | O(1) for the local link change |
| Search by value | O(n) | O(n) |
For LinkedList, locating an arbitrary index or value still takes time. Its local insertion/removal advantage applies once the relevant node or iterator position has been reached. For ArrayList, appending is amortized constant time because occasional resizing can copy elements.
In many ordinary applications, ArrayList is the sensible starting point. Consider LinkedList when its end-operation or iterator-position characteristics match the workload, and evaluate actual performance if the choice matters significantly.
12. Common Mistakes to Avoid
- Using an invalid index: A list of size
nhas valid element indexes from0ton - 1. - Confusing
setandadd:setreplaces an element; indexedaddinserts a new element and shifts following elements. - Confusing
remove(int)andremove(Object): With numeric wrapper lists, make the intended overload explicit. - Assuming
subListcreates a copy: It creates a view connected to the original list. - Modifying a list directly inside a for-each loop: Use iterator-supported modification or a suitable alternative.
- Using indexed loops on
LinkedList: Repeated indexed access can cause quadratic traversal time. - Assuming a
SetorMapalways preserves order: Ordering depends on the concrete implementation. - Using a list for frequent key lookups: Consider a map when a stable key identifies the desired value.
- Assuming synchronization makes a workflow thread-safe: Synchronized individual operations do not necessarily protect a sequence of related operations.
13. Best Practices
- Prefer
List<E>for variable declarations and select an implementation based on the access pattern. - Start with
ArrayListfor general-purpose ordered sequences unless requirements suggest otherwise. - Use indexes deliberately and validate bounds when they are derived from external input.
- Use
indexOfandlastIndexOfwhen locating positions is meaningful; use aSetorMapfor repeated membership or keyed lookup needs. - Treat
subListas a backed view and avoid conflicting structural modifications to its parent. - Use enhanced for-each for simple sequential reading, index loops when position matters, and
ListIteratorwhen bidirectional traversal or iterator-controlled edits are required. - Avoid legacy
VectorandStackin new designs unless compatibility requirements justify them; considerArrayDequefor stack behavior. - Implement
equalsconsistently for custom element types when list search and removal should be based on logical equality.
14. Quick Revision
List<E>extendsCollection<E>and represents an ordered, indexed sequence.- Indexing begins at
0; duplicates are allowed. getreads,setreplaces, indexedaddinserts, and indexedremoveremoves by position.indexOfreturns the first match;lastIndexOfreturns the last; both return-1when not found.subList(from, to)includesfrom, excludesto, and returns a view rather than a copy.ArrayListoffers fast indexed access;LinkedListoffers efficient end operations but slow indexed access.VectorandStackare legacy classes;ArrayDequeis generally preferred for new stack use cases.- Use
Listfor ordered sequences,Setfor unique membership, andMapfor key-value lookup. - Prefer for-each for straightforward traversal and
ListIteratorfor bidirectional traversal or controlled edits.
15. Conclusion
The Java List interface is the right abstraction when an application needs a sequence whose elements have positions and may repeat. Its index-based methods provide more control than the general Collection contract, while its implementations offer different performance trade-offs.
Understanding the distinction between insertion and replacement, index-based and value-based removal, and a sub-list view versus an independent copy prevents common bugs. Choosing between ArrayList, LinkedList, Set, and Map should follow the operations the application performs most often—not just the fact that each can store multiple items. For most ordinary list requirements, ArrayList is a practical default, with other structures selected when their specific behavior better matches the task.
