Skip lists are typically implemented with a short array of pointers at each node. When traversing a skip list in a loop the previous node is in a local variable

Skip lists are typically implemented with a short array of pointers at each node. When traversing a skip list in a loop the previous node is in a local variable. If you do it recursively the previous node is on the stack. "Retracing" is simply a matter of retrieving the previous node and adding 1 to the pointer array index.