Linked lists

C programming · Structures and dynamic memory

Louis Ledoux

ISTIC · University of Rennes

2026–2027

Kahoot corrections

Dynamic memory allocation · q1–q10

Kahoot (alloc) q1: pointer errors

/* X */ m = malloc(5); m = NULL;
/* Y */ free(n); n->value = 5;
/* Z */ char *p; *p = 'a';
  1. Using dangling pointers
  2. Using uninitialised pointers
  3. Lost memory

Match X, Y and Z to the problems.

  1. X–1, Y–3, Z–2
  2. X–3, Y–2, Z–1
  3. X–2, Y–1, Z–3
  4. X–3, Y–1, Z–2
  • X leaks if allocation succeeds; its address is lost.
  • Y uses a freed object; Z has no initialised address.

Kahoot (alloc) q2: free(NULL)

#include <stdio.h>
int main() {
  int *p = (int *)malloc(sizeof(int));
  p = NULL;
  free(p);
}
  • free(NULL) does nothing (CM, slide 291).
  • D assumes allocation succeeds. No alias is saved here.
  • Missing <stdlib.h> is a separate C17 error.

What is the problem with this code?

  1. Compiler error: free() can’t be applied on NULL pointer
  2. Dangling pointer
  3. The program may crash as free() is called for NULL pointer.
  4. Memory leak

Kahoot (alloc) q2: another reference

int *p = malloc(sizeof(int));
if (p == NULL) return EXIT_FAILURE;
int *q = p;
p = NULL;
free(p);
free(q);
  • q kept the allocated address before p changed.
  • free(q) releases the block. No leak here.

Kahoot (alloc) q3: return value of free()

#include <stdio.h>
#include <stdlib.h>
int main() {
  int *ptr1, *ptr2;
  ptr1 = malloc(4);
  *ptr1 = 10;
  *ptr2 = free(ptr1);
  printf("%d\n", *ptr2);
  return 0;
}

What is the output?

  1. 10
  2. The address stored in ptr1
  3. The address stored in ptr2
  4. Error
  • free() returns void: no value to assign.
  • ptr2 is also uninitialised.

Kahoot (alloc) q4: a local address

#include <stdio.h>
int *fun() {
  int x = 5;
  return &x;
}
int main() {
  int *p = fun();
  printf("%d", *p);
  return 0;
}

What is the problem with this code?

  1. Memory leak
  2. Dangling pointer
  3. There is no problem
  4. Compilation error
  • x stops existing when fun() returns.
  • Dereferencing p has undefined behaviour.

Kahoot (alloc) q5: one block

#include <stdio.h>
#include <stdlib.h>
int main() {
  int r = 3, c = 4;
  int *arr = (int *)malloc(
      r * c * sizeof(int));
  int i, j, count = 0;
  for (i = 0; i < r; i++)
    for (j = 0; j < c; j++)
      ??? = ++count;
  /* ... */
  return 0;
}

Which expression replaces ????

  1. *(arr + i*c + j)
  2. arr[i][j]
  3. arr + i*c + j
  4. *(&arr[i]+&arr[j])
  • Skip i rows of c integers, then j integers.
  • Also written arr[i*c + j].

Kahoot (alloc) q6: separate rows

#include <stdio.h>
#include <stdlib.h>
int main() {
  int r = 3, c = 4, i, j, count;
  int *arr[r];
  for (i = 0; i < r; i++)
    arr[i] = (int *)malloc(
        c * sizeof(int));
  count = 0;
  for (i = 0; i < r; i++)
    for (j = 0; j < c; j++)
      ???? = ++count;
  /* ... */
  return 0;
}

Which expression replaces ?????

  1. *(arr+i*c+j)
  2. *(*(arr + i*c) + j)
  3. *(*(arr + i*c + j))
  4. *(*(arr+i)+j)
  • *(arr+i) selects row i; +j selects column j.
  • Also written arr[i][j] or (*(arr+i))[j].

Kahoot (alloc) q7: freeing the grid

#include <stdio.h>
#include <stdlib.h>
int main() {
  int r = 3, c = 4, i, j, count;
  int **arr = (int **)malloc(
      r * sizeof(int *));
  for (i = 0; i < r; i++)
    arr[i] = (int *)malloc(
        c * sizeof(int));
  count = 0;
  for (i = 0; i < r; i++)
    for (j = 0; j < c; j++)
      arr[i][j] = ++count;
  for (i = 0; i < r; i++)
    for (j = 0; j < c; j++)
      printf("%d ", arr[i][j]);
  free(arr);
  return 0;
}

