<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="cs">

  <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>Propojené seznamy a kontejnerové typy</desc>

  </info>

  <title>GList</title>

  <section id="glist-usage">

    <title>Použití GList</title>

    
GLib poskytuje někoklik kontejnerových typů pro množiny dat: <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> a <link href="https://developer.gnome.org/glib/stable/glib-Arrays.html">GArray</link>.

    
Dříve bylo běžnou praxí používat GList ve všech situacích, kdy bylo zapotřebí uchovat řadu nebo množinu dat. To ale není rozumné — ve většině situací by místo něj měl být použit GPtrArray. Má menší paměťové nároky (třetinové až poloviční oproti obdobnému seznamu), lepší dostupnost z mezipaměti a stejnou nebo menší algoritmickou složitost pro všechny běžné operace. Jedinou typickou situací, kdy může být GList vhodnější, je při práci se uspořádanými daty ve kterých je požadováno masivní vkládání na libovolné místo v poli.

    
Když jsou použité zřetězené seznamy, dávejte pozor, aby složitost operací zůstala na rozumné úrovni podle standardní analýzy složitosti v matematické informatice. Kterákoliv operace, která používá <link href="https://developer.gnome.org/glib/2.30/glib-Doubly-Linked-Lists.html#g-list-nth">g_list_nth()</link> nebo <link href="https://developer.gnome.org/glib/2.30/glib-Doubly-Linked-Lists.html#g-list-nth-data">g_list_nth_data()</link>, je povětšinou úplně špatně. Například iterace přes GList by měla být implementována pomocí zřetězujících ukazatelů a ne postupným zvyšováním indexu.

    GList *some_list, *l;

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

  {

    gpointer element_data = l->data;

    /* Provedení něčeho s @element_data. */

  }

    
Když se místo toho použije postupné zvyšování indexu, je výsledkem kvadratické snížení výkonu (O(N^2) namísto O(N)):

    GList *some_list;

guint i;

/* Tento algoritmus je neefektivní a neměl by být použit v produkčním kódu. */

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

  {

    gpointer element_data = g_list_nth_data (some_list, i);

    /* Provedení něčeho s @element_data. */

  }

    
Snížení výkonu nastává ve funkcích g_list_length() a g_list_nth_data(), které obě kvůli provedení své operace pole procházejí (O(N)).

    
Implementace kódu uvedeného výše pomocí GPtrArray má stejnou složitost pro první (správnou) implementaci GList, ale lepší dostupnost z mezipaměti a nižší spotřebu paměti, takže bude mít lepší výkon pro velké množství prvků:

    GPtrArray *some_array;

guint i;

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

  {

    gpointer element_data = some_array->pdata[i];

    /* Provedení něčeho s @element_data. */

  }

  </section>

</page>