C Linked Lists
A linked list is a data structure made of nodes, where each node holds a value and a pointer to the next node. Unlike arrays, linked lists can grow or shrink dynamically without needing contiguous memory.
Linked lists are commonly built using structs and dynamic memory allocation, and are a foundational data structure for understanding pointers in practice.
struct Node {
int data;
struct Node *next;
};Defining a node
A node is typically a struct containing a data field and a pointer to the next node of the same type, often written self-referentially like `struct Node *next;`.
Traversing a list
To visit every node, start at the head pointer and follow each node's `next` pointer until you reach NULL, which marks the end of the list.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
int main() {
struct Node *head = malloc(sizeof(struct Node));
head->data = 10;
head->next = NULL;
printf("%d\n", head->data);
free(head);
return 0;
}10A single node is created, its data set, and next set to NULL since it's the last node.
#include <stdio.h>
struct Node { int data; struct Node *next; };
void printList(struct Node *head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node c = {3, NULL};
struct Node b = {2, &c};
struct Node a = {1, &b};
printList(&a);
return 0;
}1 2 3 The list is traversed node by node, following next pointers until NULL.
Key points
- A linked list node holds data plus a pointer to the next node.
- Linked lists grow and shrink dynamically without needing contiguous memory.
- Traversal follows next pointers until reaching NULL.
- Linked lists trade random access speed for flexible insertion/removal.