General-purpose linked list implementation in the C89 language that runs on all POSIX-compatible systems.
To initialise a list, call the m_list_init function.
The first and the last element of the list can be accessed with the
m_list_first and m_list_last functions respectively. The n-th element of
the list can be accessed with the n_list_nth function. Once you have obtained
the struct m_elem entry, you can move to the previous or the next element
with m_elem_prev and m_elem_next functions. To obtain the actual data
stored in the element, use the m_elem_data function.
To append or prepend elements to the list, use m_list_append and
m_list_prepend functions. To insert an element after another element that is
already in the list, use the m_list_insert function.
To retrieve the length of the list, use the function m_list_length. The
function operates in constant time.
To remove an element from the list, use the function m_list_remove or
m_list_remove_safe. The difference between these two functions is that the
safe variant verifies that the element selected for removal belongs to the
specified list.
To remove all elements, use m_list_clear.
In order to apply a certain function to all element data, the standard map
function is provided under the name m_list_map.
The standard join algorithm allows you to insert an element between every consecutive pair of elements in the list. Note that this is a very powerful ability when combined with shallow copies (hence the actual object exists only once).
It is up to you to decide if the list element should point to already
existing data that you mallloced earlier or whether it should be copied to a
separate memory managed by the m_list. The decision is made in one of the
m_list_append, m_list_prepend, m_list_insert functions. Possible values
are either M_LIST_COPY_DEEP for an internal copy of the memory, or
M_LIST_COPY_SHALLOW for a pointer-copy only. The size argument (one before
the last) of the function can be ignored with value 0 in case of the shallow
copy.
All operations have O(1) space complexity, with the exception of
m_list_build_index with space complexity of O(n).
| Operation | Time |
|---|---|
m_elem_data |
O(1) |
m_elem_next |
O(1) |
m_elem_prev |
O(1) |
m_list_append |
O(1) |
m_list_build_index |
O(n) |
m_list_copy |
O(n) |
m_list_drop_index |
O(1) |
m_list_equal |
O(n) |
m_list_error_string |
O(1) |
m_list_filter |
O(n) |
m_list_find |
O(n) |
m_list_first |
O(1) |
m_list_generate |
O(n) |
m_list_init |
O(n) |
m_list_insert |
O(1) |
m_list_is_empty |
O(1) |
m_list_is_sorted |
O(n) |
m_list_join |
O(n) |
m_list_last |
O(1) |
m_list_length |
O(1) |
m_list_map2 |
O(n) |
m_list_map |
O(n) |
m_list_match_all |
O(n) |
m_list_match_any |
O(n) |
m_list_match_at_least |
O(n) |
m_list_match_exactly |
O(n) |
m_list_nth |
O(1) or O(n) |
m_list_prepend |
O(1) |
m_list_remove_all |
O(n) |
m_list_remove_first |
O(1) |
m_list_remove_last |
O(1) |
m_list_remove_safe |
O(n) |
m_list_remove |
O(1) |
m_list_reverse |
O(n) |
m_list_sort |
O(nlogn) |
m_list_zip |
O(n) |
where n denotes the number of list elements. |
- Sum of integers
- Comma-separated words
- [Postfix calculator] (examples/calc.md)
- [Fizz buzz] (examples/fizz_buzz.md)
- [String palindrome test] (examples/palindrome.md)
By using only a certain subset of the m_list API, it is possible to achieve
the functionality of the stack data structure. Since it is possible to
manipulate with both ends of a m_list, it is necessary to choose one end and
be consistent. This example will use the beginning of the list.
In order to see what is on top of the stack, use the m_list_first function.
To remove the top value from the stack, use the m_list_remove_first function.
Adding to the stack is enabled by the m_list_prepend function.
As with the stack, it is necessary to choose a direction of usage of the list. The queue in this example will retrieve elements from the beginning of the list and add new values to the end.
To see what will be the next dequeued element, use the m_list_first function.
To add elements to the queue, use the m_list_append function.
To retrieve elements from the queue, use the m_list_remove_first function.
Used by all algorithms and general-purpose functions in case of a successful run of the function.
Used by all predicates and some of the general-purpose functions to indicate that the expected conditions were met.
Used by all predicates and some of the general-purpose functions to indicate that the expected conditions were not met. It is important to note that this return code is not an error, but a valid logic value.
Used by every function to indicate that one or more of the essential arguments
were NULL. Arguments such as payload can hold the value of NULL, since it
might be a valid value picked by the user.
Used by functions that expect an index or a count that relates to the elements. This return codes indicates that the number supplied is larger than the length of the list.
Returned by the m_list_remove_safe function in case that the element selected
for removal is not present in the list.
Returned in case that the copy argument of a function is not one of the
following: M_LIST_COPY_SHALLOW, M_LIST_COPY_DEEP.
Returned in case that the loc argument of a function is not one of the
following: M_LIST_INSERT_BEFORE, M_LIST_INSERT_AFTER.
Returned by the m_list_error_string function, in case that the queries return
code does not exists.
- FreeBSD 10.0 with Clang 3.3
- OS X 10.9 with Clang 3.5
- Linux Gentoo 2.2 with Clang 3.6
If a platform does not appear to be in the previous list, it does not mean that
m_list will not work in such environment. It only means that nobody tested
it - you are encouraged to do so and report either success or failure.
$ ninja
$ sudo ./install.sh
2-clause BSD license. For more information please consult the LICENSE file. In the case that you need a different license, feel free to contact me.
Daniel Lovasko (daniel.lovasko@gmail.com)