Using GLib Lists
================

GLib provides several container types for sets of data: ``GList``, ``GSList``,
``GPtrArray`` and ``GArray``.

It has been common practice in the past to use ``GList`` in all situations where
a sequence or set of data needs to be stored. This is inadvisable: you should
always prefer a ``GPtrArray`` in most situations. ``GPtrArray`` has lower memory
overhead (a third to a half of an equivalent list), better cache locality, and
the same or lower algorithmic complexity for all common operations. The only
typical situation where a ``GList`` may be more appropriate is when dealing with
ordered data, which requires expensive insertions at arbitrary indexes in the
array. If your ordered data set is large, though, you may want to use
``GSequence``, which is a much more efficient data store.

If linked lists are used, be careful to keep the complexity of operations on
them low, using standard CS complexity analysis. Any operation which uses
``g_list_nth()`` or ``g_list_nth_data()`` is almost certainly wrong.

For example, iteration over a ``GList`` should be implemented using the linking
pointers, rather than a incrementing index:

.. tabs::

   .. code-tab:: c

      // some_list is a GList defined elsewhere
      for (GList *l = some_list; l != NULL; l = l->next)
        {
          YourDataType *element_data = l->data;

          // Do something with @element_data
        }

   .. code-tab:: vala

      // some_list is a GList defined elsewhere
      for (List l = some_list; l != null; l = l.next) {
          YourDataType element_data = l.data;

          // Do something with @element_data
      }

      // or

      foreach (YourDataType element_data in some_list) {
          // Do something with @element_data
      }


Using an incrementing index instead results in a quadratic decrease in
performance (O(N²) rather than O(N)):

.. tabs::

   .. code-tab:: c

      // some_list is a GList defined elsewhere

      // g_list_length() will iterate the list to determine its length
      for (guint i = 0; i < g_list_length (some_list); i++)
        {
          // g_list_nth_data() will iterate the list to retrieve the data
          YourDataType *element_data = g_list_nth_data (some_list, i);

          // Do something with @element_data
        }

   .. code-tab:: vala

      // some_list is a GList defined elsewhere

      // List.length () will iterate the list to determine its length
      for (int i = 0; i < some_list.length (); i++) {
          // List.nth_data () will iterate the list to retrieve the data
          YourDataType element_data = some_list.nth_data (i);

          // Do something with @element_data
      }


The performance penalty in the code above comes from ``g_list_length()`` and
``g_list_nth_data()``, which both traverse the list to perform their operations.

Implementing the above with a ``GPtrArray`` has the same complexity as the first
(correct) ``GList`` example, but better cache locality and lower memory
consumption, so will perform better for large numbers of elements:

.. tabs::

   .. code-tab:: c

      // some_array is a GPtrArray defined elsewhere
      for (guint i = 0; i < some_array->len; i++)
        {
          YourDataType *element_data = g_ptr_array_index (some_array, i);

          // Do something with @element_data
        }

   .. code-tab:: vala

      // some_array is a GPtrArray defined elsewhere
      for (int i = 0; i < some_array.length; i++) {
          YourDataType element_data = some_array.get (i);

          // Do something with @element_data
      }