A fast, performant implementation of skip list in Rust.

Overview

Subway

skiplist image

A fast, performant implementation of skip list in Rust.
A skip list is probabilistic data structure that provides O(log N) search and insertion complexity.
For more information about how to skiplist work refer here.

Build License: MIT

Usage

The SkipList supports the following operations.

insert

Insert an element into the list while maintaining sorted order.
The insert method accepts a key and a value.
The values in the list will be stored sorted by key.

let list = SkipList::new();
list.insert(1, 1);
list.insert(2, 2);

get

Returns an optional value if the supplied key is found in the list.
Time complexity of this operation is around O(logN).

let maybe_value = list.get(&key);
if maybe_value.is_some() {
    let value = maybe_value.unwrap();
} 

delete

Deletes an item from the linked list if present using the supplied key.

list.delete(&key_to_delete);

collect

Collects the list of items in the skip list sorted by key into a list.

list.insert(2, 2);
list.insert(1, 1);
list.insert(5, 5);
let values = list.collect(); // (1, 1), (2, 2), (5, 5)
You might also like...
A Rust ASN.1 (DER) serializer.

rust-asn1 This is a Rust library for parsing and generating ASN.1 data (DER only). Installation Add asn1 to the [dependencies] section of your Cargo.t

Encoding and decoding support for BSON in Rust

bson-rs Encoding and decoding support for BSON in Rust Index Overview of BSON Format Usage BSON Values BSON Documents Modeling BSON with strongly type

Rust library for reading/writing numbers in big-endian and little-endian.

byteorder This crate provides convenience methods for encoding and decoding numbers in either big-endian or little-endian order. Dual-licensed under M

Cap'n Proto for Rust

Cap'n Proto for Rust documentation blog Introduction Cap'n Proto is a type system for distributed systems. With Cap'n Proto, you describe your data an

Character encoding support for Rust

Encoding 0.3.0-dev Character encoding support for Rust. (also known as rust-encoding) It is based on WHATWG Encoding Standard, and also provides an ad

A CSV parser for Rust, with Serde support.

csv A fast and flexible CSV reader and writer for Rust, with support for Serde. Dual-licensed under MIT or the UNLICENSE. Documentation https://docs.r

A HTTP Archive format (HAR) serialization & deserialization library, written in Rust.

har-rs HTTP Archive format (HAR) serialization & deserialization library, written in Rust. Install Add the following to your Cargo.toml file: [depende

A HTML entity encoding library for Rust

A HTML entity encoding library for Rust Example usage All example assume a extern crate htmlescape; and use htmlescape::{relevant functions here}; is

pem-rs pem PEM jcreekmore/pem-rs [pem] — A Rust based way to parse and encode PEM-encoded data

pem A Rust library for parsing and encoding PEM-encoded data. Documentation Module documentation with examples Usage Add this to your Cargo.toml: [dep

Comments
  • Skip List insertion is slow

    Skip List insertion is slow

    Description

    The current insert implementation inserts into each level of the skip list. Using the bisect method it is possible to obtain insertion points across all levels in logarithmic time and insert new nodes after each of those points if required.

    bug 
    opened by sushrut141 1
  • Implement bisect method for SkipList

    Implement bisect method for SkipList

    The bisect should return the rightmost position where an element can be inserted to keep the list sorted. The bisect method should return the key present at this rightmost position.

    enhancement 
    opened by sushrut141 0
Releases(v0.1.1)
  • v0.1.1(Mar 13, 2021)

    The bisect method allows for efficiently finding the insertion point in the list. Specifically, bisect returns the largest key after which the the supplied key can be inserted in the list.

    Source code(tar.gz)
    Source code(zip)
  • v0.1.0(Feb 4, 2021)

Owner
Sushrut
Sushrut
Fast and compact sets of bytes or ASCII characters

bset Fast and compact sets of bytes and ASCII characters, useful for searching, parsing and determining membership of a given byte in the given set. T

null 26 Jul 19, 2022
A series of compact encoding schemes for building small and fast parsers and serializers

A series of compact encoding schemes for building small and fast parsers and serializers

Manfred Kröhnert 2 Feb 5, 2022
MessagePack implementation for Rust / msgpack.org[Rust]

RMP - Rust MessagePack RMP is a pure Rust MessagePack implementation. This repository consists of three separate crates: the RMP core and two implemen

Evgeny Safronov 840 Dec 30, 2022
Implementation of Bencode encoding written in rust

Rust Bencode Implementation of Bencode encoding written in rust. Project Status Not in active developement due to lack of time and other priorities. I

Arjan Topolovec 32 Aug 6, 2022
A Gecko-oriented implementation of the Encoding Standard in Rust

encoding_rs encoding_rs an implementation of the (non-JavaScript parts of) the Encoding Standard written in Rust and used in Gecko (starting with Fire

Henri Sivonen 284 Dec 13, 2022
Rust implementation of CRC(16, 32, 64) with support of various standards

crc Rust implementation of CRC(16, 32, 64). MSRV is 1.46. Usage Add crc to Cargo.toml [dependencies] crc = "2.0" Compute CRC use crc::{Crc, Algorithm,

Rui Hu 120 Dec 23, 2022
PROST! a Protocol Buffers implementation for the Rust Language

PROST! prost is a Protocol Buffers implementation for the Rust Language. prost generates simple, idiomatic Rust code from proto2 and proto3 files. Com

Dan Burkert 17 Jan 8, 2023
Rust implementation of Google protocol buffers

rust-protobuf Protobuf implementation in Rust. Written in pure rust Generate rust code Has runtime library for generated code (Coded{Input|Output}Stre

Stepan Koltsov 2.3k Dec 31, 2022
A binary encoder / decoder implementation in Rust.

Bincode A compact encoder / decoder pair that uses a binary zero-fluff encoding scheme. The size of the encoded object will be the same or smaller tha

Bincode 1.9k Dec 29, 2022
rust-jsonnet - The Google Jsonnet( operation data template language) for rust

rust-jsonnet ==== Crate rust-jsonnet - The Google Jsonnet( operation data template language) for rust Google jsonnet documet: (http://google.github.io

Qihoo 360 24 Dec 1, 2022