Skip List

How searching works in skip list

  • lets say we are trying to find a node with value V
  • we try to find a node whose next value is greater than V
  • the search starts in the top left(express lane), starting from first element.
  • If we find the element we are done.
  • If we find an element which is less than V and whose next element is greater than V, we drop down to the below level, and continue doing the same
  • Time complexity of different operations in skip list(similar to balanced trees)

  • Search => Average => O(log n), Worst => O(n)
  • Insert => Average => O(log n), Worst => O(n)
  • Search => Average => O(log n), Worst => O(n)
  • Search => Average => O(log n), Worst => O(n)
  • Bloom Filter