The Skip List acts as a layered Linked List with a sorted sequence of keys and express lanes that increase in speed as you go up the layers. These express lanes are used to speed up the lookup operation. The runtime complexity is generally O(log(N)). The lookup function works by starting at the head of the list at the fastest express lane. Then it peeks ahead to the next element on that express lane. If that element is larger than the key that one is looking up then the pointer moves down to a slower lane and repeats the peak process. If the element that one peeked to is smaller than the lookup, the pointer will step ahead, then move down to a slower lane and peek again. This process is repeated until the node is either found or not found.
The Insertion Function is done by creating an approximate express lane structure. Changing the base list when inserting an element would normally invalidate the express lane structure and repairing the problems that would arise would be too costly for the program. So, the Skip List uses a coin-flip method proportional to the ideal structure of the Skip List. A node to be inserted has a 50% chance to be on the next fastest highway using the analogy of flipping a coin to heads. For every level upwards on the highway, the coin is flipped giving probabilities that are proportional to the ideal logarithmic structure of the Skip List. Even though this method is not perfect, overtime the probabilities will always even out to a model that is very similar to the ideal version. By doing the insertion in Skip List under an approximated formula, runtime is decreased greatly.
The deletion function a similar method for lookup to find the node to be deleted and even though at the worst case the runtime can be O(n), this runtime would be improbably rare. Due to the randomness of both the insertion and deletion function, the runtime is on average O(log(N)). After the node to be deleted is found in a Skip List. All references attatched to that node on all highways must be refigured to keep the connectivity of the Skip List.