Self-checkedTier 1 16 min readpds.linked-list-singly

Singly linked lists

A linked list is a chain of separately allocated nodes, each holding a value and the address of the next node. Learn the struct, traversal, insertion at the front, end and after a node, why a function that changes the head needs a pointer to the head pointer, and what each operation costs compared with an array.

Why it exists

An array has a fixed size and its items sit side by side, so inserting in the middle means moving everything after the gap. A linked list gives up the side-by-side layout. Each item lives in its own small block of memory, and the blocks are tied together by addresses: every block says where the next one is. Insertion and deletion then change a few pointers and move no data. The price is that you can no longer jump to the $k$ -th item; you must follow the chain.

Prerequisites

Pointers and pointer arithmetic Dynamic memory: malloc, free and leaks

Precise definitions

A struct in one minute

A structure groups several variables, called members, under one name. A linked-list node needs two: a value and the address of the next node.

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

struct node is now a type. A variable struct node n; has two members, n.data and n.next.
If p is a pointer to a node, the members are (*p).data and (*p).next. The shorthand p->data and p->next means exactly the same.
The structure contains a pointer to its own type. That is allowed (a struct cannot contain itself, which would be infinite, but it can point at another one).
sizeof(struct node) is not simply 4 + 8. The compiler inserts padding so that the pointer starts at a multiple of 8. On gcc x86-64: data is at offset 0, 4 bytes of padding, next at offset 8, total size 16. Always write malloc(sizeof *n), never a number.
More about structs (and unions) is on the structures page.

The list

Singly linked list. A chain of nodes in which each node's next points to the following node. The last node's next is NULL.
Head pointer. A variable struct node *head that holds the address of the first node. It is the only way into the list. If head == NULL, the list is empty.
Nodes live on the heap, each from its own malloc (see dynamic memory). Their addresses are unrelated to their order in the list. The order is the order of the next pointers.
Traversal idiom. Visit every node:

for (struct node *p = head; p != NULL; p = p->next)
    /* use p->data */

Cost of each operation

Operation	Singly linked list	Array
Access the $k$ -th item	$O(k)$ (follow $k$ pointers)	$O(1)$
Search for a value	$O(n)$	$O(n)$ (unsorted), $O(\log n)$ (sorted)
Insert at the front	$O(1)$	$O(n)$ (shift everything)
Insert at the end	$O(n)$ (walk to the last node), $O(1)$ with a tail pointer	$O(1)$ if there is room
Insert after a node you already hold	$O(1)$	$O(n)$
Delete the first node	$O(1)$	$O(n)$
Delete a node you already hold, if you also hold its predecessor	$O(1)$	$O(n)$
Delete the last node	$O(n)$ (need the second-to-last)	$O(1)$
Extra memory per item	a pointer (8 bytes), any padding, and the allocator's own bookkeeping	none
Size limit	none (until memory runs out)	fixed or must be resized

Arrays are better for random access and for cache-friendly scans. Lists are better for frequent insertion and deletion at known places.

How it works

Building a list

Step through this real run. The node blocks are on the heap; head, n and cur are ordinary variables on the stack. Watch three things:

A new node is created and filled in first (its next is set to the old head). It is not in the list until head = n.
The order of the two pointer assignments matters. Setting head first would lose the old list.
To append, cur walks along next until cur->next is NULL. The walk is the cost of insertion at the end.

Building a singly linked list

Real run, real addresses

C source

1#include <stdio.h>

2#include <stdlib.h>

4struct node {

5 int data;

6 struct node *next;

7};

9int main(void) {

10 struct node *head = NULL, *n = NULL;

11 n = malloc(sizeof *n);

12 n->data = 10;

13 n->next = head;

14 head = n;

15 n = malloc(sizeof *n);

16 n->data = 20;

17 n->next = head;

18 head = n;

19 n = malloc(sizeof *n);

20 n->data = 30;

21 n->next = head;

22 head = n;

23 struct node *cur = head;

24 while (cur->next != NULL) {

25 cur = cur->next;

26 }

27 n = malloc(sizeof *n);

28 n->data = 40;

29 n->next = NULL;

30 cur->next = n;

31 return 0;

32}

