A C header file only implementation of a typed linked list.
Go to file
Daniel Eklöf 9958204f19
ci/woodpecker/push/woodpecker Pipeline was successful Details
ci: 'pipeline' -> 'steps'
2023-08-18 16:48:32 +02:00
.gitignore PKGBUILD: initial 2019-12-01 12:31:34 +01:00
.woodpecker.yml ci: 'pipeline' -> 'steps' 2023-08-18 16:48:32 +02:00
LICENSE license: fix bad copy-paste: first commit was in 2019 2020-07-25 09:44:39 +02:00
PKGBUILD meson/pkgbuild: bump version to 1.1.0 2022-08-07 09:18:47 +02:00
README.md tll_sort: document in the cheat sheet 2022-08-04 13:51:47 +02:00
meson.build meson/pkgbuild: bump version to 1.1.0 2022-08-07 09:18:47 +02:00
test.c tll_sort: implement a sort macro 2022-08-02 17:28:27 +02:00
tllist.h tll_sort: tabs -> spaces 2022-08-07 09:21:53 +02:00


CI status


tllist is a Typed Linked List C header file only library implemented using pre-processor macros.

Packaging status

  1. Description
  2. Usage
    1. Declaring a variable
    2. Adding items - basic
    3. List length
    4. Accessing items
    5. Iterating
    6. Removing items - basic
    7. Adding items - advanced
    8. Removing items - advanced
    9. Freeing
  3. Integrating
    1. Installing
    2. Meson
  4. API
    1. Cheat sheet


Most C implementations of linked list are untyped. That is, their data carriers are typically void *. This is error prone since your compiler will not be able to help you correct your mistakes (oh, was it a pointer-to-a-pointer... I thought it was just a pointer...).

tllist addresses this by using pre-processor macros to implement dynamic types, where the data carrier is typed to whatever you want; both primitive data types are supported as well as aggregated ones such as structs, enums and unions.

Being a double-linked list, most operations are constant in time (including pushing and popping both to/from front and back).

The memory overhead is fairly small; each item carries, besides its data, a prev and next pointer (i.e. a constant 16 byte overhead per item on 64-bit architectures).

The list itself has two head and tail pointers, plus a length variable (typically 8 bytes on 64-bit architectures) to make list length lookup constant in time.

Thus, assuming 64-bit pointers (and a 64-bit size_t type), the total overhead is 3*8 + n*2*8 bytes.


Declaring a variable

  1. Declare a variable

    /* Declare a variable using an anonymous type */
    tll(int) an_integer_list = tll_init();
  2. Typedef

    /* First typedef the list type */
    typedef tll(int) an_integer_list_t;
    /* Then declare a variable using that typedef */
    an_integer_list_t an_integer_list = tll_init();

Adding items - basic

Use tll_push_back() or tll_push_front() to add elements to the back or front of the list.

tll_push_back(an_integer_list, 4711);
tll_push_front(an_integer_list, 1234);

List length

tll_length() returns the length (number of items) in a list.

tll_push_back(an_integer_list, 1234);
tll_push_back(an_integer_list, 5678);
printf("length: %zu\n", tll_length(an_integer_list));


length: 2

Accessing items

For the front and back items, you can use tll_front() and tll_back() respectively. For any other item in the list, you need to iterate the list and find the item yourself.

tll_push_back(an_integer_list, 1234);
tll_push_back(an_integer_list, 5555);
tll_push_back(an_integer_list, 6789);

printf("front: %d\n", tll_front(an_integer_list));
printf("back: %d\n", tll_back(an_integer_list));


front: 1234
back: 6789


You can iterate the list either forward or backwards, using tll_foreach() and tll_rforeach() respectively.

The it variable should be treated as an opaque iterator type, where it->item is the item.

In reality, it is simply a pointer to the linked list entry, and since tllist is a header-only implementation, you do have access to e.g. the next/prev pointers. There should not be any need to access anything except item however.

Note that it can be named anything.

tll_push_back(an_integer_list, 1);
tll_push_back(an_integer_list, 2);

