Jednosměrné seznamy jsou těžkou analogií k obousměrným. Základní rozdíl, v čem se tyto dva typy liší, je skutečnost, že jednosměrné seznamy lze procházet jen v jednom směru, tj. nedisponují pointery na „předcházející“ prvky ( prev).
Uzly jednosměrných seznamů jsou definovány strukturou GSList:
struct GSList
{
gpointer data;
GSList *next;
};
Jak vidíte, položka prev skutečně chybí.
Drtivá většina skutečností řečených v minulých dílech o obousměrných seznamech (GLib část 12. a GLib část 13.) platí i pro jednosměrné seznamy. GSList y mají sadu funkcí, které jsou takřka shodné s funkcemi pro práci s GList y ( g_list_...). Každá funkce nebo makro, které má co do činění s jednosměrnými seznamy, začíná „ g_slist_...“.
Následující tabulka shrnuje seznam funkcí pro práci s obousměrnými seznamy a jejich obdob pro manipulaci s jednosměrnými seznamy:
GSList |
GList |
Stručný popis |
GSList* g_slist_append(GSList *list, gpointer data); |
GList* g_list_append(GList *list, gpointer data); |
Přidání prvku na konec seznamu |
GSList* g_slist_prepend(GSList *list, gpointer data); |
GList* g_list_prepend(GList *list, gpointer data); |
Přidání prvku na začátek seznamu |
GSList* g_slist_insert(GSList *list, gpointer data, gint position); |
GList* g_list_insert(GList *list, gpointer data, gint position); |
Přidání prvku na pozici position |
GSList* g_slist_insert_sorted(GSList *list, gpointer data, GCompareFunc func); |
GList* g_list_insert_sorted(GList *list, gpointer data, GCompareFunc func); |
Vložení prvku tak, aby byl seznam seřazený |
GSList* g_slist_remove(GSList *list, gpointer data); |
GList* g_list_remove(GList *list, gpointer data); |
Odstranění uzlu ze seznamu s následnou dealokací |
GSList* g_slist_remove_link(GSList *list, GSList *llink); |
GList* g_list_remove_link(GList *list, GList *llink); |
Odstranění uzlu (prvku) seznamu bez jeho dealokace |
void g_slist_free(GSList *list); |
void g_list_free(GList *list); |
Uvolnění celého seznamu z paměti |
void g_slist_free_1(GSList *list); |
void g_list_free_1(GList *list); |
Dealokace uzlu (prvku) seznamu |
guint g_slist_length(GSList *list); |
guint g_list_length(GList *list); |
Zjištění délky seznamu |
GSList* g_slist_copy(GSList *list); |
GList* g_list_copy(GList *list); |
Vytvoření kopie seznamu |
GSList* g_slist_reverse(GSList *list); |
GList* g_list_reverse(GList *list); |
Změna pořadí prvků (první – poslední,…) |
GSList* g_slist_sort(GSList *list, GCompareFunc compare_func); |
GList* g_list_sort(GList *list, GCompareFunc compare_func); |
Seřazení prvků v seznamu |
GSList* g_slist_concat(GSList *list1, GSList *list2); |
GList* g_list_concat(GList *list1, GList *list2); |
Spojení dvou seznamů do jednoho |
void g_slist_foreach(GSList *list, GFunc func, gpointer user_data); |
void g_list_foreach(GList *list, GFunc func, gpointer user_data); |
Provedení funkce func na každou položku seznamu |
| není k dispozici | GList* g_list_first(GList *list); |
Vrácení prvního prvku seznamu |
GSList* g_slist_last(GSList *list); |
GList* g_list_last(GList *list); |
Vrácení posledního prvku seznamu |
| není k dispozici | #define g_list_previous(list) |
Vrácení předcházejícího prvku |
#define g_slist_next(slist) |
#define g_list_next(slist) |
Vrácení následujícího prvku |
GSList* g_slist_nth(GSList *list, guint n); |
GList* g_list_nth(GList *list, guint n); |
Vrácení n-tého prvku seznamu |
gpointer g_slist_nth_data(GSList *list, guint n); |
gpointer g_list_nth_data(GList *list, guint n); |
Vrácení dat n-tého prvku |
GSList* g_slist_find(GSList *list, gpointer data); |
GList* g_list_find(GList *list, gpointer data); |
Hledání prvku podle dat |
GSList* g_slist_find_custom(GSList *list, gpointer data, GCompareFunc func); |
GList* g_list_find_custom(GList *list, gpointer data, GCompareFunc func); |
Hledání prvku s plnou kontrolou nad operací porovnávání |
gint g_slist_position(GSList *list, GSList *llink); |
gint g_list_position(GList *list, GList *llink); |
Vrácení pozice prvku v seznamu |
gint g_slist_index(GSList *list, gpointer data); |
gint g_list_index(GList *list, gpointer data); |
Vrácení pozice prvku podle dat |
Funkce jsou téměř stejné a stejné jsou i jejich vlastnosti. Patrně jste si všimli, že pro jednoduché seznamy neexistuje žádná funkce g_slist_first() či makro g_slist_previous(). Je to logické: jednosměrné seznamy neposkytují pointery na předcházející prvky a proto by jeho nalezení, popřípadě nalezení prvního prvku seznamu bylo jako škrábat se levou nohou za pravým uchem.
Pro jakýkoliv bližší popis funkcí odkazuji čtenáře na dříve uvedené články o obousměrných seznamech, kde jsou všechny funkce dopodrobna vysvětleny. Jejich popis se dá aplikovat i na jednosměrné seznamy.
A použití?
Jednosměrné seznamy, protože ve svých prvcích GSList postrádají jeden pointer, jsou trochu úspornější co do obsazení paměti než obousměrné seznamy. Jejich použitím si však uzavíráte možnost procházení seznamem ve zpětném směru. Je to opět klasický kompromis mezi výkonností a nároky na paměť (hardware).
Příklad:
/* Nalezeni "predchazejiciho prvku" * k danemu prvku jednosmerneho seznamu */
#include <glib.h>
/* Funkce, ktera vyhleda v seznamu list
* predchozi prvek k prvku link */
GSList* my_g_slist_previous(GSList *list, GSList* link)
{
GSList* l;
l = list;
while (l != NULL) {
if (l->next == link) {
return l;
}
l = l->next;
}
return l;
}
gint main(void)
{
GSList *list = NULL;
GSList *l1, *l2;
/* vytvoreni nejakeho jednosmerneho seznamu */
list = g_slist_append(list, "Josef");
list = g_slist_append(list, "Karel");
list = g_slist_append(list, "Tonda");
list = g_slist_append(list, "Tomas");
/* ziskani odkazu na "nejaky" prvek seznamu */
l1 = list->next->next->next;
/* nalezeni predchazejiciho prvku */
l2 = my_g_slist_previous(list, l1);
/* kontrolni tisk */
printf("Predchazejicim prvkem k prvku %s je %s.\n",
l1->data, l2->data);
/* dealokace a konec */
g_slist_free(list);
return(0);
}
ČLÁNKY DO MAILU