Linked lists

A linked list is a type of a list (i.e. linearly ordered dynamically-sized container) where elements are not contiguously laid out in the memory, but instead every element is stored individually, and is linked to its neighbouring elements. Internally, a linked list is implemented via C++'s std::list<std::shared_ptr>.

• Operations
• Iterating
• Lifetime
• Generic linked lists

Operations

In terms of supported operations, linked lists are limited in comparison to standard (array) lists. While obtaining an element by its index is supported, it is slower, because in order to find the corresponding element, the algorithm must iterate all elements from the beginning until it finds the desired one.

Adding to a linked list is performed similarly to adding to a normal list:

new LinkedList:ll = linked_list_new();
linked_list_add(ll, true);
linked_list_add_arr(ll, Float:{1.0, 2.0});
linked_list_add_str(ll, "test");
linked_list_add_var(ll, VAR_NULL);
linked_list_delete(ll);

Other operations are supported as well, but those that require an index or a range of indices are potentially slower or unavailable.

Iterating

The main features of linked lists is being able to add or remove any number of elements in the middle without needing to move other elements in the memory and without invalidating any iterators.

new LinkedList:ll = linked_list_new();
linked_list_add_args(ll, 1, 3, 3, 4);
assert linked_list_size(ll) == 4;
new Iter:first = linked_list_iter(ll);
new Iter:last = iter_to_last(linked_list_iter(ll));
assert iter_get(first) == 1 && iter_get(last) == 4;

new Iter:test = linked_list_iter(ll);
iter_move_next(test);
assert iter_get(test) == 3;
iter_insert(test, 2);
assert iter_get(first) == 1 && iter_get(last) == 4;
iter_to_last(test);
iter_move_previous(test);
iter_erase(test);
assert iter_get(first) == 1 && iter_get(last) == 4;

for_linked_list(it : ll)
{
    print_s(str_val(it)); // 1 2 3 4
}

Lifetime

Like normal lists, linked lists are not garbage collected and must be managed explicitly. When a list is no longer usable, linked_list_delete or linked_list_delete_deep must be called to delete it and its contents (recursively in case of linked_list_delete_deep).

Generic linked lists

Linked lists are heterogenous in nature, but they can be limited to a certain tag at compile time:

new LinkedList<Float>:ll = linked_list_new<Float>();
linked_list_add<Float>(ll, 1.0);
linked_list_add<Float>(ll, 1.1);
linked_list_add<Float>(ll, true); //tag mismatch

for_linked_list_of<Float>(it : ll)
{
    print_s(str_val(it));
}