tll_foreach(an_integer_list, it) {
    printf("forward: %d\n", it->item);

tll_rforeach(an_integer_list, it) {
    printf("reverse: %d\n", it->item);


forward: 1
forward: 2
reverse: 2
reverse: 1

Removing items - basic

tll_pop_front() and tll_pop_back() removes the front/back item and returns it.

tll_push_back(an_integer_list, 1234);
tll_push_back(an_integer_list, 5678);

printf("front: %d\n", tll_pop_front(an_integer_list));
printf("back: %d\n", tll_pop_back(an_integer_list));
printf("length: %zu\n", tll_length(an_integer_list));


front: 1234
back: 5678
length: 0

Adding items - advanced

Given an iterator, you can insert new items before or after that iterator, using tll_insert_before() and tll_insert_after().

tll_foreach(an_integer_list, it) {
    if (it->item == 1234) {
        tll_insert_before(an_integer_list, it, 7777);

Q: Why do I have to pass both the list and the iterator to tll_insert_before()?

A: If not, each element in the list would have to contain a pointer to the owning list, which would significantly increase the overhead.

Removing items - advanced

Similar to how you can add items while iterating a list, you can also remove them.

Note that the *foreach() functions are safe in this regard - it is perfectly OK to remove the "current" item.

tll_foreach(an_integer_list, it) {
    if (it->item.delete_me)
        tll_remove(an_integer_list, it);

To make it slightly easier to handle cases where the item itself must be free:d as well, there is also tll_remove_and_free(). It works just like tll_remove(), but takes an additional argument; a callback that will be called for each item.

tll(int *) int_p_list = tll_init();

int *a = malloc(sizeof(*a));
int *b = malloc(sizeof(*b));

*a = 1234;
*b = 5678;

tll_push_back(int_p_list, a);
tll_push_back(int_p_list, b);

tll_foreach(int_p_list, it) {
    tll_remove_and_free(int_p_list, it, free);


To remove all items, use tll_free(), or tll_free_and_free(). Conceptually, these just do:

tll_foreach(an_integer_list, it) {
    tll_remove(an_integer_list, it);

Note that there is no need to call tll_free() on an empty (tll_length(list) == 0) list.


The easiest way may be to simply copy tllist.h into your project. But see sections below for other ways.


tllist can be installed as a system library. You can then use pkg-config --cflags tllist to get the compiler flags needed to set the include path.

If you are running Arch Linux, there's a bundled PKGBUILD you can use.


You can use tllist as a subproject. In your main project's meson.build, to something like:

tllist = subproject('tllist').get_variable('tllist')
executable('you-executable', ..., dependencies: [tllist])

Or, if tllist has been installed as a system library, a regular

tllist = dependency('tllist')

will suffice. Optionally, you can combine the two; search for a system library first, and fallback to a subproject:

tllist = dependency('tllist', version: '>=1.0.0', fallback: ['tllist', 'tllist'])


Cheat sheet

Function Description Context Complexity
list = tll_init() initialize a new tllist variable to an empty list Variable init O(1)
tll_length(list) returns the length (number of items) of a list O(1)
tll_push_front(list, item) inserts item at the beginning of the list O(1)
tll_push_back(list, item) inserts item at the end of the list O(1)
tll_front(list) returns the first item in the list O(1)
tll_back(list) returns the last item in the list O(1)
tll_pop_front(list) removes and returns the first item in the list O(1)
tll_pop_back(list) removes and returns the last item in the list O(1)
tll_foreach(list, it) iterates the list from the beginning to the end O(n)
tll_rforeach(list, it) iterates the list from the end to the beginning O(n)
tll_insert_before(list, it, item) inserts item before it. tll_(r)foreach() O(1)
tll_insert_after(list, it, item) inserts item after it. tll_(r)foreach() O(1)
tll_remove(list, it) removes it from the list. tll_(r)foreach() O(1)
tll_remove_and_free(list, it, cb) removes it from the list, and calls cb(it->item). tll_(r)foreach() O(1)
tll_free(list) removes all items from the list O(n)
tll_free_and_free(list, cb) removes all items from the list, and calls cb(it->item) for each item. O(n)
tll_sort(list, cmp) sort the list according to the result of cmp(item1, item2) O(n log(n))