Topic 10: Collections in Java - List

📖 8 min read · 🎯 advanced · 🧭 Prerequisites: strings-in-java, advanced-ui-concepts-themes-styles-localization

Why this matters

Up until now, you've probably stored data in simple variables — one box, one value. But what happens when you need to store ten items? A hundred? A list of products, a queue of messages, a history of user actions? That's where Java's List collections come in. There are four main types — ArrayList, LinkedList, Vector, and Stack — and each one handles data differently under the hood. Pick the right one and your Android app feels fast and clean. Pick the wrong one and you'll wonder why everything slows down. Let's sort that out right now.

What You'll Learn

How the List interface unifies ordered, index-based collections in Java
When to choose ArrayList over LinkedList and why the trade-offs matter
How Vector adds thread-safety and when that matters in Android apps
How Stack enforces LIFO ordering and where to apply it (e.g., undo operations)

The Analogy

Think of Java Lists as bookshelves — all designed to hold books, but built differently for different reading rooms. An ArrayList is a long continuous shelf: grab any book instantly by its slot number, but shuffling books around takes effort. A LinkedList is a chain of small shelves, each tagged with the address of the next one: rearranging is fast, but jumping straight to slot 47 means following the chain link by link. A Vector is a locked display case — every action requires a key, so two librarians can't collide, but the extra locking slows individual access. A Stack is the returns trolley by the front desk: the last book placed on top is the first one you pick up, no exceptions. The right shelf for the job keeps the library running smoothly; the wrong one creates chaos.

Chapter 1: The List Interface

Java's java.util.List interface defines an ordered collection (also called a sequence). Every element occupies a specific index position starting at 0. Because List is an interface, you never instantiate it directly — you choose one of its concrete implementations.

Key guarantees shared by all List implementations:

Elements are stored in insertion order.
Duplicate elements are allowed.
Random access is available via get(int index).
The size grows dynamically as elements are added.

The four most commonly used implementations:

Implementation	Backed by	Thread-safe	Best for
`ArrayList`	Resizable array	No	Random access, iteration
`LinkedList`	Doubly-linked nodes	No	Frequent insertions/deletions
`Vector`	Resizable array	Yes	Multi-threaded environments
`Stack`	Vector (LIFO)	Yes	Undo/redo, expression parsing

Chapter 2: ArrayList — The Dynamic Bookshelf

An ArrayList backs its elements with a plain Java array that resizes automatically when capacity is exceeded. It provides O(1) indexed access — the fastest option when you mostly read and iterate — but O(n) insertions and deletions at arbitrary positions because elements must be shifted.

Creating and Using ArrayList

The example below models a reading list. Notice the generic type parameter <String> that constrains the list to string values only.

import java.util.ArrayList;

public class ReadingList {
    private ArrayList<String> books;

    public ReadingList() {
        books = new ArrayList<>();
    }

    // Add a book to the list
    public void addBook(String book) {
        books.add(book);
        System.out.println("Added: " + book);
    }

    // Remove a book from the list
    public void removeBook(String book) {
        if (books.remove(book)) {
            System.out.println("Removed: " + book);
        } else {
            System.out.println("Book not found: " + book);
        }
    }

    // Display all books in the list
    public void displayBooks() {
        System.out.println("Reading List:");
        for (String book : books) {
            System.out.println("- " + book);
        }
    }

    public static void main(String[] args) {
        ReadingList readingList = new ReadingList();
        readingList.addBook("The Catcher in the Rye");
        readingList.addBook("To Kill a Mockingbird");
        readingList.displayBooks();
        readingList.removeBook("The Catcher in the Rye");
        readingList.displayBooks();
    }
}

What to watch: books.remove(book) removes by value, not by index. It returns true if the element was found and removed, which is how we drive the conditional output.

Chapter 3: LinkedList — The Flexible Bookshelf

A LinkedList stores each element in a node that holds the value plus references to the previous and next nodes (doubly-linked). This means inserting or removing at the head or tail is O(1) — no shifting required. The trade-off is that indexed access is O(n) because you must traverse the chain from one end.

LinkedList also implements the Deque interface, so it exposes methods like addFirst(), addLast(), peekFirst(), and pollLast() that ArrayList does not have.

Creating and Using LinkedList

Here a music playlist benefits from frequent additions at either end:

import java.util.LinkedList;

public class Playlist {
    private LinkedList<String> songs;

    public Playlist() {
        songs = new LinkedList<>();
    }

