Data Structures Fundamentals
An array is a contiguous block of memory that stores elements of the same type, one after another, with no gaps.
Think of it like a row of numbered lockers in a hallway — they're all the same size, all next to each other, and you can jump directly to any locker by its number.
Because elements are stored contiguously (back-to-back in memory), the computer can calculate exactly where any element lives using simple arithmetic.
Each element occupies a fixed number of bytes. The array starts at a base address and elements follow sequentially.
int[] arr = {10, 20, 30, 40, 50}; — each int = 4 bytes
To access arr[i], the CPU performs:
Unlike a linked list where you'd have to walk through each node one by one, an array lets you jump directly to any position. The hardware can compute the exact memory address in a single step.
| Operation | Time Complexity | Why? |
|---|---|---|
| Access by index | O(1) | Direct address calculation |
| Search (unsorted) | O(n) | Must check each element |
| Insert at index | O(n) | Shift all elements after |
| Append (at end) | O(1)* | Amortized — occasional resize |
| Delete at index | O(n) | Shift all elements after |
* Append is amortized O(1) because dynamic arrays double their capacity when full. Most appends are O(1), but the occasional resize copies all elements — averaged out, it's still constant.
// Fixed-size array int[] arr = new int[5]; // With values int[] arr = {10, 20, 30, 40, 50}; // Dynamic (ArrayList) ArrayList<Integer> list = new ArrayList<>();
# Python lists are dynamic arrays arr = [10, 20, 30, 40, 50] # Empty list arr = [] # Pre-filled arr = [0] * 5
int value = arr[2]; // 30
value = arr[2] # 30
// ArrayList only (arrays are fixed-size) list.add(2, 25); // insert 25 at index 2
arr.insert(2, 25) # insert 25 at index 2
list.remove(2); // remove at index 2
del arr[2] # remove at index 2 arr.pop(2) # same, but returns value
for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } // Enhanced for loop for (int num : arr) { System.out.println(num); }
for i in range(len(arr)): print(arr[i]) # Pythonic way for num in arr: print(num)
Basic array manipulation — shift elements in place. Uses everything we just covered.
Open on LeetCode →From contiguous memory to scattered nodes connected by references
A linked list is a collection of nodes scattered throughout memory, where each node stores data and a reference (pointer) to the next node.
Unlike arrays, nodes don't sit next to each other in memory. They can be anywhere on the heap — connected only by the addresses they store.
No index math is possible. To reach node #5, you must start at the head and follow 5 pointers. There's no shortcut.
Each node lives at a random memory address. The next field stores the address of the following node.
Nodes at addresses 0x100, 0x2F0, 0x4A8, 0x710 — scattered, not contiguous
Every linked list is built from a simple Node object. It has two fields: the data and a reference to the next node.
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } }
class Node: def __init__(self, data): self.data = data self.next = None
A reference (or pointer) is just a memory address. When we write node.next = new Node(10), the next field stores the heap address where that new Node object was allocated.
In Java/Python, references are managed by the runtime. In C/C++, you'd see the raw pointer value (like 0x2F0). The concept is the same: one object "points to" another's location in memory.
Node current = head; while (current != null) { System.out.println(current.data); current = current.next; }
current = head while current is not None: print(current.data) current = current.next
Node newNode = new Node(42); newNode.next = head; head = newNode;
new_node = Node(42) new_node.next = head head = new_node
Node newNode = new Node(99); if (head == null) { head = newNode; } else { Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; }
new_node = Node(99) if head is None: head = new_node else: current = head while current.next is not None: current = current.next current.next = new_node
if (head != null && head.data == target) { head = head.next; } else { Node current = head; while (current.next != null) { if (current.next.data == target) { current.next = current.next.next; break; } current = current.next; } }
if head and head.data == target: head = head.next else: current = head while current.next: if current.next.data == target: current.next = current.next.next break current = current.next
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at front | O(n) | O(1) |
| Insert at end | O(1)* | O(n) or O(1) with tail ptr |
| Search | O(n) | O(n) |
| Delete (known position) | O(n) | O(1) |
| Memory layout | Contiguous | Scattered (heap) |
| Memory overhead | None (data only) | Extra pointer per node |
| Cache performance | Excellent | Poor |
Arrays — when you need fast random access, know the size upfront, or iterate frequently.
Linked Lists — when you insert/delete at the front often, don't know the size, or need constant-time insertions at known positions.
The classic linked list problem. Reassign pointers to reverse the chain. Uses everything we just covered.
Open on LeetCode →