CentralNotice Skip list From Wikipedia, the free encyclopedia Jump to: navigation , search This article may be too technical for most readers to understand . Please help improve this article to make it understandable to non-experts , without removing the technical details. The talk page may contain suggestions. (October 2011) Skip List Type List Invented 1989 Invented by W. Pugh Time complexity in big O notation Average Worst case Space O(n) O(n log n) [ 1 ] Search O(log n) O(n) [ 1 ] Insert O(log n) O(n) Delete O(log n) O(n) Part of a series on Probabilistic data structures Bloom filter Quotient filter Skip list Random trees Random binary tree Treap Rapidly exploring random tree Related Randomized algorithm Computer science portal v t e In computer science , a skip list is a d...