[ANN] cll 0.2.0 - mutable circular/cyclic doubly linked lists

Community
1

Hi all,

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 init
  • traversing through the list using next and prev functions
  • adding and removing elements at the current head using add and pop
  • finding and navigating to elements in the list either by iterating through all elements or looking up elements with the backing hashtable
    • seek to iterate through and perform an O(n) lookup
    • find to perform an O(1) lookup
  • iterate through the full list from the current head and apply a given function to each element with iter
  • output the current circular list as a standard Ocaml list using to_list

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.

2 Likes