C
Traversing list
Learn to traverse a linked list with a loop.
Traversing a list
Traversing a list means visiting each node in turn from head to end. A cursor variable starts at the head and advances one step at a time.
Example: Node *cur = head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; }. The cur != NULL condition stops the loop when we reach the end. The cur = cur->next step moves the cursor forward. This runs in O(n) time where n is the node count. Traversal doesn't modify nodes; it only reads them.
The list_print function
Traversal becomes a list_print function. It takes the head and prints each node's data field.
Definition: void list_print(Node *head) { Node *cur = head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }. A space follows each value; a newline ends the loop. This keeps the output tidy. The function returns void because it computes nothing; it only prints. If the list is empty (head == NULL) the loop doesn't run and only a newline is printed.
Exercise Print with list_print
Write void list_print(Node *head): start with Node *cur = head;, in a while (cur != NULL) loop do printf("%d ", cur->data); and cur = cur->next;, after the loop printf("\n");. In main prepend 30, 20, 10; call list_print(head);; then free every node.
Show example solution
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *list_push_front(Node *head, int value) {
Node *n = malloc(sizeof(Node));
n->data = value;
n->next = head;
return n;
}
void list_print(Node *head) {
Node *cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main(void) {
Node *head = NULL;
head = list_push_front(head, 30);
head = list_push_front(head, 20);
head = list_push_front(head, 10);
list_print(head);
while (head) { Node *t = head; head = head->next; free(t); }
return 0;
}
Test yourself
-
Traversal idioms
- cur = head
- init cursor
- cur != NULL
- loop condition
- cur->data
- read value
- cur = cur->next
- advance one
-
When does the while (cur != NULL) loop stop?
- when cur is NULL
- when cur is head
- when data is 0
- when next is not NULL
Show answer
when cur is NULL — When cur is NULL we've reached the end of the list.
-
Advance the cursor
cur = cur->____;
Show answer
cur = cur->next;
Next lesson: Deleting from list
