Course Outcome (CO) states what a learner should be able to do after the course; CO1 to CO5 label the five syllabus outcomes.
Learning outcome: Use the List interface, perform indexed list operations, and select ArrayList or LinkedList based on access and update requirements.
A List<E> stores an ordered sequence. It preserves encounter order, supports position-based access, and permits duplicate elements. These properties make lists useful for marks, names, transactions, and any data where order matters.
In simple terms: A list is a numbered row of seats. Seat numbers start at 0, each seat holds one value, and two seats may hold the same value. Nothing is rearranged unless the program asks for it.
Properties of a List
| Property | Meaning |
|---|---|
| Ordered | Iteration follows the list's encounter order |
| Indexed | Positions range from 0 to size() - 1 |
| Duplicates allowed | Equal values may appear more than once |
| Positional updates | Elements can be inserted, replaced, or removed by index |
List<String> names = new ArrayList<>();
names.add("Aarav");
names.add("Diya");
names.add("Aarav");
System.out.println(names); // [Aarav, Diya, Aarav]
System.out.println(names.get(1)); // Diya
Common List Methods
| Method | Purpose |
|---|---|
add(e) |
Appends an element |
add(index, e) |
Inserts an element at a position |
get(index) |
Returns the element at a position |
set(index, e) |
Replaces the element at a position |
remove(index) |
Removes the element at a position |
remove(object) |
Removes the first equal object |
indexOf(object) |
Returns the first matching index or -1 |
lastIndexOf(object) |
Returns the last matching index or -1 |
subList(from, to) |
Returns a view of a range; to is exclusive |
Be careful with List<Integer>: remove(1) removes the value at index 1, while remove(Integer.valueOf(1)) removes the value 1.
ArrayList
ArrayList<E> implements List<E> with a resizable internal array. It is the usual default list when a program needs fast indexed access and mostly appends elements.
In simple terms: An ArrayList is a row of numbered lockers. Jumping straight to locker 7 is instant. Squeezing a new locker into the middle is slow, because every locker after it has to shift one place along.
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo {
public static void main(String[] args) {
List<String> topics = new ArrayList<>();
topics.add("Collections");
topics.add("Maps");
topics.add("Threads");
topics.add(1, "Lists");
topics.set(2, "Sets");
System.out.println(topics);
System.out.println("First topic: " + topics.get(0));
}
}
Output:
[Collections, Lists, Sets, Threads]
First topic: Collections
ArrayList Performance Model
| Operation | Typical cost | Reason |
|---|---|---|
get(index) |
Constant time | Direct array access |
set(index, value) |
Constant time | Direct replacement |
Append with add(value) |
Amortised constant time | Most appends use available capacity |
| Insert/remove near beginning | Linear time | Later elements must shift |
Search with contains |
Linear time | Elements may need to be checked one by one |
The list's size is its number of elements. Its internal capacity is the number of positions currently allocated. Capacity grows automatically and is intentionally hidden from normal list logic.
In simple terms: Size is how many students are in the room; capacity is how many chairs have been laid out. When the chairs run out, the list quietly arranges a bigger room and moves everyone across. Use size() to count elements; capacity management does not change that count.
Constructors, Capacity and Class Hierarchy
| Expression | Result |
|---|---|
new ArrayList<>() |
Empty list; the documented default initial capacity is 10 |
new ArrayList<>(50) |
Empty list with capacity for at least 50 elements; size is still 0 |
new ArrayList<>(existing) |
New list containing the existing element references in order |
new LinkedList<>() |
Empty linked list |
new LinkedList<>(existing) |
New linked nodes containing the existing element references |
Application Programming Interface (API) defines the operations one software component can use to communicate with another.
The default ArrayList backing array can be allocated lazily. Capacity is an implementation detail, not the number returned by size(). Removing an element reduces size but does not automatically shrink capacity. ensureCapacity(n) reserves room; trimToSize() reduces spare capacity. Neither adds elements. See the ArrayList API.
ArrayList extends AbstractList and implements List, RandomAccess, Cloneable and Serializable. LinkedList extends AbstractSequentialList and implements List, Deque, Cloneable and Serializable. Both permit null and duplicates and are unsynchronised. RandomAccess marks efficient indexed access; it declares no methods.
LinkedList
LinkedList<E> is a doubly linked implementation of both List<E> and Deque<E>. Each element is stored in a node connected to neighbouring nodes.
It can act as a list, queue, or deque.
In simple terms: A LinkedList is a chain of people, each holding the hand of the one before and the one after. Once the position is known, inserting a new node changes a few links. Finding a position by index still requires walking the chain from an end.
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> tasks = new LinkedList<>();
tasks.addLast("Compile code");
tasks.addLast("Run tests");
tasks.addFirst("Read requirements");
System.out.println("Next: " + tasks.removeFirst());
System.out.println("Remaining: " + tasks);
}
}
Output:
Next: Read requirements
Remaining: [Compile code, Run tests]
Index-based access in a linked list requires traversal from the nearer end. Repeated calls such as linked.get(i) inside a loop can therefore be inefficient. Use an enhanced for loop or iterator for sequential traversal.
Why it matters: a for (int i = 0; ...) loop over a LinkedList re-walks the chain for every single index, so reading n elements costs roughly n × n steps. The enhanced for loop walks the chain only once.
More LinkedList Operations
| Operation | Behaviour |
|---|---|
getFirst() / getLast() |
Read an end element; throw if empty |
peekFirst() / peekLast() |
Read an end element; return null if empty |
removeFirst() / removeLast() |
Remove an end element; throw if empty |
pollFirst() / pollLast() |
Remove an end element; return null if empty |
addAll(index, values) |
Insert a collection at a position |
listIterator(index) |
Start traversal at a cursor position from 0 through size(), inclusive |
clone() |
Make a shallow structural copy; the elements remain shared |
Inserting or removing at a known node or through an already-positioned iterator is efficient. Finding a middle position first still takes linear time, so “LinkedList is always faster for insertion” is misleading. Prefer not to store null when using poll or peek, because null also means empty.
ArrayList vs LinkedList
| Decision factor | ArrayList |
LinkedList |
|---|---|---|
| Internal structure | Resizable array | Doubly linked nodes |
| Indexed reads | Fast | Requires traversal |
| Append at end | Efficient | Efficient |
| Add/remove at either end | End is efficient; front shifts elements | Efficient through deque methods |
| Memory overhead | Lower | Higher because nodes store links |
Implements Deque |
No | Yes |
| Typical use | General-purpose list | Queue/deque behaviour or frequent end operations |
Choose ArrayList for most general list work. Choose LinkedList when deque operations are central and the program does not depend on frequent random access. For a stack or queue that does not need null elements, ArrayDeque is often a suitable default; its operations are introduced in the collections-framework lesson.
Traversal Patterns
Use an index when the position matters:
for (int i = 0; i < topics.size(); i++) {
System.out.println(i + ": " + topics.get(i));
}
Use an enhanced for loop when only values matter:
for (String topic : topics) {
System.out.println(topic);
}
Use ListIterator when traversal must move in both directions or update elements during traversal.
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class ListIteratorDemo {
public static void main(String[] args) {
List<String> codes = new ArrayList<>(List.of("java", "sql", "git"));
ListIterator<String> iterator = codes.listIterator();
while (iterator.hasNext()) {
iterator.set(iterator.next().toUpperCase());
}
System.out.println(codes);
}
}
Output:
[JAVA, SQL, GIT]
In simple terms: an ordinary iterator moves forwards and may support removal. A ListIterator is a bookmark with a pen: set(...) replaces the element last returned by next() or previous(), and it can also travel backwards with hasPrevious() and previous().
Sorting a List
Lists can be sorted using their sort method.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class SortNames {
public static void main(String[] args) {
List<String> names = new ArrayList<>(List.of("Meera", "Aman", "Zoya"));
names.sort(Comparator.naturalOrder());
System.out.println(names);
}
}
Output:
[Aman, Meera, Zoya]
Common Mistakes
| Mistake | Result or correction |
|---|---|
Accessing index equal to size() |
Causes IndexOutOfBoundsException; the last index is size() - 1. |
Expecting LinkedList.get(i) to be constant time |
Indexed access traverses nodes. |
Removing an integer value with remove(1) |
Removes index 1; use remove(Integer.valueOf(1)) for the object. |
| Changing a list directly during a for-each loop | May cause ConcurrentModificationException; use an iterator or removeIf. |
Assuming List.of(...) is mutable |
It is unmodifiable; copy it into an ArrayList before updating. |
Practice
- Store five marks in an
ArrayList<Integer>, replace one mark, and print the average. - Insert a new name at index
1and remove the final name. - Use
LinkedListas a queue withaddLastandremoveFirst. - Sort a list of cities in reverse alphabetical order.
Quick Check
1. Can a List contain duplicate values?
Yes. A list preserves positions and allows equal values to appear multiple times.
2. Which implementation is normally preferred for frequent indexed reads?
ArrayList is normally preferred because it supports direct array-based indexed access.
3. Why can LinkedList act as a queue?
It implements Deque and provides operations such as addLast, peekFirst, and removeFirst.
4. What is the final valid index in a list of size 8?
The final valid index is 7.
Lecture Quiz
A program performs thousands of indexed reads and mostly appends new values. Which implementation is the better default?
ArrayList is the better default because indexed access is direct and appending is amortised constant time.
Summary
List represents an ordered, indexed sequence that permits duplicates. ArrayList uses a resizable array and is the general-purpose choice for fast indexed access. LinkedList uses linked nodes, also implements Deque, and is useful when operations at the ends are central.