List, ArrayList, and LinkedList

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

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

Be careful with List<Integer>: remove(1) removes the value at index 1, while remove(Integer.valueOf(1)) removes the value 1.

In simple terms: In a list of numbers, Java cannot guess whether 1 means "seat number 1" or "the number 1". A plain int is read as a position; wrapping it as Integer.valueOf(1) makes it a value.

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

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. Only size() is visible to your code.

LinkedList

LinkedList<E> is a doubly linked implementation of both List<E> and Deque<E>. Each element is stored in a node connected to neighboring 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. Inserting somebody in the middle only changes two handshakes, but reaching the seventh person means 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.

ArrayList vs LinkedList

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 pure stack or queue, ArrayDeque is also commonly preferred, but it is covered with queues later.

Rule of thumb: start with ArrayList. Move to LinkedList only when the program mainly adds and removes at the two ends and rarely jumps to a middle index.

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 is a bookmark you can only read. A ListIterator is a bookmark with a pen: set(...) overwrites the element just returned by next(), 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

Practice

1. Store five marks in an ArrayList<Integer>, replace one mark, and print the average.
2. Insert a new name at index 1 and remove the final name.
3. Use LinkedList as a queue with addLast and removeFirst.
4. Sort a list of cities in reverse alphabetical order.

Quick Check

Lecture Quiz

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.