Linked list
- C course
- Intermediate
- Lesson 70/116
- 5 min
Learn to create a linked list with struct.
Linked list
A linked list is a data structure where each node points to the next. Unlike arrays, its size isn't fixed; it grows as you add nodes.
Each node has two parts: data (the value carried) and next (the address of the next node). In C you define it with a struct: typedef struct Node { int data; struct Node *next; } Node;. With typedef you can write the short Node instead of struct Node. At the end of the list the next field is NULL; this signals the list is over.
Creating a node
A new node is allocated from the heap with malloc. The call Node *n = malloc(sizeof(Node)); reserves memory the size of one Node and gives its address to n.
The node's fields are filled like n->data = 42; and n->next = NULL;. The -> operator accesses a field of the struct a pointer addresses. When the node is alone in the list, next is still NULL. When done, release the memory with free(n); or a leak occurs. malloc and free require the <stdlib.h> header.
Practice Single-node list
Write typedef struct Node { int data; struct Node *next; } Node;. In main allocate one node with Node *n = malloc(sizeof(Node));. Set n->data = 42; and n->next = NULL;. Print with printf("%d\n", n->data);. Finally call free(n);.
Starter code
#include <stdio.h>
#include <stdlib.h>
// Define the Node struct: int data, struct Node *next
// main: create one node, set data = 42, print, free it
int main(void) {
// write here
return 0;
}Sample solution
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
int main(void) {
Node *n = malloc(sizeof(Node));
n->data = 42;
n->next = NULL;
printf("%d\n", n->data);
free(n);
return 0;
}Expected output
42
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Which field in a Node struct holds the next node?
- data
- prev
- next Correct answer
- size
Explanation: The next field carries the address of the following Node.
2 Allocate memory for a Node
Node *n = malloc(sizeof(____));Node *n = malloc(sizeof(Node));Explanation: sizeof(Node) gives the byte size of one Node.
3 Node parts
| Term | Meaning |
|---|---|
data |
carried value |
next |
next node address |
malloc |
allocate memory |
free |
release memory |