Linear
Array Fundamentals
Contiguous memory, O(1) index access, O(n) insert and delete. The structure behind ArrayList and half of Java's collections.
Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation
What is Array?
Contiguous memory is the defining property — every element sits at a fixed offset from the base address, and the CPU can compute the location of any slot with a single formula: address = base + index × element_size. That formula is why index access costs O(1) regardless of array length. The trade-off: because no gaps exist between elements, inserting or deleting in the middle forces every element after the target to shift one position — an O(n) operation. A raw Java array (int[]) has a fixed capacity set at allocation time; ArrayList wraps such an array and doubles capacity when full, giving amortized O(1) appends at the cost of occasional O(n) resize copies. You encounter this structure everywhere in Java — ArrayList, HashMap's internal bucket array, and even the call stack itself are all backed by contiguous arrays.
Analogy: A row of numbered parking spaces in a lot. Every space is the same size, numbered from 0, and the attendant can drive straight to space 47 without checking any other space first — that is O(1) access. But if a VIP needs space 10 and it is taken, every car from space 10 onward must move one space to the right to make room — that is the O(n) insertion cost you pay for the privilege of instant lookup.
02
Section Two · Mental Model
How It Thinks
Elements stored at contiguous memory addresses
▶
Index access is O(1) — address formula needs no traversal
No gaps allowed between elements
▶
Insert or delete in the middle shifts every element after it — O(n)
Size fixed at allocation time (raw array)
▶
ArrayList doubles capacity when full — amortized O(1) add, O(n) resize
Elements laid out sequentially in memory
▶
CPU cache loads neighbouring elements automatically — iteration is fast
All elements are the same type and size
▶
Random access via formula: address = base + index × element_size
03
Section Three · Operations
Core Operations
Access by Index
Retrieves the element at a given position by computing its memory address directly — no traversal required.
Pseudocode
function get(array, index):
if index < 0 or index >= array.length:
throw IndexOutOfBounds // O(1) — bounds check return array[index] // O(1) — direct address
Access by Index — direct jump to index 3
Why O(1) is guaranteed:
- The CPU calculates the exact memory address using base + index × element_size and jumps there directly — it does not matter whether the array has 10 elements or 10 million.
- The JVM bounds-checks the index first, which is also O(1).
Linear Search
Scans elements one by one from the start until it finds the target or exhausts the array.
Pseudocode
function search(array, target):
for i from 0 to array.length - 1:
if array[i] == target:
return i // found at index i return -1 // O(n) — worst case full scan
When linear search beats binary search: Binary search needs a sorted array and costs O(log n) setup thinking — for arrays under ~20 elements, linear search is faster in practice because it has no branching overhead and plays well with the CPU cache.
Insert at End
Appends a new element after the last element — O(1) when capacity remains, O(n) when the internal array must be resized.
Pseudocode
function addLast(array, value):
if size == capacity:
resize() // O(n) — copy to new array (rare)
array[size] = value // O(1) — write at next open slot
size = size + 1 // amortized O(1)
Amortized O(1) — not O(1):
- Each individual append is O(1) except when a resize triggers — then it is O(n).
- But resizes happen so rarely (each doubles capacity) that the average cost per append over any sequence of n appends is O(1).
- This is what amortized means.
Insert at Middle
Places a new element at a given index by shifting every subsequent element one position to the right to create a gap.
Pseudocode
function addAt(array, index, value):
if size == capacity:
resize()
for i from size down to index + 1:
array[i] = array[i - 1] // shift right
array[index] = value
size = size + 1 // O(n) — dominated by the shift
Insert at Middle — insert 25 at index 2
Always shift right-to-left:
- The loop must run from the end of the array backward to the insertion index — not forward.
- Shifting forward overwrites elements before copying them, corrupting the array.
- Every insert-at-index implementation that runs the loop the wrong way loses data silently.
Delete at Middle
Removes the element at a given index by shifting every subsequent element one position to the left to close the gap.
Pseudocode
function removeAt(array, index):
for i from index to size - 2:
array[i] = array[i + 1] // shift left
size = size - 1
array[size] = null // clear last slot (GC hygiene) // O(n) — dominated by the shift
Delete at Middle — remove index 2 (value 30)
Null the last slot after deletion:
- After shifting left, the last slot still holds a reference to the old object.
- If you do not null it out, the array holds a stale reference the GC cannot collect — a memory leak that grows with every deletion.
- ArrayList handles this for you; manual implementations often miss it.
Resize
When the internal array is full, allocates a new array of double the capacity and copies all existing elements into it.
Pseudocode
function resize(array, oldCapacity):
newCapacity = oldCapacity * 2
newArray = new Array[newCapacity] // allocate doubled array for i from 0 to oldCapacity - 1:
newArray[i] = array[i] // copy each element return newArray // O(n) — copy dominates
Resize — capacity 4 → 8 (doubling)
Doubling is the key — not adding a fixed amount:
- If ArrayList grew by adding 10 slots each time, a list that reaches 10,000 elements would trigger 1,000 resizes — O(n²) total work.
- Doubling means the number of resizes is O(log n), and the total copy work across all resizes is O(n).
- That is why append is amortized O(1).
Common Mistake: Using an ArrayList when an int[] would do — and paying boxing cost on every operation. List<Integer> stores objects, not primitives. Every add() boxes the int into an Integer object on the heap; every get() unboxes it back. For a loop over a million numbers, this overhead is measurable. When the size is known and the type is primitive, int[] is always faster.
04
Section Four · Implementation
Build It Once
Build this from scratch once — it makes the mechanics concrete. In any real project or interview, reach for the built-in (Section 05).
Java — Array core mechanics
// Build once to understand the mechanics — use ArrayList in practice. public class DynamicArray {
private int[] data;
private int size;
public DynamicArray(int capacity) {
data = new int[capacity];
size = 0;
}
// O(1) — direct address calculation public int get(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
return data[index]; // no traversal — direct memory offset
}
// O(n) — must shift every element after index to the right public void addAt(int index, int value) {
if (size == data.length) resize();
// shift right-to-left to avoid overwriting for (int i = size; i > index; i--)
data[i] = data[i - 1];
data[index] = value;
size++;
}
// O(n) — must shift every element after index to the left public int removeAt(int index) {
int removed = data[index];
// shift left-to-right to close the gap for (int i = index; i < size - 1; i++)
data[i] = data[i + 1];
size--;
data[size] = 0; // clear stale slot return removed;
}
}
Array — Full Implementation
Java — Complete DynamicArray implementation
import java.util.Arrays;
public class DynamicArray<T> {
private Object[] data;
private int size;
private static final int DEFAULT_CAPACITY = 4;
public DynamicArray() { data = new Object[DEFAULT_CAPACITY]; size = 0; }
public DynamicArray(int capacity) { data = new Object[capacity]; size = 0; }
// O(1) — direct index access
@SuppressWarnings("unchecked")
public T get(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
return (T) data[index];
}
// O(1) — overwrite at known position public void set(int index, T value) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
data[index] = value;
}
// O(1) amortized — append at end, resize when full public void addLast(T value) {
if (size == data.length) resize();
data[size++] = value;
}
// O(n) — shift right from index onward public void addAt(int index, T value) {
if (index < 0 || index > size) throw new IndexOutOfBoundsException();
if (size == data.length) resize();
for (int i = size; i > index; i--)
data[i] = data[i - 1];
data[index] = value;
size++;
}
// O(n) — shift left to close the gap
@SuppressWarnings("unchecked")
public T removeAt(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
T removed = (T) data[index];
for (int i = index; i < size - 1; i++)
data[i] = data[i + 1];
data[--size] = null; // GC hygiene — prevent memory leak return removed;
}
// O(n) — linear scan public boolean contains(T value) {
return indexOf(value) != -1;
}
// O(n) — linear scan from index 0 public int indexOf(T value) {
for (int i = 0; i < size; i++)
if (data[i] != null && data[i].equals(value)) return i;
return -1;
}
// O(1) public int size() { return size; }
public boolean isEmpty() { return size == 0; }
// O(n) — allocate double, copy all elements private void resize() {
data = Arrays.copyOf(data, data.length * 2);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i < size - 1) sb.append(", ");
}
return sb.append("]").toString();
}
public static void main(String[] args) {
DynamicArray<Integer> arr = new DynamicArray<>(4);
// 1. Add elements
arr.addLast(10); arr.addLast(20); arr.addLast(30);
System.out.println(arr); // [10, 20, 30] // 2. Insert at middle
arr.addAt(1, 15);
System.out.println(arr); // [10, 15, 20, 30] // 3. Remove at index
arr.removeAt(2);
System.out.println(arr); // [10, 15, 30] // 4. Contains check
System.out.println(arr.contains(15)); // true
System.out.println(arr.contains(99)); // false // 5. Trigger resize — capacity was 4, adding 5th element forces doubling
arr.addLast(40); arr.addLast(50);
System.out.println(arr); // [10, 15, 30, 40, 50]
}
}
Python — Built-in list + manual DynamicArray
# Python's list IS a dynamic array — these are the key operations:
nums = [10, 20, 30]
nums.append(40) # O(1) amortized — add at end
nums.insert(1, 15) # O(n) — shifts elements right
nums.pop(2) # O(n) — shifts elements left
nums[0] # O(1) — direct index access 15 in nums # O(n) — linear scan # ─── Manual implementation for understanding ─── class DynamicArray:
def __init__(self, capacity=4):
self._data = [None] * capacity
self._size = 0 def __getitem__(self, index): # O(1) if index < 0 or index >= self._size:
raise IndexError("index out of range")
return self._data[index]
def append(self, value): # O(1) amortized if self._size == len(self._data):
self._resize()
self._data[self._size] = value
self._size += 1 def insert_at(self, index, value): # O(n) if self._size == len(self._data):
self._resize()
for i in range(self._size, index, -1):
self._data[i] = self._data[i - 1]
self._data[index] = value
self._size += 1 def remove_at(self, index): # O(n)
removed = self._data[index]
for i in range(index, self._size - 1):
self._data[i] = self._data[i + 1]
self._size -= 1
self._data[self._size] = None return removed
def __len__(self): # O(1) return self._size
def _resize(self): # O(n)
self._data = self._data + [None] * len(self._data)
def __str__(self):
return str(self._data[:self._size])
05
Section Five · Java Built-in
Use It In Java
IN JAVA
Use
ArrayList<T> — or int[] / T[] for fixed-size cases Import
import java.util.ArrayList; | Method | Complexity | Note |
|---|---|---|
add(value) | O(1) amort | Appends; triggers resize when full |
add(index, value) | O(n) | Shifts elements right from index |
get(index) | O(1) | Direct address — no traversal |
set(index, value) | O(1) | Overwrites in place |
remove(index) | O(n) | Shifts elements left, nulls last slot |
contains(value) | O(n) | Linear scan from index 0 |
indexOf(value) | O(n) | Returns -1 if not found |
size() | O(1) | Stored as a field — not counted |
⚠ Gotcha:
ArrayList<int> is a compile error — Java generics do not accept primitives. Use ArrayList<Integer> instead, which boxes every int into an Integer object on the heap. For large numeric lists this boxing cost is real and measurable — prefer int[] when the size is known and performance matters.
Choose Use ArrayList when the collection size changes at runtime or when you need contains(), indexOf(), or Collections.sort(). Use int[] / String[] when the size is fixed at creation time — raw arrays are faster, use less memory, and avoid boxing entirely.
06
Section Six · Decision Guide
Pick The Right Structure
Decision Flowchart
Comparison Table
| Structure | Access | Insert (middle) | Delete (middle) | Best For |
|---|---|---|---|---|
| int[] / ArrayList ← this | O(1) | O(n) | O(n) | Random access, iteration |
| LinkedList | O(n) | O(1)* | O(1)* | Frequent head/tail insert/delete |
| ArrayDeque | O(n) | O(1) head/tail | O(1) head/tail | Stack, queue, BFS/DFS |
| HashMap | O(1) avg | O(1) avg | O(1) avg | Key→value lookup, frequency count |
07
Section Seven · Practice
Problems To Solve
Two patterns unlock most array interview problems: two-pointer (works inward from both ends or uses a fast/slow pointer to track two positions simultaneously) and sliding window (maintains a subarray of variable or fixed size by moving both ends forward). Look for phrases like "pair", "subarray", "contiguous", "maximum window", or "minimum window" — they signal one of these two patterns.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Easy | two-pointer | Two Sum | A HashMap lets you check in O(1) whether the complement of each element has already been seen — one pass, no nested loop. |
| Easy | two-pointer | Contains Duplicate | A HashSet detects a duplicate the moment you try to add an element that already exists — O(1) per check. |
| Easy | sliding-window | Best Time to Buy and Sell Stock | Track the minimum price seen so far and the maximum profit achievable from it — one pass, two variables. |
| Medium | two-pointer | Product of Array Except Self | Two passes — left-to-right builds prefix products, right-to-left builds suffix products — no division needed. |
| Medium | sliding-window | Maximum Subarray | Kadane's: at each index decide whether to extend the current subarray or start fresh — whichever sum is larger. |
| Medium | reversal | Rotate Array | Three in-place reversals — whole array, first k elements, remaining — achieves rotation in O(1) extra space. |
Interview Pattern:
- Two-pointer and sliding window solve roughly 70% of array interview problems.
- Two-pointer works when the answer involves a pair or requires comparing elements from two positions.
- Sliding window works when the problem asks for a contiguous subarray — look for the words "maximum", "minimum", "longest", or "shortest" combined with "subarray" or "window".