Arrays and Linked Lists

Arrays

An array stores a fixed number of same-typed slots addressed by integer index. Java checks bounds at runtime. A dynamic array such as ArrayList maintains a backing array and grows it when capacity is exhausted.

Dynamic-array operation	Typical bound
Read or replace by index	Θ(1)
Append	amortized Θ(1), worst-case Θ(n)
Insert/remove near beginning	Θ(n)
Search unsorted values	Θ(n)

Resizing copies existing references into a larger array. Geometric growth makes the total copying cost across many appends linear, giving amortized constant append time.

Linked lists

A singly linked node stores a value and a reference to the next node. A doubly linked node also references its predecessor.

final class Node<T> {
    final T value;
    Node<T> next;

    Node(T value, Node<T> next) {
        this.value = value;
        this.next = next;
    }
}

Insertion after an already-known node is Θ(1). Finding that position remains Θ(n). This distinction prevents the misleading claim that arbitrary linked- list insertion is always constant time.

Choosing

Prefer a dynamic array for indexed access and cache-friendly iteration. Prefer a linked representation when the algorithm already holds node references and performs many local structural changes. In Java application code, ArrayList is usually the default sequence; select LinkedList only with evidence that its trade-offs fit the workload.

Exercises

1. Derive the amortized cost of doubling capacity.
2. Reverse a singly linked list and state a loop invariant.
3. Explain why indexed access in a linked list is Θ(n).