implement a skiplist in swift

A skip list is a data structure that allows for search and insertion in O(log n) time complexity, similar to a balanced binary search tree, but with simpler implementation. It consists of a hierarchy of linked lists with increasingly fewer elements, with each node in a higher-level list skipping over sections of lower-level lists. Here's an implementation of a skip list in Swift:


main.swift
class SkipList<T: Comparable> {
  
  private class Node {
    let value: T
    var next: [Node?]
    
    init(value: T, level: Int) {
      self.value = value
      self.next = Array(repeating: nil, count: level)
    }
  }
  
  private let maxLevel: Int
  private let p = 0.5 // probability of increasing level
  private var head: Node
  private var level: Int
  
  init(maxLevel: Int) {
    self.maxLevel = maxLevel
    self.head = Node(value: nil as! T, level: maxLevel)
    self.level = 0
  }
  
  func insert(value: T) {
    let newNode = Node(value: value, level: randomLevel())
    var current = head
    var update = Array(repeating: head, count: maxLevel)
    
    // find the insertion point and update references
    for i in stride(from: level, to: -1, by: -1) {
      while let next = current.next[i], next.value < value {
        current = next
      }
      update[i] = current
    }
    current = current.next[0] ?? head
    if current?.value == value { return } // already in the list
    if newNode.level > level {
      for i in level+1...newNode.level {
        update[i] = head
      }
      level = newNode.level
    }
    for i in 0...newNode.level {
      newNode.next[i] = update[i]?.next[i]
      update[i]?.next[i] = newNode
    }
  }
  
  func contains(value: T) -> Bool {
    var current = head
    // traverse the skip list from highest level to lowest
    for i in stride(from: level, to: -1, by: -1) {
      while let next = current.next[i], next.value <= value {
        if next.value == value { return true }
        current = next
      }
    }
    return false
  }
  
  private func randomLevel() -> Int {
    var lvl = 0
    while Double.random(in: 0..<1) < p && lvl < maxLevel {
      lvl += 1
    }
    return lvl
  }
  
}
1762 chars
71 lines

In this implementation, Node represents a single element in the skip list with a value and an array of next pointers to elements at the same level and in lower levels. SkipList maintains a few parameters:

maxLevel: the maximum level of the skip list
p: the probability of increasing a node level
head: the node at the top level with no value
level: the current highest level in the skip list

The insert method creates a new node with a randomized level, traverses the skip list to find the correct insertion point and update references to point to the new node at all levels up to its level. The contains method traverses the skip list from the highest level to the lowest, searching for nodes with the target value. The randomLevel method uses a bounded random number generator to simulate a coin flip with probability p of returning heads, until a maximum level is reached.

Note that this implementation assumes all inserted values are unique. To support duplicates, the contains method could return a count of nodes with the target value instead of a binary result, and the insert method could find the insertion point for the new node by comparing its value to the value of the last node at each level instead of skipping over higer-value nodes.

similar swift code snippets

hello world in swift

loop in swift

protocol in swift

sort a list of people by name in swift

make a table view in swift

how do you determine if a string is a palindrome in swift

make http get request in swift

create an enum in swift

create a generic function in swift

open a new view in swift

related categories