Is this code correct?

  1. Yes
  2. No
  3. I do not know
  • free(arr) releases only the pointer table.
  • On success, the three rows leak. Free them first:
for (i = 0; i < r; i++)
  free(arr[i]);
free(arr);

Kahoot (alloc) q8: initialisation

struct Point {
  int x = 0;
  int y = 0;
};

What is the output? (C17)

  1. x=0, y=0
  2. Compilation error
  3. Nothing of the mentioned
  • A C structure definition cannot initialise its members.
  • Initialise an object after defining its type.

Kahoot (alloc) q9: structure copy

#include <stdio.h>
struct student { char *name; };
struct student s;
struct student fun(void) {
  s.name = "newton";
  printf("%s\n", s.name);
  s.name = "alan";
  return s;
}
void main() {
  struct student m = fun();
  printf("%s\n", m.name);
  m.name = "turing";
  printf("%s\n", s.name);
}

What is the output?

  1. newton · alan · alan
  2. alan · newton · alan
  3. newton · alan · turing
  4. Compilation error
  • Assigning m.name does not change s.name.
  • A assumes void main() is accepted; strict compilation can reject it. Use int main(void).

Kahoot (alloc) q9: the caller

struct student m = fun();
printf("%s\n", m.name);
m.name = "turing";
printf("%s\n", s.name);
Pointer value After fun() After assignment
m.name points to "alan" "turing"
s.name points to "alan" "alan"
  • Returning s copies its pointer member into m.
  • The last printf() reads s.name, still alan.

Kahoot (alloc) q10: member access

#include <stdio.h>
struct point { int x; int y; };
void foo(struct point *);
int main() {
  struct point p1 = {1, 2};
  foo(&p1);
}
void foo(struct point *p) {
  printf("%d\n", *p.x++);
}

What is the output?

  1. Compile time error
  2. Segmentation fault
  3. 2
  4. 1
  • *p.x++: . binds before *.
  • p is a pointer. p->x++ or (*p).x++ prints 1, then sets x to 2.

Struct reminder

Each list node will hold a song ID and a pointer.

A structure groups them together.

Struct: type and object

struct Point {
    int x;
    int y;
};
struct Point origin = {0, 0};
origin.x = 3;
  • struct Point describes the type; origin is an object.
  • origin.x accesses that object’s x member.

Typedef: a type alias

typedef struct Point point_t;

struct Point a = {1, 2};
point_t b = {1, 2};
  • struct Point and point_t name the same type.
  • typedef creates no object and allocates no heap memory.

1. A playlist that changes

A listener requests a song next.

Can we insert it without shifting the rest of the playlist?

Play E immediately after B

  • B is playing. A listener requests E next.

A B C D are linked. B is playing. E is separate with no successor.

  • We want A → B → E → C → D. Keep C and D in the playlist.

With an array, make room for E

  • The array has a spare slot. Where do C and D go?

An array changes from A B C D spare to A B E C D by shifting C and D.

  • C and D move one slot. A longer suffix means more moves.

A node stores a song and a link

  • A node stores a song ID and the address of the next node.

Each box has song ID at left and next pointer at right. head reaches A; each next reaches the following node; D next is NULL.

  • The dot is a pointer value; the arrow leads to its node. NULL ends the list.

First, let E remember C

  • Before changing B, keep its current successor.

A B C D remain linked. Separate E now points to C.

  • E → C. Following the playlist from head still gives A B C D.

Then, make B lead to E

  • Change the next-song link stored in B.

B now points to E. E points to C. The original nodes stay in place.

  • Follow the arrows: A → B → E → C → D. Two links changed.

Cancel the request

  • E has not played yet. Make B lead to C again.

B points directly to C again. E is outside the playlist but still exists.

  • E is unlinked. Its storage still needs to be released.

When links help

  • We already know the current song: B.
  • Adding or removing its successor changes a few links.
  • The other nodes stay in place.
  • Finding song number 500 requires following the chain.
  • Arrays give direct indexing and store elements together.

The same edit with numbers

Insert 101 into [100, 103, 105, 200]. What must change?

  • Array with capacity: move 103, 105 and 200 one slot.
  • List: find 100, then link 100 → 101 → 103.
  • The list needs an extra pointer per node and sequential search.

2. Linked-list basics

Turn the drawn playlist into a working C program: A → B → NULL.

  • Allocate two nodes.
  • Link them using next.
  • Walk the list without changing head.

Can we use the alias here?

typedef struct list_elem {
    int value;
    list_elem_t *next;
} list_elem_t;
  • At next, does the compiler already know list_elem_t?
  • GCC: unknown type name ‘list_elem_t’.
  • This typedef declares the alias after the closing brace.