Stack

headpointer

NULL…d5f8

npointer

NULL…d5f0

Heap

nothing here yet

Amber = changed in this step. Hover a cell for its full address. Arrows show where a pointer points; the small tag under a cell names the pointers aimed at it.

Step 1

head holds the address of the first node. NULL means the list is empty.

1 / 11

Each node is a separate heap block holding data and a pointer to the next node. head is the only way in. Produced by: real execution: every address and value is read from memory by the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog (ASLR off so the numbers are stable)

Passing the head to a function

head is an ordinary pointer, and C passes arguments by value (see parameter passing). A function that receives struct node *head gets a copy of the address. It can change the nodes (through the copy) but changing head itself changes only the copy. So a function that may change which node is first has two choices:

take struct node **head (a pointer to the caller's head pointer) and write *head = n;, or
return the new head, and let the caller write head = insert(head, x);.

Example 5 runs both versions.

Worked examples

EX 1Padding in the node

Easy

#include <stdio.h>
#include <stddef.h>
 
struct node {
    int data;
    struct node *next;
};
 
int main(void) {
    printf("%zu %zu %zu\n", sizeof(struct node), offsetof(struct node, data),
           offsetof(struct node, next));
    return 0;
}

Output (gcc, x86-64):

16 0 8

Reading it. data is at offset 0 and takes 4 bytes. The pointer must be aligned to 8, so 4 bytes of padding follow, and next sits at offset 8. The whole node is 16 bytes, not 12. A GATE question that asks for the size of such a struct gives or assumes the sizes and alignment rules; with all members the same size (for example two ints) no padding appears.

EX 2Insert at the front, then traverse

Easy

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
int main(void) {
    struct node *head = NULL;
    for (int v = 10; v <= 30; v += 10) {
        struct node *n = malloc(sizeof *n);
        if (n == NULL) return 1;
        n->data = v;
        n->next = head;
        head = n;
    }
    int len = 0, sum = 0;
    for (struct node *p = head; p != NULL; p = p->next) {
        printf("%d ", p->data);
        len++;
        sum += p->data;
    }
    printf("\n%d %d\n", len, sum);
    while (head != NULL) {
        struct node *t = head;
        head = head->next;
        free(t);
    }
    return 0;
}

Output:

30 20 10
3 60

Reading it. Each new node is put in front of the old ones, so the list comes out in the reverse of the insertion order. Traversal follows next until NULL. The cleanup loop saves the node in t before moving head, then frees it: freeing head first and then reading head->next would read freed memory.

EX 3Search, and insert after a node

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *push(struct node *head, int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->data = x;
    n->next = head;
    return n;
}
 
static struct node *find(struct node *head, int key) {
    for (struct node *p = head; p != NULL; p = p->next)
        if (p->data == key) return p;
    return NULL;
}
 
static void insert_after(struct node *p, int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->data = x;
    n->next = p->next;
    p->next = n;
}
 
int main(void) {
    struct node *head = NULL;
    head = push(head, 10);
    head = push(head, 20);
    head = push(head, 30);
    struct node *p = find(head, 20);
    if (p != NULL) insert_after(p, 25);
    printf("%s\n", find(head, 99) == NULL ? "99 not found" : "99 found");
    for (p = head; p != NULL; p = p->next) printf("%d ", p->data);
    printf("\n");
    return 0;
}

Output:

99 not found
30 20 25 10

Reading it. insert_after does two assignments in a fixed order: first n->next = p->next (the new node takes over the rest of the list), then p->next = n (the list now enters the new node). Doing them the other way round would make p->next point at the new node first, and the new node's next would then copy itself: the rest of the list would be lost. Inserting after a node you already hold costs $O(1)$ ; finding that node cost $O(n)$ .

EX 4Insertion at the end: walking versus a tail pointer

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *mk(int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->data = x;
    n->next = NULL;
    return n;
}
 
int main(void) {
    struct node *h1 = NULL, *h2 = NULL, *tail = NULL;
    int hops1 = 0;
    for (int v = 1; v <= 4; v++) {
        struct node *n = mk(v);
        if (h1 == NULL) h1 = n;
        else {
            struct node *p = h1;
            while (p->next != NULL) {
                p = p->next;
                hops1++;
            }
            p->next = n;
        }
        n = mk(v);
        if (tail == NULL) h2 = n;
        else tail->next = n;
        tail = n;
    }
    printf("%d %d\n", hops1, h2->next->next->next->data);
    return 0;
}

Output:

3 4

Reading it. Without a tail pointer, the 1st append goes into an empty list (0 hops), the 2nd finds the single node already last (0 hops), the 3rd needs 1 hop and the 4th needs 2: $0 + 0 + 1 + 2 = 3$ . Appending $n$ items this way costs $0 + 1 + \cdots + (n-2) = \frac{(n-1)(n-2)}{2} = \Theta(n^2)$ hops in total. With a tail pointer every append takes the same few steps and needs no hops at all. The second number, 4, is the data of the fourth node of the second list, showing that both ways built the same list. (The tail version also needs care when the list is empty, shown by the tail == NULL test. The program does not free its lists, to keep the example short.)

EX 5Changing the head: by value versus pointer to pointer

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static void push_bad(struct node *head, int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->data = x;
    n->next = head;
    head = n;
}
 
static void push_good(struct node **head, int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->data = x;
    n->next = *head;
    *head = n;
}
 
static int length(const struct node *p) {
    int n = 0;
    for (; p != NULL; p = p->next) n++;
    return n;
}
 
int main(void) {
    struct node *head = NULL;
    push_bad(head, 1);
    int a = length(head);
    push_good(&head, 1);
    int b = length(head);
    printf("%d %d\n", a, b);
    return 0;
}

Output:

0 1

Reading it. In push_bad the parameter head is a copy of the caller's head. The assignment head = n changes only the copy, and the new node is lost (a leak). In push_good the parameter holds the address of the caller's head, so *head = n changes the caller's variable. This is the same lesson as swap(int, int) versus swap(int *, int *): to change a variable of type $T$ in the caller, pass a pointer to $T$ ; here $T$ is struct node *, so the parameter is struct node **.

EX 6What do these list functions compute?

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *last(struct node *h) {
    struct node *p = h;
    while (p && p->next) p = p->next;
    return p;
}
 
static int len(struct node *p) {
    return p == NULL ? 0 : 1 + len(p->next);
}
 
static int alt(struct node *p) {
    if (p == NULL) return 0;
    return p->data + (p->next ? alt(p->next->next) : 0);
}
 
int main(void) {
    struct node *head = NULL;
    for (int v = 5; v >= 1; v--) {
        struct node *n = malloc(sizeof *n);
        if (n == NULL) return 1;
        n->data = v;
        n->next = head;
        head = n;
    }
    printf("%d %d %d\n", last(head)->data, len(head), alt(head));
    return 0;
}

Output:

5 5 9

Reading it. The list is 1, 2, 3, 4, 5 (values 5 down to 1 inserted at the front). last walks while there is a next node and returns the final node (data 5). len is the recursive length: 1 plus the length of the rest (5). alt adds the first value, then skips one node and continues: $1 + 3 + 5 = 9$ . The test p->next ? ... : 0 stops it from reading p->next->next when p->next is NULL. For an exam, write the list as a row of boxes and mark where each pointer is on every call.

Cheat box

Node: struct node { int data; struct node *next; };. p->x is (*p).x. Allocate with malloc(sizeof *p).
head == NULL means empty. The last node's next is NULL.
Traverse: for (p = head; p != NULL; p = p->next).
Insert at the front: n->next = head; head = n; $O(1)$ . Insert after p: n->next = p->next; p->next = n; $O(1)$ . Insert at the end: $O(n)$ , or $O(1)$ with a tail pointer.
Delete the first node: head = head->next; (save it first, then free). Delete anywhere needs the predecessor.
Access the $k$ -th: $O(k)$ . Search: $O(n)$ .
To change head inside a function, pass struct node ** (or return the new head).
sizeof(struct node) includes padding (16 on gcc x86-64).
Each node costs a pointer plus padding and allocator overhead. Free every node.

Traps and GATE patterns

Connections

Builds on

Pointers and pointer arithmetic Dynamic memory: malloc, free and leaks

Unlocks

Doubly and circular linked listsPrerequisite ofplanned

Chaining and open addressinguses Dynamic memory: malloc, free and leaksuses Stack (abstract data type)uses Queue (abstract data type)uses Linked list operationsPrerequisite of Trees and binary treesPrerequisite of Graph representationsPrerequisite of Graph representationsimplemented by

Across subjects

No cross-subject links yet.

Within this subject

Linked list operationsuses Stack (abstract data type)uses Queue (abstract data type)uses Arrays and indexingcontrasts-with

Structures, unions and memory alignmentusesplanned

The nodes are heap blocks from dynamic memory, linked by pointers. More operations (deletion, reversal, finding the middle, cycle detection, merging) are on the list operations page. The list is the natural structure behind a growing stack and a queue. Compare the storage with an array: contiguous and indexed versus scattered and linked. Operating systems and file systems use the same idea of linking blocks.

PYQs

4 previous year questions from your book. I re-solved each one myself (0 by running or simulating, 4 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2023 · MCQ · 1 markQ3 · page 55 of the book

Let SLLdel be a function that deletes a node in a
singly-linked list given a pointer to the node and a
pointer to the head of the list. Similarly, let DLLdel
be another function that deletes a node in a doubly-
linked list given a pointer to the node and a pointer to
the head of the list.
Let n denote the number of nodes in each of the linked
lists. Which one of the following choices is TRUE
about the worst-case time complexity of SLLdel and
DLLdel?

(a)SLLdel is O(1) and DLLdel is O(n).
(b)Both SLLdel and DLLdel are O(log(n)).
(c)Both SLLdel and DLLdel are O(1).
(d)SLLdel is O(n) and DLLdel is O(1). DATA STRUCTURE

GATE 2022 · MCQ · 1 markQ4 · page 56 of the book

Consider the problem of reversing a singly linked
list. To take an example, given the linked list below,

the reversed linked list should look like,

Which one of the following statements is TRUE
about the time complexity of algorithms that solve
the above problem in O(1) space?

(a)The best algorithm for the problem takes θ(n) time in the worst case.
(b)The best algorithm for the problem takes θ(nlogn) time in the worst case.
(c)The best algorithm for the problem takes θ(n2) time in the worst case.
(d)It is not possible to reverse a singly linked list in O(1) space.

GATE 2018 · MCQQ7 · page 56 of the book

A queue is implemented using a non-circular singly
linked list. The queue has a head pointer and a tail
pointer, as shown in the figure. Let n denote the
number of nodes in the queue. Let 'enqueue' be
implemented by inserting a new node at the head, and
'dequeue' be implemented by deletion of a node from
the tail.

Which one of the following is the time complexity of
the most time-efficient implementation of 'enqueue'
and 'dequeue, respectively, for this data structure?

(a)θ(1), θ(1)
(b)θ(1), θ(n)
(c)θ(n), θ(1)
(d)θ(n), θ(n) } for (index = 0; index <= 3; index++) { printf("Value at index %d is %d\n", index, head- >value); head = head→next; printf("Value at index %d is %d\n", index+1, head→value); } } DATA STRUCTURE

