Singly linked list

Prerequisites

• Structs in C: grouping a value and a pointer.
• Pointers and NULL.
• Arrays, to compare against.

The analogy

How it works

Start with a sequence of operations by hand

The list is head → 5 → 3 → NULL. Do each operation and guess which pointers change before opening "Check".

Finish the picture: the back of the list

Now add 9 at the back of 7 → 3, first with only a head pointer, then with a tail pointer too.

• Only head. Predict: how many nodes do you walk?
  Check

  All of them: 7, then 3, to find the node whose next is NULL. Then 3 points to 9. $O(n)$.

• With a tail pointer. Predict the cost.
  Check

  One step: tail->next = 9, then tail = 9. $O(1)$.

The rule in plain words

Every node stores a value and a next pointer; the last node points to NULL. The list is reached through head.

To insert, create a node and rewire one pointer. To remove, make the previous node skip it. To find anything, start at head and follow next.

The code

Read this code after you have done the operations by hand. It will make more sense.

typedef struct Node { int val; struct Node *next; } Node;

Node *push_front(Node *head, int v) {       /* returns the new head */
    Node *n = malloc(sizeof(Node));
    n->val = v;
    n->next = head;
    return n;
}

Node *remove_value(Node *head, int v) {     /* returns the new head */
    if (head == NULL) return NULL;
    if (head->val == v) { Node *rest = head->next; free(head); return rest; }
    Node *p = head;
    while (p->next && p->next->val != v) p = p->next;   /* stop before v */
    if (p->next) { Node *gone = p->next; p->next = gone->next; free(gone); }
    return head;
}

flowchart LR
  H["head"] --> A["7 | next"]
  A --> B["5 | next"]
  B --> C["3 | next"]
  C --> N["NULL"]
          

How fast is it?

Reaching position $k$ (counting from 0) means following $k$ pointers. On average, over all positions:

Changing links next to a node you already hold is constant work: one or two pointer writes.

Common mistakes

• Losing the rest of the list by overwriting head before saving head->next.
• Dereferencing p->next->val without first checking that p->next is not NULL.
• Forgetting to free removed nodes, which leaks memory.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Inserting at the front is $O(1)$ because only the new node and the head pointer change.
• Access by position is $O(n)$ because nodes are scattered in memory and can only be reached by following next.
• Deleting needs the previous node because its next pointer is what must skip the removed node.
• A tail pointer makes push_back $O(1)$ because it saves the walk to the last node.
• The head is a special case because no node points to it; removing it changes head itself.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a singly linked list like a treasure hunt?
   Sample answer

   Each clue says where the next one is, so you must follow them in order from the start. Each node points to the next node the same way.

2. Walk through push_front(7) and then remove(5) on 5 → 3.
   Sample answer

   push_front makes 7 point to 5 and become the head: 7 → 5 → 3. remove(5) finds 7, the node before 5, and points it to 3: 7 → 3.

3. Why does remove_value return a pointer instead of void?

   A good answer mentions the first node.

   Sample answer

   If the value is in the first node, the head itself changes. Returning the new head lets the caller update its head variable.

4. So what is a singly linked list, in one sentence?
   Sample answer

   A chain of nodes, each holding a value and a pointer to the next, reached from a head pointer.

5. Why is reading the $k$-th element $O(k)$ and not $O(1)$ as in an array?

   A good answer mentions memory layout.

   Sample answer

   Nodes are not stored next to each other, so there's no address formula; the only way to reach node $k$ is to follow $k$ pointers.

6. What do push_front, push_back, search and delete-after-a-known-node cost?
   Sample answer

   push_front $O(1)$, push_back $O(n)$ or $O(1)$ with a tail pointer, search $O(n)$, delete after a known node $O(1)$.

7. When would you choose a linked list over an array?
   Sample answer

   When you insert and delete a lot at the front or next to nodes you already hold, and rarely need access by index.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out malloc/free details and the tail-pointer variant. I'd keep the treasure-hunt analogy, the push_front and remove pictures, and "$O(1)$ to relink, $O(n)$ to find".

External resources

• VisuAlgo: Linked list: animate insert, remove and search on your own list.
• GeeksforGeeks: Singly linked list: operations with code in C.
• Wikipedia: Linked list: history, variants and trade-offs against arrays.

Videos

• YouTube search: singly linked list explained: pick a walkthrough with box-and-arrow drawings.