A tag inside, an alias afterwards

typedef struct list_elem {
    int value;
    struct list_elem *next;
} list_elem_t;
  • struct list_elem is already known inside the braces.
  • next stores a pointer. The node’s full size is not needed yet.
  • After this declaration, list_elem_t names the same type.

Now we can use the alias:

list_elem_t *head = NULL;

What is in one node?

  • A song ID and the address of the next node.

A node has a stored value and a next pointer.

  • The next node is a separate object, possibly far away in memory.
  • next stores its address; the nodes need not be adjacent.

Start with an empty playlist

list_elem_t *head = NULL;
  • head is a local pointer in main().
  • Its value is NULL: there is no first node yet.
  • No malloc() call, so no heap node.

head is a local pointer on the stack, containing NULL. No node is allocated on the heap.

Allocate the first song

  • Here, create A on the heap.
  • A local node on the stack would work here too.
  • In a real program: control its lifetime across functions, and possibly store larger objects.
  • What must head contain to reach it?

head is a local pointer on the stack, containing NULL. No node is allocated on the heap.

list_elem_t *node =
    malloc(sizeof(list_elem_t));
if (node == NULL)
    return EXIT_FAILURE;
  • node receives the address of the heap block.
  • head is still NULL. ? means uninitialised.

node on the stack holds 0x1000, pointing to an uninitialised heap block. head remains NULL. Allocation succeeds.

node->value = 'A';
  • Write into the heap object.
  • next is still uninitialised.

Only value has been initialised to A in the heap node.

node->next = NULL;
  • A has no successor yet.
  • head still does not reach A.

The allocated node contains A and NULL, but head is still NULL.

head = node;
  • Copy the address into head.
  • Two pointer variables, one allocated node.

Stack pointers head and node both hold 0x1000 and refer to one heap node A.

Add a second song

  • Next, add B after A.
  • Which member must change to link A to B?

Stack pointers head and node both hold 0x1000 and refer to one heap node A.

node =
    malloc(sizeof(list_elem_t));
  • Continue after checking node != NULL.
  • node moves to the new allocation. head still reaches A.

The new B block at 0x3000 is uninitialised. node points there, while head still points to A at 0x1000.

node->value = 'B';
  • Initialise the new heap object.
  • A is unchanged.

The new block value is B, its next is still uninitialised.

node->next = NULL;
  • B has no successor.
  • A and B are still unlinked.

A and B both have NULL next members. There is not yet a link from A to B.

head->next = node;
  • Write B’s address into A’s next member.
  • head itself does not change.

head stays at 0x1000. node holds 0x3000. The next member in heap node A now holds 0x3000, linking A to B.

Read the playlist

list_elem_t *p = head;
while (p != NULL) {
    printf("%c -> ", p->value);
    p = p->next;
}
puts("NULL");
  • Finally, read the nodes by following next.
  • What does this print? Does it change head?

head stays at 0x1000. node holds 0x3000. The next member in heap node A now holds 0x3000, linking A to B.

list_elem_t *p = head;
  • Copy the first node’s address into p.
  • p->value is A.

p and head both hold 0x1000. node still holds 0x3000. The stored address identifies the current heap node.

printf("%c -> ", p->value);
p = p->next;
  • Print A, then copy A’s next address into p.
  • p reaches B. head still reaches A.

p now holds 0x3000 and reaches B. head still holds 0x1000.

printf("%c -> ", p->value);
p = p->next;
  • Print B, then p becomes NULL.
  • The loop stops. Output: A → B → NULL.

p is NULL, so traversal ends. head still reaches A and both heap nodes are unchanged.

3. Create nodes in a function

Creating each song repeats the same allocation code.

Let create_element() do that work for us.

Create a node in a function

What survives when this function returns?

list_elem_t *create_element(int value) {
    list_elem_t *node = malloc(sizeof(list_elem_t));
    if (node == NULL) return NULL;
    node->value = value;
    node->next = NULL;
    return node;
}

In main(): list_elem_t *node = create_element('A');

Call create_element('A')

/* main pauses here */
list_elem_t *node = create_element('A');

main waits for the call to initialise its node variable. create_element has parameter value equal to A; no heap node exists yet.

  • main() waits. The called function gets its own stack frame.

malloc() reserves the node

list_elem_t *node = malloc(sizeof(list_elem_t));
if (node == NULL) return NULL;

The callee node stores 0x1000 and points to uninitialised value and next fields. main is still waiting.

  • Here malloc() returns 0x1000. ? means uninitialised.

