# 4.1 Pointers, new/delete & the Heap

> A pointer holds an address. new asks the heap for memory that lives until you delete it. Master this and linked lists become easy.

Chapter: Linked Lists · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/pointers-and-memory

## Mental model

A variable is a **house**; its value is the **person living there**; its address is the **street address**. A **pointer** is a slip of paper with an address written on it. It doesn't hold the person, it tells you where to find them.

```cpp
int x = 5;      // a house with 5 in it
int* p = &x;    // & = "address of": p holds x's address
*p = 10;        // * = "go to that address": changes x to 10
```

### Stack vs heap

- **Stack**: local variables. Created when a function starts, destroyed automatically when it returns. Fast, but small, and its size is fixed at compile time.
- **Heap**: memory you request at run time with **`new`**. It stays alive until **you** call **`delete`**. This is how we make data structures that grow while the program runs.

```cpp
Node* n = new Node{7, nullptr};   // lives on the heap
delete n;                          // give it back
n = nullptr;                       // don't keep a stale address
```

### Three classic bugs

1. **Null dereference**: `*p` when `p == nullptr`. Crash.
2. **Dangling pointer**: using `p` after `delete p`. Random behaviour.
3. **Memory leak**: losing the last pointer to heap memory, so it can never be freed.

> Rule of thumb: every `new` has exactly one matching `delete`. After deleting, set the pointer to `nullptr`.

## C++ code: pointers.cpp

```cpp
#include <iostream>
using namespace std;

int main() {
    int x = 5;
    int* p = &x;                 // p holds the address of x
    *p = 10;                     // write through the pointer
    cout << "x = " << x << ", *p = " << *p << "\n";
    cout << "p points to x? " << (p == &x ? "yes" : "no") << "\n";

    int* q = new int(42);        // one int on the heap
    cout << "*q = " << *q << "\n";
    delete q;                    // give it back
    q = nullptr;                 // never leave a dangling pointer
    if (q == nullptr) cout << "q is safely null\n";

    int n = 4;
    int* arr = new int[n];       // array on the heap: size chosen at run time
    for (int i = 0; i < n; i++) arr[i] = (i + 1) * 10;
    cout << "arr: ";
    for (int i = 0; i < n; i++) cout << *(arr + i) << " ";   // pointer arithmetic
    cout << "\n";
    delete[] arr;                // new[] needs delete[]
    arr = nullptr;
}
```

Expected output:

```text
x = 10, *p = 10
p points to x? yes
*q = 42
q is safely null
arr: 10 20 30 40
```

## Complexity

| Case | Cost |
| --- | --- |
| `&x`, `*p`, `p->field` | O(1) |
| `new` / `delete` one object | O(1) (amortised; done by the allocator) |
| Stack memory | automatic: freed when the function returns |
| Heap memory | manual: lives until `delete` |


Linked lists, trees and graphs are built from heap nodes connected by pointers. Every bug in Chapters 4–7 is a pointer bug in disguise.

## Videos

- [Introduction to pointers in C/C++](https://youtu.be/h-HBipu_1P0) (mycodeschool): The clearest 10-minute introduction to `&`, `*` and what a pointer really stores.
- [Pointers and dynamic memory: stack vs heap](https://youtu.be/_8-ht2AKyH4) (mycodeschool): Explains stack vs heap with diagrams. This is exactly what the visualizer above animates.

## Exam lens

Likely questions:

- What is a pointer? Explain `&` and `*` with an example.
- Differentiate between stack and heap memory.
- What is a memory leak? Write code that causes one and fix it.
- What is a dangling pointer and how do you avoid it?

Common mistakes:

- Dereferencing `nullptr` or an uninitialised pointer, which crashes (segmentation fault).
- Using memory after `delete` (dangling pointer). Set the pointer to `nullptr` right after.
- `new[]` paired with `delete` instead of `delete[]`.
- Overwriting the only pointer to heap memory before deleting it, which leaks it forever.

## Quick check

1. What does this print?

```cpp
int x = 3;
int* p = &x;
*p = *p + 4;
cout << x;
```
   A. 3
   B. 4
   C. 7
   D. an address
   Answer: C. `*p` IS x, so x becomes 3 + 4.

2. Memory from `new` is freed…
   A. when the function returns
   B. when you call delete
   C. never
   D. when the pointer goes out of scope
   Answer: B. Heap memory is manual. If the pointer disappears first, you have a leak.

3. Which line causes a leak?

```cpp
int* p = new int(5);   // A
p = new int(6);       // B
delete p;             // C
```
   A. A
   B. B
   C. C
   D. none
   Answer: B. The address of the 5 is lost at line B, so it can never be deleted.

4. For a pointer `Node* n`, `n->data` is the same as…
   A. `*n.data`
   B. `(*n).data`
   C. `&n.data`
   D. `n.data`
   Answer: B. Arrow = dereference, then access the member.

## Practice

**Trace by hand.** Draw the stack and heap after each line and say what is printed:
```cpp
int a = 2;
int* p = &a;
int* q = new int(a * 5);
*p = *q + 1;
cout << a << " " << *q;
delete q;
```


Solution:

- stack: a = 2, p → a; heap: (none)
- `q = new int(10)`: heap gets 10, q → it
- `*p = *q + 1` sets a = 11
- prints **11 10**
- `delete q` frees the heap int (q is now dangling, so set it to `nullptr`)


**Implement it.** Write `int* makeArray(int n)` that returns a heap array filled with 1..n, use it in `main`, print the sum, and free it correctly.

Hint: `int* a = new int[n];` … `delete[] a;`. Check with `g++ -fsanitize=address` that there is no leak.

**Problems:**

- [Design Linked List](https://leetcode.com/problems/design-linked-list/) (medium). Hint: The best pointer workout. Start with addAtHead and get; draw boxes and arrows on paper for every line.
- [Pointers in C (HackerRank)](https://www.hackerrank.com/challenges/c-tutorial-pointer/problem) (easy). Hint: Modify two values through pointers. Warm-up for `*` and `&`.

## Mastery checklist

- [ ] I can explain `&`, `*` and `->` with a drawing.
- [ ] I can explain the difference between stack and heap memory.
- [ ] I can pair every `new` with exactly one `delete` (and `new[]` with `delete[]`).
- [ ] I can spot leaks and dangling pointers in code.