Core Data Structures

Arrays & Linked Lists

The two fundamental ways to store a sequence: a contiguous array (fast random access, expensive middle insertion) versus a chain of linked nodes (fast insertion at a known point, no random access at all).

Array: O(1) indexed access, O(n) insert/remove in the middle (elements must shift), contiguous memory is cache-friendly
Singly-linked list: O(1) insert/remove at a known node, O(n) to reach any position, one extra pointer per element
Doubly-linked list adds backward traversal and O(1) removal given only a reference to the node, at the cost of a second pointer
Dynamic arrays (ArrayList) amortize growth to O(1) per append — see Amortized Analysis
On modern hardware, cache locality often makes arrays win in practice even for workloads that look insertion-heavy on paper

Array vs. singly-linked list vs. doubly-linked list
Operation	Array	Singly-linked	Doubly-linked
Access by index	O(1)	O(n)	O(n)
Insert/remove at front	O(n)	O(1)	O(1)
Insert/remove at end	O(1) amortized	O(n) (no tail ptr) / O(1) (with)	O(1)
Insert/remove at known node	O(n) shift	O(1) (forward only)	O(1)
Extra memory per element	none	1 pointer	2 pointers

A minimal singly-linked list node, and reversing it in place

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

static <T> Node<T> reverse(Node<T> head) {   // O(n) time, O(1) extra space
    Node<T> prev = null;
    while (head != null) {
        Node<T> next = head.next;   // save before overwriting
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;                    // new head
}

The reversal above is the canonical linked-list exercise because it forces you to hold three pointers (prev, head, next) at once — drop the temporary next and the list is severed. This is also where Fast Slow Pointers and other pointer-manipulation interview patterns live: linked lists reward careful, explicit bookkeeping because there is no index to fall back on.