This is cll, a simple circular linked list implementation designed for O(1) insertion and removal, O(n) traversal, and close to O(1) search using a backing hashtable.
Currently it supports:
- initialising a circular linked list from a standard list with
- traversing through the list using
- adding and removing elements at the current head using
- finding and navigating to elements in the list either by iterating through all elements or looking up elements with the backing hashtable
seekto iterate through and perform an O(n) lookup
findto perform an O(1) lookup
- iterate through the full list from the current head and apply a given function to each element with
- output the current circular list as a standard Ocaml list using
I started developing
cll after writing circular linked list implementations for a couple of programming puzzles, and decided that writing and publishing a library was a good way for me to continue learning Ocaml.
I have included examples in the Github repo for both of these puzzles: Advent of code 2020 day 23 (crab cups), and the Josephus problem Codewars kata.