This is a partial skip list implementation. See https://en.wikipedia.org/wiki/Skip_list It is different from the classic implementation in that that the layers are doubly linked lists, and a scan operation can traverse left and right progressing downwards through the layers, thus, resembling a snake motion. Based on the assumption that operations with pointers are atomic, there is no contention between insert() and scan() operations - only insertions are globally contentious. It is application's responsibility to ensure that local operations on a member node are either atomic or protected, should the application require thread safety. Expected performance is O(nlogn) for space, O(logn) for scan (with no worse case guarantee which is hardly relevant in practice), and O(1) for next/previous/max/min. Limitation (partial implementation) is that no delete()/destroy() methods are available. This is on an assumption that the list can only grow or be static, always required by the application, and never shrinks. Such grave decision was made because freeing memory blocks would necessitate mutex on any read operation. To use the structure you need #include "snakelist.h" in your global header, and this global header - in snakelist.c. This chaining is due to DECLARE_SNAKELIST_N macro which you have to use in the global header to specify members of each node of type snakelist_n. Memory allocation and definition for every snakelist_n object is your responsibility. You will also need to define a standard function for node comparison. The rest is easy. You create an object of type snakelist_i that controls the instance of the structure: snakelist_i *mylist = snakelist_create() returns NULL on failure. Here, memory allocation is done for you. snakelist_scan(mylist, node, int (*compar())) returns pointer to the node in the list or NULL if "not found". snakelist_insert(mylist, node, int (*compar())) returns NULL on success (-ful insertion) or a pointer to the node if it is already in the list. Note, if you call scan(), check its NULL, then call insert(), you are subject to race condition. Finally, included test.h and test.c demonstrate how to use the code. The latter does a quick benchmarking against simple linked list scan. Enjoy! NB Do not forget to change snakelist.h's variable SNAKELIST_LAYERS_NUMBER to indicate the maximal number of nodes you wish to cater for. This number is 2 powered to (number of layers + 1). Thus, second layer will be started when you add >= 4 nodes, etc.