# 4.2 Singly Linked List

> Nodes on the heap, each pointing to the next. Insert at front, end or a position, delete by value, search and traverse, plus the dummy-node trick and the classic pitfalls.

Chapter: Linked Lists · ~75 min · medium
URL: https://dsa.fetehadin.com/learn/singly-linked-list

## Mental model

A **treasure hunt**: each clue tells you where the next clue is hidden. You can't jump to clue #7. You must follow clues 1 → 2 → … → 7. But adding a new clue in the middle is easy: change one clue to point to the new one, and the new one to point onward.

That is a **singly linked list**: nodes scattered around the heap, each holding **data** and a **pointer to the next node**. The program only keeps **`head`**, the address of the first node. The last node's `next` is `nullptr`.

```cpp
struct Node {
    int data;
    Node* next;
};
```

### The golden rule of rewiring

When inserting, **connect the new node first, then redirect the old pointer**. If you move `head` (or `temp->next`) first, you lose the rest of the list.

### Deleting needs the node before

To remove node X you change the arrow that points **to** X, and that arrow belongs to the **previous** node. So deletion walks with a `prev` pointer. Deleting the head is a special case: there is no previous node.

### The dummy (sentinel) node

Put a fake node **before** the head: `Node dummy{0, head};`. Now every real node, including the first, has a previous node, so one loop handles all cases. At the end, `head = dummy.next`.

### Pitfalls checklist

- Check `nullptr` before every `->`.
- Handle the **empty list**, **one node**, **head** and **tail** cases.
- `delete` every node you unlink.
- Never move `head` to traverse. Use a `temp` copy.

## C++ code: singly-linked-list.cpp

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

struct Node {
    int data;
    Node* next;
};

void insertFront(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    n->next = head;          // 1. new node points at the old head
    head = n;                // 2. head points at the new node
}

void insertEnd(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    if (head == nullptr) { head = n; return; }
    Node* temp = head;
    while (temp->next != nullptr)
        temp = temp->next;
    temp->next = n;
}

void insertAt(Node*& head, int pos, int x) {      // pos is 0-based
    if (pos == 0) { insertFront(head, x); return; }
    Node* temp = head;
    for (int i = 0; i < pos - 1 && temp != nullptr; i++)
        temp = temp->next;
    if (temp == nullptr) return;                  // position too big
    Node* n = new Node{x, temp->next};
    temp->next = n;
}

void deleteValue(Node*& head, int x) {
    if (head == nullptr) return;
    if (head->data == x) {                        // deleting the head
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* prev = head;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next == nullptr) return;            // not found
    Node* temp = prev->next;
    prev->next = temp->next;
    delete temp;
}

void deleteDummy(Node*& head, int x) {            // same job, no special case
    Node dummy{0, head};
    Node* prev = &dummy;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next != nullptr) {
        Node* temp = prev->next;
        prev->next = temp->next;
        delete temp;
    }
    head = dummy.next;
}

bool search(Node* head, int x) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == x) return true;
        temp = temp->next;
    }
    return false;
}

void print(Node* head) {
    for (Node* t = head; t != nullptr; t = t->next) cout << t->data << " -> ";
    cout << "null\n";
}