GATE 2016 · Set 2 · MCQ · 1 markQ9 · page 57 of the book

N items are stored in a sorted doubly linked list.
For a delete operation, a pointer is provided to the
record to be deleted. For a decrease-key operation,
a pointer is provided to the record on which the
operation is to be performed.
An algorithm performs the following operations on
the list in this order:
Θ(N) delete, O(logN) insert, O(logN) find and
Θ(N)decrease-key . What is the time complexity of
all these operations put together?

(a)O(log2N)
(b)O(N)
(c)O(N2)
(d)O(N2logN)

Self-check

Question 1

Inserting a node n at the front of a list with head head takes two statements. Which are they, in which order, and what happens if they are swapped?

Show answer

n->next = head; then head = n;. Swapped, head = n; first makes the list start at n, whose next is still garbage or NULL, and then n->next = head; makes n point to itself. The old list is lost and n->next forms a cycle of one node.

Question 2

A list has $n$ nodes and a head pointer only. What is the cost of inserting at the front, inserting at the end, deleting the first node, and deleting the last node?

Show answer

Front insertion $O(1)$ , end insertion $O(n)$ , first deletion $O(1)$ , last deletion $O(n)$ (the second-to-last node must be found to set its next to NULL). A tail pointer makes the end insertion $O(1)$ but does not help the last deletion.

