Unit 1 · Lesson 220 minAcademic review pending

A list that grows one node at a time

A singly linked list replaces an array's fixed block of memory with a chain of separately allocated nodes, each pointing to the next.

Choose explanation

After this lesson

You should be able to

Define a node structure with a data field and a next pointer.
Insert a node at the front and traverse the full list.
Explain why a linked list has no random access.

Try it before you read

Try it live

list.c0 node(s)

head → NULL

Insert at front rewires one pointer — no shifting, unlike an array.

Trading contiguous memory for pointers

An array's elements sit side by side in one block, which is exactly what makes indexing instant but also what makes resizing expensive — growing it means allocating a whole new block and copying everything. A linked list gives up the side-by-side layout: each element is its own small allocation, called a node, holding a value and the address of the next node.

The last node's next holds NULL, marking the end. There is no fixed capacity to run out of — you can keep adding nodes as long as memory allows, which is the dynamic behaviour Lesson 1 promised.

A node: one value, one link to the next

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

typedef struct Node Node;

Node *head = NULL;   /* an empty list is just a NULL pointer */

Inserting at the front

Allocate a new node, point its next at the current head, then move head to the new node. Order matters: if you moved head first, you would lose your only reference to the rest of the list before the new node had a chance to point at it.

This is a constant-time operation regardless of how long the list already is — no shifting, unlike inserting at the front of an array. That is the first concrete payoff of giving up contiguous memory.

Link first, then hand back the new head

Node *insert_front(Node *head, int value)
{
    Node *node = malloc(sizeof(Node));
    node->data = value;
    node->next = head;    /* link before moving head */
    return node;           /* new head */
}

Traversal, and the access you gave up

To visit every node you walk the chain: start at head, print the data, move to next, repeat until you reach NULL. This is the do { } while pattern from your C course applied to pointers instead of numbers.

To reach the fifth element you must walk through the first four — there is no marks[4]-style jump. That is the real cost of the trade you made: O(1) insertion at the front, but O(n) to reach any given position.

Walk until next is NULL

void print_list(const Node *head)
{
    for (const Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d -> ", cur->data);
    printf("NULL\n");
}

Try it yourself

Build a singly linked list by reading integers from the user until -1, inserting each at the front, then print the list.

Need a hint?

-1 is a sentinel, exactly like the sentinel loop from your C course. Do not insert it as data.

Check the worked solution

Because every insertion happens at the front, the printed order is the reverse of the input order — the first number typed ends up last in the list. That is expected here and is exactly why the next lesson exists: a way to insert at the end without walking the whole list each time is not free with a plain singly linked list.

#include <stdio.h>
#include <stdlib.h>

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

Node *insert_front(Node *head, int value)
{
    Node *node = malloc(sizeof(Node));
    node->data = value;
    node->next = head;
    return node;
}

void print_list(const Node *head)
{
    for (const Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d -> ", cur->data);
    printf("NULL\n");
}

int main(void)
{
    Node *head = NULL;
    int   n;

    printf("Enter integers, -1 to stop: ");
    scanf("%d", &n);
    while (n != -1) {
        head = insert_front(head, n);
        scanf("%d", &n);
    }

    print_list(head);
    return 0;
}

Quick check

Why is inserting at the front of a singly linked list O(1), while inserting at the front of an array is O(n)?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Linear list – Introduction · singly linked list

Maps to course outcomes CO1, CO4.