Initialise value and next

node->value = value;
node->next = NULL;

The callee pointer still contains 0x1000. The heap fields now contain A and NULL. Caller head remains NULL.

  • -> follows node to write the heap structure.

Return the address to main()

/* inside create_element */
return node;

The dashed return arrow copies 0x1000 from the callee node to the separate node in main. Both refer to one heap object.

  • The return value copies 0x1000 into main()’s node.

The call ends; the node remains

/* back in main: the call has completed */
list_elem_t *node = create_element('A');

The callee frame is gone. main’s node still holds 0x1000 and reaches the structure. head remains NULL.

  • The local pointer is gone; the heap node stays allocated.

Make the node the first one

/* in main */
head = node;

main’s head and node both hold 0x1000 and reach the same heap object. No callee frame remains.

  • Two pointers hold the same address. There is still one node.

4. Change the caller’s head

We want insert_head(...) to put a new song first.

How can it update head in main()?

Can the function change head?

Will the caller’s head change?

int insert_head(list_elem_t *l, int value) {
    list_elem_t *node = create_element(value);
    if (node == NULL) return -1;
    node->next = l;
    l = node;
    return 0;
}

Call: insert_head(head, 'A').

The argument is copied into l

insert_head(head, 'A');
/* parameter: list_elem_t *l */

head and parameter l are separate pointers, both NULL. No heap node has been allocated yet.

  • l gets NULL, the value of head. The variables are separate.

The function creates a node

list_elem_t *node = create_element(value);
node->next = l;

The helper node reaches the new heap object. Local l and caller head both remain NULL.

  • node->next gets NULL. head is still NULL.

l = node changes only l

l = node;

l now holds 0x1000. Both local l and node reach the allocation. head stays NULL.

  • l changes. head is a separate variable and stays NULL.

Return loses the node’s address

/* inside insert_head */
return 0;

Local l and node are gone. head remains NULL. The allocation survives with no remaining pointer to it.

  • The local pointers are gone; the node is unreachable.

Pass the address of head

insert_head(&head, 'A');
/* parameter: list_elem_t **l */

l stores 0x7000, the illustrative address of main’s head variable. head still contains NULL. No heap node exists yet.

  • Here &head is 0x7000. *l refers to head itself.

Read the old head through *l

list_elem_t *node = create_element(value);
node->next = *l;

l reaches head; the new node is at 0x1000. Reading *l copies head’s NULL value into next.

  • Read *l: NULL, the current value stored in head.

Write head through *l

*l = node;

Writing through l changes head from NULL to 0x1000. l remains 0x7000. head and local node reach the same heap object.

  • head becomes 0x1000. l still contains &head.

Back in main(): head is updated

/* insert_head has returned */
printf("head -> %c -> NULL\n", head->value);

The helper frame is gone. head holds 0x1000 and reaches the allocated node. main can print it, then free it.

  • C still passes by value. The copied value was &head.

5. Insert without losing links

A new song must fit before, between, or after the existing songs.

Which links need to change?

Insert at the head · starting state

A to B to C to D. A newly allocated node E is ready to link.

  • A → B → C → D. A newly allocated node E is ready to link.

Insert at the head · which link matters?

head is our entry point to the existing chain.

  • head is our entry point to the existing chain.

If we change head first

What remains reachable after head = node?

A B C D remain linked from head. E is separate; its next is NULL.

The old entry point has been lost.

head = node;
  • Only E remains reachable; A–D leak.

Back to the initial list

Reset to the initial state. Preserve the old address before changing head.

  • Reset to the initial state. Preserve the old address before changing head.

Move head to E

E already points to A. What must change now?

E already points to A, but head still points to A.

E is now the first node.

head = node;
  • E → A → B → C → D.

Insert in the middle · starting state

Insert E between B and C. previous points to B.

  • Insert E between B and C. previous points to B.

Insert in the middle · the link to preserve

B’s next link is currently our route to C and the rest of the chain.

  • B’s next link is currently our route to C and the rest of the chain.

If B points to E first

What remains reachable after changing B’s link first?

previous points to B; B still points to C. E is separate.

The previous link to C has been overwritten.

previous->next = node;
  • The list stops at E; C and D leak.

Back to the initial list

Reset to A to B to C to D with E still separate.

  • Reset to A → B → C → D with E still separate.

Link B to E

E already points to C. Which link finishes the insertion?

E already points to C; B still points directly to C.

The list is now A to B to E to C to D.

previous->next = node;
  • The list is now A → B → E → C → D.

Insert at the tail · starting state

Append E after D. tail points to D.

  • Append E after D. tail points to D.