    // Add a song to the end of the playlist
    public void addSong(String song) {
        songs.add(song);
        System.out.println("Added: " + song);
    }

    // Add a song to the beginning of the playlist
    public void addFirstSong(String song) {
        songs.addFirst(song);
        System.out.println("Added to beginning: " + song);
    }

    // Remove a song from the playlist
    public void removeSong(String song) {
        if (songs.remove(song)) {
            System.out.println("Removed: " + song);
        } else {
            System.out.println("Song not found: " + song);
        }
    }

    // Display all songs in the playlist
    public void displaySongs() {
        System.out.println("Playlist:");
        for (String song : songs) {
            System.out.println("- " + song);
        }
    }

    public static void main(String[] args) {
        Playlist playlist = new Playlist();
        playlist.addSong("Imagine");
        playlist.addFirstSong("Bohemian Rhapsody");
        playlist.displaySongs();
        playlist.removeSong("Imagine");
        playlist.displaySongs();
    }
}

What to watch: addFirstSong calls songs.addFirst(song) — an O(1) head insertion that ArrayList cannot perform without shifting every existing element.

Chapter 4: Vector — The Thread-Safe Bookshelf

Vector is functionally identical to ArrayList in terms of its array-backed storage, but every public method is synchronized. This means only one thread can read or write at a time, making it safe for concurrent environments without additional locking on the caller's side.

The cost is performance: the synchronization overhead is paid on every single operation, even when only one thread is active. Modern Java code often prefers Collections.synchronizedList() or java.util.concurrent classes like CopyOnWriteArrayList for finer-grained control, but Vector remains part of the Java standard library and appears frequently in legacy Android codebases.

Creating and Using Vector

The example below tracks active users in a multi-threaded chat application:

import java.util.Vector;

public class ChatUsers {
    private Vector<String> users;

    public ChatUsers() {
        users = new Vector<>();
    }

    // Add a user to the list
    public synchronized void addUser(String user) {
        users.add(user);
        System.out.println("User added: " + user);
    }

    // Remove a user from the list
    public synchronized void removeUser(String user) {
        if (users.remove(user)) {
            System.out.println("User removed: " + user);
        } else {
            System.out.println("User not found: " + user);
        }
    }

    // Display all users in the list
    public synchronized void displayUsers() {
        System.out.println("Active Users:");
        for (String user : users) {
            System.out.println("- " + user);
        }
    }

    public static void main(String[] args) {
        ChatUsers chatUsers = new ChatUsers();
        chatUsers.addUser("Alice");
        chatUsers.addUser("Bob");
        chatUsers.displayUsers();
        chatUsers.removeUser("Alice");
        chatUsers.displayUsers();
    }
}

What to watch: The synchronized keyword appears both on the Vector methods internally and on the public methods here — a deliberate double-lock that ensures compound operations (check + modify) are atomic at the ChatUsers level.

Chapter 5: Stack — The Last-In-First-Out Bookshelf

Stack extends Vector and enforces LIFO (Last-In-First-Out) ordering. The primary operations are:

push(item) — place an item on top of the stack
pop() — remove and return the top item
peek() — inspect the top item without removing it
isEmpty() — check whether any items remain

Classic use cases include undo/redo systems, expression parsing, and navigation back-stacks — all scenarios where the most recent action is the first one you want to revisit.

Creating and Using Stack

Here a text editor uses a Stack to support undo:

import java.util.Stack;

public class TextEditor {
    private Stack<String> actions;

    public TextEditor() {
        actions = new Stack<>();
    }

    // Add an action to the stack
    public void addAction(String action) {
        actions.push(action);
        System.out.println("Action added: " + action);
    }

    // Undo the last action
    public void undoAction() {
        if (!actions.isEmpty()) {
            String lastAction = actions.pop();
            System.out.println("Action undone: " + lastAction);
        } else {
            System.out.println("No actions to undo.");
        }
    }

    // Display all actions in the stack
    public void displayActions() {
        System.out.println("Actions:");
        for (String action : actions) {
            System.out.println("- " + action);
        }
    }

    public static void main(String[] args) {
        TextEditor editor = new TextEditor();
        editor.addAction("Type 'Hello'");
        editor.addAction("Type 'World'");
        editor.displayActions();
        editor.undoAction();
        editor.displayActions();
    }
}

What to watch: actions.pop() both removes and returns the top element. The isEmpty() guard prevents a EmptyStackException when there is nothing left to undo.

Chapter 6: Choosing the Right List

