A high-performance Go library implementing a skip list with O(log n) operations and benchmark-proven speed.
skiplist is a Go library that implements a high-performance skip list data structure. It provides an efficient alternative to balanced trees and linked lists with predictable O(log n) time complexity for insertion, deletion, and search operations. The library is optimized for real-world applications and currently holds the title of fastest skip list implementation in Go according to benchmarks.
Go developers who need efficient ordered data structures for applications requiring fast insertions, deletions, and searches with predictable performance characteristics.
Developers choose this library because it offers benchmark-proven performance as the fastest skip list implementation in Go, with minimal overhead and convenient additional functions like FindGreaterOrEqual and node iteration capabilities.
A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.
According to the README's benchmarks, this is the fastest skip list implementation in Go, outperforming others by up to 800ns per insertion and 300ns per deletion in tests with up to 3 million elements.
Core functions like Insert and Delete show approximate logarithmic complexity in random operations, with near-constant time for operations at list ends, as demonstrated in the provided performance graphs.
Includes extra functions like FindGreaterOrEqual, GetSmallestNode, and ChangeValue, which simplify common tasks such as range queries and in-place updates, enhancing practical usability beyond basic operations.
The library is tailored for maximum performance with minimal extra code, as stated in the philosophy, ensuring efficient execution across all operations without unnecessary bloat.
The O(log n) complexity is approximate and probabilistic, meaning worst-case scenarios can deviate from expected performance, unlike deterministic structures like balanced trees that guarantee strict bounds.
The implementation lacks thread-safe operations, requiring developers to manage synchronization manually with mutexes or other patterns in concurrent applications, adding complexity.
Skip lists inherently use multiple levels of pointers per element, which can increase memory usage compared to simpler data structures like linked lists or arrays, though not explicitly quantified in the README.