We derive a method to construct and maintain a skip list such that the amortized cost of search, insert, and delete is O(logn).