void freeList(Node*& head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Node* head = nullptr;
    insertEnd(head, 12);
    insertEnd(head, 7);
    insertEnd(head, 31);
    insertFront(head, 9);
    print(head);
    insertAt(head, 2, 15);
    print(head);
    deleteValue(head, 9);      // head
    deleteValue(head, 31);     // tail
    print(head);
    deleteDummy(head, 12);     // new head, handled by the dummy
    print(head);
    cout << "search 15: " << search(head, 15) << ", search 99: " << search(head, 99) << "\n";
    freeList(head);
    print(head);
}
```

Expected output:

```text
9 -> 12 -> 7 -> 31 -> null
9 -> 12 -> 15 -> 7 -> 31 -> null
12 -> 15 -> 7 -> null
15 -> 7 -> null
search 15: 1, search 99: 0
null
```

## Complexity

| Case | Cost |
| --- | --- |
| Insert at front | O(1) |
| Insert at end | O(n), or O(1) with a tail pointer |
| Insert at position k | O(k) |
| Delete by value / search | O(n) |
| Access the i-th item | O(n): no random access |

Space: O(n) plus one pointer per node

Compared with an array, a linked list wins at **inserting and deleting** (no shifting) and loses at **indexing** (must walk) and cache-friendliness.

## Videos

- [Introduction to linked list](https://youtu.be/NobHlGUjV3g) (mycodeschool): Why linked lists exist and how they compare with arrays.
- [Linked List: Implementation in C/C++](https://youtu.be/vcQIFT79_50) (mycodeschool): Writes the C/C++ node struct and insertion functions line by line.
- [Data Structures: Full Course Using C and C++](https://youtu.be/B31LgI4Y4DQ) (freeCodeCamp.org): The full freeCodeCamp version of mycodeschool's course; includes insert at nth position and delete.

## Exam lens

Likely questions:

- Write a function to insert a node at the beginning, at the end and at a given position of a singly linked list.
- Write a function that deletes the first node with a given value.
- Compare arrays and linked lists (memory, access, insertion, deletion).
- What is a dummy (sentinel) node and why does it simplify deletion?
- What happens if you write `head = n; n->next = head;` (wrong order)?

Common mistakes:

- Losing the list by updating `head` before linking the new node (`head = n;` first).
- Dereferencing `temp->next` without checking `temp != nullptr`.
- Forgetting the empty-list and delete-the-head special cases.
- Not calling `delete` on removed nodes (memory leak).
- Passing `Node* head` by value to a function that changes head. Use `Node*& head`.

## Quick check

1. Correct order to insert node n at the front?
   A. `head = n; n->next = head;`
   B. `n->next = head; head = n;`
   C. `n->next = nullptr; head = n;`
   D. `head->next = n;`
   Answer: B. Link to the old head first, then move head. The other order makes n point to itself and loses the list.

2. To delete a node in a singly linked list you need a pointer to…
   A. the node itself only
   B. the node BEFORE it
   C. the tail
   D. the head only
   Answer: B. The previous node's `next` is the arrow you must change.

3. What does this print? List: 3 → 8 → 5

```cpp
int c = 0;
for (Node* t = head; t; t = t->next) c += t->data;
cout << c;
```
   A. 3
   B. 16
   C. 5
   D. crash
   Answer: B. A traversal summing 3 + 8 + 5.

4. Why use a dummy node?
   A. It saves memory
   B. Every real node then has a previous node, so deleting the head needs no special case
   C. It makes search O(1)
   D. It sorts the list
   Answer: B. The dummy sits before head, and at the end `head = dummy.next`.

5. Why must `insertFront` take `Node*& head`?
   A. For speed
   B. So the change to head is visible to the caller
   C. References are required for pointers
   D. It doesn't need to
   Answer: B. A plain `Node*` parameter is a copy; assigning to it would not update the caller's head.

## Practice

**Trace by hand.** Start empty. Do insertEnd 4, insertFront 7, insertAt(1, 2), insertEnd 9, delete 7, delete 9. Write the list after each step.

Solution:

- insertEnd 4 → `4`
- insertFront 7 → `7 → 4`
- insertAt(1, 2) → `7 → 2 → 4`
- insertEnd 9 → `7 → 2 → 4 → 9`
- delete 7 (head case) → `2 → 4 → 9`
- delete 9 → `2 → 4`


**Implement it.** Write `reverse(Node*& head)` (iterative, O(1) extra space), `length(Node* head)` and `deleteAt(Node*& head, int pos)`.

Hint: Reverse: keep `prev = nullptr`, `cur = head`. Each step: save `next = cur->next`, set `cur->next = prev`, move `prev = cur`, `cur = next`. Finally `head = prev`.

```cpp
void reverse(Node*& head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
}
```


**Problems:**

- [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) (easy). Hint: Three pointers, prev / cur / next. Draw it.
- [Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) (easy). Hint: While `cur->next` has the same value as `cur`, unlink it.
- [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) (easy). Hint: A dummy node plus a tail pointer. Always attach the smaller head.
- [Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/) (medium). Hint: Walk to the node before position `left`, then reverse the sublist with the same three-pointer trick. A dummy node saves you when left = 1.

## Mastery checklist

- [ ] I can insert at the front, the end and a position without losing the list.
- [ ] I can delete by value, including the head and not-found cases.
- [ ] I can use a dummy node to remove special cases.
- [ ] I can reverse a linked list iteratively.
- [ ] I free every removed node with delete.