Several flavours of BSD provide header-only libraries for linked lists and search trees as part of their libc in sys/queue.h and sys/tree.h, which are remarkabl

Several flavours of BSD provide header-only libraries for linked lists and search trees as part of their libc in sys/queue.h and sys/tree.h, which are remarkably nice and easy to use. newlib libc provides these, and macOS used to provide them in /usr/include (now they're only in the kernel headers - but they're header-only and self-contained so they're easy to add to any project). sys/queue.h provides four different linked list implementations: standard singly-linked lists, standard doubly-linked lists, a singly-linked list with a tail pointer (for fast tail insertion) and a doubly-linked list without a head pointer. All come complete with sys/tree.h provides two types of balanced search trees: splay trees and red-black trees. Both provide ordered dictionaries Both libraries make quite extensive use of macros, but they are quite reasonably implemented and documented via man-page. I've successfully used them a few times. Shame that, like other nice BSD innovations (e.g. strlcpy/strlcat) they haven't made it into other libcs.