Question 3

struct s { char c; int i; char d; }; on a typical 64-bit gcc platform (int is 4 bytes and 4-aligned). What is sizeof(struct s)?

Show answer

c at offset 0 (1 byte), 3 bytes padding, i at offset 4 (4 bytes), d at offset 8 (1 byte), then 3 bytes of trailing padding so that the size is a multiple of the largest alignment (4): total 12. Reordering the members as int i; char c; char d; gives 8.

Question 4

Why does push_bad(head, x) (taking the head by value) leak memory in addition to not working?

Show answer

The new node is allocated and linked to the old head, but the only pointers to it are the locals n and the copy head, and both disappear when the function returns. Nothing can reach or free that node.

Question 5

In the animation, the walk to the end ends with cur on the node holding 10, which is head->next->next. Why can the loop not simply be replaced by that fixed chain of ->next?

Show answer

The number of nodes is not fixed in general, and a list has no index. Each hop must be made by following next, and the loop condition cur->next != NULL is how the program recognises the last node. A fixed chain such as head->next->next finds the last node only in a list of exactly 3 nodes. In a longer list it stops early, and in a shorter one it dereferences NULL.

Revision card

One-screen revision

Node = data + next. head is the entry; NULL ends the list and also means empty.
Insert at front $O(1)$ ; at end $O(n)$ (tail pointer: $O(1)$ ); after a held node $O(1)$ . Delete first $O(1)$ . Access $k$ -th $O(k)$ .
Insert order: set the new node's next first, then move the old pointer.
Changing head in a function: struct node **, or return the new head.
Never touch a node after free. Save next first.
sizeof(struct node) includes padding. Use sizeof *n.
Check 0, 1 and 2 nodes. Draw boxes and arrows.

References

·Kernighan and Ritchie, The C Programming Language, 2nd ed., Sections 6.1 Basics of Structures, 6.2 Structures and Functions, 6.4 Pointers to Structures, 6.5 Self-referential Structures
·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 10.2 Linked lists
·ISO/IEC 9899:2011 (C11), Sections 6.7.2.1 Structure and union specifiers, 6.5.2.3 Structure and union members, 7.19 Common definitions (offsetof)

Verification

The animation replays a real run of an instrumented C program: every address, data value and next pointer is read from the heap nodes at each step, the leak flags are computed by following pointers from the live variables, and the test suite checks the final order of the nodes, the 8-byte distance from data to next, and that no node is ever unreachable. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan (with leak detection off: several examples do not free their lists to stay short). The sizeof and offset values are for gcc on x86-64. The textbook section numbers were written from memory and have NOT been checked against the books. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Queue (abstract data type)

Linked list operations