level as pand above position qreturning the position of the new entry (and setting internal references so that nextprevaboveand below methods will work correctly for pqand rthe expected running time of the insertion algorithm on skip list with entries is (logn)which we show in section code fragment insertion in skip list method coinflip(returns "headsor "tails"each with probability / variables nhand hold the number of entriesthe heightand the start node of the skip list figure insertion of an entry with key into the skip list of figure we assume that the random "coin flipsfor the new entry came up heads three times in rowfollowed by tails the positions visited are highlighted in blue the positions inserted to hold