Linked List Traversal is the fundamental operation on linked lists. Starting from the head node, it follows each next pointer until reaching a null pointer, visiting and processing each node along the way. All other linked list operations build on this basic traversal pattern.
struct Node { int val; Node* next; };
void traverse(Node* head) {
Node* curr = head;
while (curr != nullptr) {
cout << curr->val << " ";
curr = curr->next;
}
}A singly linked list node has two fields: a value and a next pointer. The last node has next=null. The list is accessed only through the head pointer.
Start with curr=head. On each iteration process curr.val, then advance curr=curr.next. Stop when curr is null. This is the foundation for all linked list operations.
Unlike arrays, linked lists do not support O(1) random access. Reaching the kth element requires traversing k nodes, taking O(k) time. This is the key trade-off versus arrays.
Quiz coming soon for this algorithm.