Skip list

Skip list insertion and deletion has to keep track of the references for all levels of the node to be inserted or deleted. So the first thing we do for insertion or deletions is that for each of the levels from top to bottom, all nodes with references that should now be changed are found. This could be on the stack via recursion or on heap. Then they are updated to the target node and with the current pointing to the earlier as in the case for insertion or they are updated to what the target node points to and the target node spliced as in the case for deletion. In all cases, the level zero iteration of nodes should span the entire list.

Insertion should perform the updates to the references as it walks down the levels. Deletion could perform the updates as it returns up the levels.