flowchart TD
    A[Need a List?] --> B{Multi-threaded?}
    B -- Yes --> C{LIFO ordering?}
    B -- No --> D{Frequent insert/delete\nat head or middle?}
    C -- Yes --> E[Stack]
    C -- No --> F[Vector]
    D -- Yes --> G[LinkedList]
    D -- No --> H[ArrayList]

Quick decision rules:

Default choice for most Android work → ArrayList
Frequent head/tail insertions or deque behavior → LinkedList
Shared mutable list across threads in legacy code → Vector
Undo/redo, back-stack, LIFO history → Stack

🧪 Try It Yourself

Task: Build a BrowserHistory class that models a simplified browser back-button using a Stack<String>. It should support:

visit(String url) — push the URL onto the history stack and print "Visiting: <url>"
goBack() — pop the most recent URL and print "Going back to: <url>", or print "No history." if the stack is empty
A main method that visits three URLs then calls goBack() twice

Success criterion: Running main should print exactly five lines — three "Visiting" lines and two "Going back to" lines — with the URLs appearing in reverse visit order on the back calls.

Starter snippet:

import java.util.Stack;

public class BrowserHistory {
    private Stack<String> history = new Stack<>();

    public void visit(String url) {
        // TODO: push url and print
    }

    public void goBack() {
        // TODO: pop and print, or print "No history."
    }

    public static void main(String[] args) {
        BrowserHistory browser = new BrowserHistory();
        browser.visit("https://example.dev");
        browser.visit("https://example.dev/courses");
        browser.visit("https://example.dev/courses/android");
        browser.goBack();
        browser.goBack();
    }
}

🔍 Checkpoint Quiz

Q1. Why does ArrayList provide faster random access than LinkedList?

A) ArrayList uses a hash table internally
B) ArrayList stores elements in contiguous memory, so any index is reached in one step
C) ArrayList is synchronized, which speeds up reads
D) LinkedList stores elements in reverse order

Q2. Given the following code, what is printed on the last line of output?

import java.util.Stack;
Stack<Integer> s = new Stack<>();
s.push(10);
s.push(20);
s.push(30);
s.pop();
System.out.println(s.peek());

A) 10
B) 30
C) 20
D) An EmptyStackException is thrown

Q3. A developer is building an Android activity that maintains a list of recently connected Bluetooth devices. Multiple background threads can add and remove devices simultaneously. Which List implementation is the safest drop-in choice without adding external synchronization?

A) ArrayList
B) LinkedList
C) Stack
D) Vector

Q4. What is the key behavioral difference between addFirst() on a LinkedList and add(0, element) on an ArrayList when the list already contains 10,000 elements?

A1. B — ArrayList wraps a plain array; get(i) computes the memory address as base + i * elementSize in one operation. LinkedList must hop through node references from the head to reach index i.

A2. C — push(30) is called, then pop() removes 30, leaving 20 on top. peek() returns the top element without removing it, so 20 is printed.

A3. D — Vector synchronizes all its methods internally, making it safe for concurrent reads and writes without additional locking. ArrayList and LinkedList are not thread-safe; Stack is thread-safe (it extends Vector) but imposes LIFO semantics that don't fit a "recently connected" list.

A4. LinkedList.addFirst() is O(1) — it rewires two node pointers at the head. ArrayList.add(0, element) is O(n) — it must shift all 10,000 existing elements one position to the right to make room at index 0. At large scales this is a significant performance gap.

🪞 Recap

Java's List interface provides ordered, index-based, dynamically sized collections; ArrayList, LinkedList, Vector, and Stack are its four primary implementations.
ArrayList gives O(1) random access backed by a resizable array — the default choice for most read-heavy lists in Android.
LinkedList excels at O(1) head/tail insertions and deletions and also implements Deque, unlocking addFirst(), pollLast(), and similar methods.
Vector is a synchronized ArrayList — thread-safe out of the box, but slower due to per-method locking; useful in legacy multi-threaded contexts.
Stack enforces LIFO order via push() / pop() / peek() and is the right tool for undo systems, navigation history, and expression evaluation.

📚 Further Reading

Java List interface (Oracle docs) — the source of truth on every method in the List contract
Java Collections Framework overview — Oracle's official tutorial covering the full hierarchy
Effective Java, 3rd Edition — Item 28: Prefer lists to arrays — Joshua Bloch on why generics + lists beat raw arrays in modern Java
⬅️ Previous: Advanced UI Concepts: Themes, Styles & Localization
➡️ Next: Android Event Handling

Topic 10 : Collections in Java - List