Prof. (Dr. ) Harish Kumar MittalProfessor · Researcher · Educator

Project Based Learning in Java

List, ArrayList, and LinkedList

Ordered collections, indexed access, list operations, and implementation choice.

Lecture 2.1.1 CO3 aligned Unit 2 · Chapter 2.1

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

  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

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.