Insert at the tail · link D to E

  • Which link attaches E to the chain?

tail points to D. D ends the chain with NULL; E is separate.

Connect the old tail to the new node.

tail->next = node;
  • Connect the old tail to the new node.

Insert at the tail · terminate the chain

What makes E the last node?

D points to E. E already contains NULL from its creation.

The list is now A to B to C to D to E to NULL.

node->next = NULL;
  • The list is now A → B → C → D → E → NULL.

6. Unlink, then free

A song is removed from the playlist.

Reconnect the remaining songs and release its memory.

Delete the head · save the victim

  • Which address must we keep before changing head?

head points to A in A B C D. No victim pointer has been saved yet.

Keep the address of A so it can be freed after unlinking.

list_elem_t *victim = head;
  • Keep the address of A so it can be freed after unlinking.

Delete the head · unlink, then release

Where should head point before we release A?

head and victim both point to A. A still points to B and is not freed.

B is now the first node. Do not access A after free.

head = victim->next;
free(victim);
  • B is now the first node. Do not access A after free().

Delete in the middle · save B

previous points to A. Save the node to be removed.

list_elem_t *victim = previous->next;
  • previous points to A. Save the node to be removed.

Delete in the middle · reconnect A to C

  • How do we bypass B before releasing it?

previous points to A; victim points to B. A still points to B, then C.

Preserve the successor before freeing the removed node.

previous->next = victim->next;
free(victim);
  • Preserve the successor before freeing the removed node.

Delete the tail · find its predecessor

previous points to C; save its successor D.

list_elem_t *victim = previous->next;
  • previous points to C; save its successor D.

Delete the tail · make C the last node

What must C’s next link become?

previous points to C; victim points to D. C still points to D.

Set C’s next link to NULL, then free D.

previous->next = NULL;
free(victim);
  • Set C’s next link to NULL, then free D.

7. Doubly linked lists

  • To delete D, we first had to find C.
  • D’s next link cannot take us back to C.
  • What if each node remembered its predecessor?

A link in each direction

What extra address should each node store?

A B C have next links only. A node has no direct link to its predecessor.

Each node stores prev and next; the outer links are NULL.

  • Add prev: reach the predecessor directly to unlink a known node.
  • Also traverse in both directions: our player can offer a Previous button.
  • One extra pointer per node; maintain both links.

Time and storage costs

\(n\) nodes; current node known, predecessor not saved.

Operation Singly linked Doubly linked
Find its predecessor \(O(n)\) \(O(1)\)
Unlink this node \(O(n)\) \(O(1)\)
Find node number \(k\) \(O(n)\) worst case \(O(n)\) worst case
Total node storage \(\Theta(n)\) \(\Theta(n)\)
  • Singly linked: start at head, follow next to the predecessor.
  • Doubly linked: read prev directly; one extra pointer per node.

8. Questions

Choose A, B, C or D, then explain why.

Linked lists · q1: changing the head

void prepend(list_elem_t *head,
             list_elem_t *node) {
    node->next = head;
    head = node;
}

head points to A; node points to a separate node E.

After prepend(head, node), what happens to the caller’s head?

  1. It points to E.
  2. It still points to A.
  3. It becomes NULL.
  4. It points to a copy of A.
  • The function changes its local pointer copy.
  • E points to A, but the caller’s head is unchanged.

Linked lists · q2: insertion order

Insert E between B and C. Which order works?

A B C D remain linked; previous points to B. node points to separate E, whose next is NULL.

/* X */ previous->next = node;
/* Y */ node->next = previous->next;
  1. X, then Y
  2. Y, then X
  3. Only X
  4. Only Y
  • E remembers C before B points to E.

Linked lists · q3: releasing a node

victim points to the first node of a nonempty list.

free(victim);
head = victim->next;

What is the problem?

  1. The whole list is freed.
  2. head must become NULL.
  3. We read a freed node.
  4. There is no problem.
  • Read victim->next before free().
  • The invalid read has undefined behaviour; a crash is not guaranteed.

Linked lists · q4: time and storage

A doubly linked list has \(n\) nodes; the current node is known.

Reading prev: what time cost and total node storage?

  1. \(O(1)\) time; \(\Theta(n)\) storage
  2. \(O(n)\) time; \(\Theta(n)\) storage
  3. \(O(1)\) time; \(\Theta(1)\) storage
  4. \(O(n)\) time; \(\Theta(n^2)\) storage
  • Direct access to the predecessor; no traversal.
  • One extra pointer per node; total storage stays linear.
Université de Rennes Louis Ledoux