Start at the highest level. Move right only while the next key is strictly smaller than x, then descend without returning to head.
def findPreds(x: Int): Array[Node] = {
  require(Int.MinValue < x && x < Int.MaxValue)
  val preds = new Array[Node](NumLevels)
  var n = head
  var level = NumLevels - 1
  while (level >= 0) {
    while (n.nexts(level).datum < x) {
      n = n.nexts(level)
    }
    preds(level) = n
    level -= 1
  }
  preds
}
At each inner loop head, n belongs to the current level and has key below x. Every node already passed has key below x. The representation invariant ensures that n also belongs to the next lower level. Stopping just before a key at least x therefore gives
(1)
The tail prevents a null dereference during the comparison. Strict comparison makes the predecessor lie before the first occurrence of x, including duplicates. On the source diagram, findPreds(14) yields data , in increasing level order.[ref]
With the customary random-level policy this has expected logarithmic time complexity for a suitably sized level cap; an unlucky skip list can require a linear scan. No deterministic logarithmic guarantee is claimed.

Ancestors (12)

  1. c
  2. 3
  3. Imperative programming
  4. 2014
  5. Past exam of the year 1 of the computer science course of the University of Oxford
  6. Year 1 of the computer science course of the University of Oxford
  7. Computer science course of the University of Oxford
  8. Undergraduate course of the University of Oxford
  9. Course of the University of Oxford
  10. University of Oxford
  11. List of universities
  12. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version