skip_list.rb

    start.include? x
  end

  def each(&block)
    return to_enum(:each) unless block
    @lists[0].each(&block) if @lists[0]
  end

  def insert(x)
    if !@lists[0] || x < @lists[0].head
      prev = x
      @lists.map! do |rest|
        head = LinkedList.new(prev, rest)
        prev = Node.new(x, head)
        head
      end
    else
      nodes = []

      i = @lists.size - 1

      start = @lists[i]
      while i >= 1
        node = start.each_node.find { |n|
          n.tail.nil? or n.tail.head.value >= x
        }

        nodes << node
        start = node.head.below

        i -= 1
      end

      bottom = start.each_node.find { |n|
        n.tail.nil? or n.tail.head >= x
      }.insert(x)

      i = nodes.size - 1
      while rand(2).zero? && i >= 0
        bottom = nodes[i].insert Node.new(x, bottom)
        i -= 1
      end

      if i < 0
        while rand(2).zero?
          @lists << LinkedList.new(Node.new(@lists[0].head, @lists.last), nil)
          bottom = @lists.last.insert Node.new(x, bottom)
        end
      end
    end
  end
end