Data Structures19 sections · 729 units
Open in Course

Traversal Pattern

Walking the list

The basic traversal pattern uses a single pointer: ```pseudocode current = head while current != null: process(current.val) current = current.next


First, check `current != null` before accessing `current.val` or `current.next`. Accessing fields of `null` crashes your program. 

Second, save `current.next` before modifying the node if you plan to change pointers. Once you overwrite `current.next`, you lose access to the rest of the list. 

Time complexity is $O(n)$. Space complexity is $O(1)$ since you only use one pointer regardless of list size. Time: $O(n)$. Space: $O(1)$.