<page xmlns="http://projectmallard.org/1.0/" xmlns:its="http://www.w3.org/2005/11/its" xmlns:xi="http://www.w3.org/2003/XInclude" type="topic" id="glist" xml:lang="de">

  <info>

    <link type="guide" xref="index#specific-how-tos"/>

    <credit type="author copyright">

      <name>Philip Withnall</name>

      <email its:translate="no">philip.withnall@collabora.co.uk</email>

      <years>2015</years>

    </credit>

    <include xmlns="http://www.w3.org/2001/XInclude" href="cc-by-sa-3-0.xml"/>

    <desc>Linked lists and container types</desc>

    <mal:credit xmlns:mal="http://projectmallard.org/1.0/" type="translator copyright">

      <mal:name>Mario Blättermann</mal:name>

      <mal:email>mario.blaettermann@gmail.com</mal:email>

      <mal:years>2016</mal:years>

    </mal:credit>

    <mal:credit xmlns:mal="http://projectmallard.org/1.0/" type="translator copyright">

      <mal:name>Christian Kirbach</mal:name>

      <mal:email>christian.kirbach@gmail.com</mal:email>

      <mal:years>2016</mal:years>

    </mal:credit>

  </info>

  <title>GList</title>

  <section id="glist-usage">

    <title>Verwendung von GList</title>

      GLib provides several container types for sets of data:

      <link href="https://developer.gnome.org/glib/stable/glib-Doubly-Linked-Lists.html">GList</link>,

      <link href="https://developer.gnome.org/glib/stable/glib-Singly-Linked-Lists.html">GSList</link>,

      <link href="https://developer.gnome.org/glib/stable/glib-Pointer-Arrays.html">GPtrArray</link> and

      <link href="https://developer.gnome.org/glib/stable/glib-Arrays.html">GArray</link>.

      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 —

      in most situations, a GPtrArray should be used instead. It 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 linked lists are used, be careful to keep the complexity of operations

      on them low, using standard CS complexity analysis. Any operation which

      uses

      <link href="https://developer.gnome.org/glib/2.30/glib-Doubly-Linked-Lists.html#g-list-nth">g_list_nth()</link> or

      <link href="https://developer.gnome.org/glib/2.30/glib-Doubly-Linked-Lists.html#g-list-nth-data">g_list_nth_data()</link>

      is almost certainly wrong. For example, iteration over a GList should be

      implemented using the linking pointers, rather than a incrementing index:

    GList *some_list, *l;

for (l = some_list; l != NULL; l = l->next)

  {

    gpointer element_data = l->data;

    /* Do something with @element_data. */

  }

      Using an incrementing index instead results in a quadratic decrease in

      performance (O(N^2) rather than O(N)):

    GList *some_list;

guint i;

/* This code is inefficient and should not be used in production. */

for (i = 0; i < g_list_length (some_list); i++)

  {

    gpointer element_data = g_list_nth_data (some_list, i);

    /* Do something with @element_data. */

  }

      The performance penalty comes from g_list_length() and

      g_list_nth_data() which both traverse the list

      (O(N)) to perform their operations.

      Implementing the above with a GPtrArray has the same complexity as the

      first (correct) GList implementation, but better cache locality and lower

      memory consumption, so will perform better for large numbers of elements:

    GPtrArray *some_array;

guint i;

for (i = 0; i < some_array->len; i++)

  {

    gpointer element_data = some_array->pdata[i];

    /* Do something with @element_data. */

  }

  </section>

</page>