单向链表
概念
或许在 GLib 中最简单的容器就是单向链表；即 GSList。如其名称所示，它是一系 列链接到一起的数据条目，可以从一个数据条目导航到下一个数据条目。它之所以 称为单向链表，是因为在条目之间只有一个单向的链接。所以，只能“向前”遍历 列表，但不能向前移动后再向后退。
进一步讲，每次向列表添加一个条目时，都会创建一个新的 GSList 结构体。这个 GSList 结构体由一个数据条目和一个指针构成。先前列表的末尾指向这个新的节 点，这表示现在这个新节点在列表的末尾。这里的术语可能令人费解，因为整个结 构体称为 GSList，而每个节点也是一个 GSList 结构体。
不过，概念上讲，一个列表只是多个列表的一个序列，其中每个列表有一个条目。 这就像是在红灯前的一行汽车；就算是只有一辆汽车在红灯前等待，它也被认为是 一行汽车。
将一长串条目链接起来，随之而来有一些用法。确定列表的长度是一个 O(n) 操作 ；因为只有统计了每一个条目才能指出列表有多长。向列表的起始端添加条目很快 （一个 O(1) 操作），因为列表的长度不是固定的，超出限制值后不必重新构建。 不过，查找某个条目是一个 O(n) 操作，因为需要对整个列表进行一次线性搜索， 直到找到所有寻找的条目。向列表的末尾添加一个条目也是一个 O(n) 操作，因为要想到达末尾，需要从头开始遍历直到列表的末尾。
GSList 可以保存两种基本类型的数据：整型或者指针。不过，这实际上意味着几乎 可以向 GSList 中放入任何内容。例如，如果需要一个“short”数据类型的 GSLi st，那么只需要在 GSList 中放入一个指向 short 类型数据的指针。
现在理论已经足够了；接下来真正地使用 GSList!
创建、添加和销毁
下面的代码将初始化一个 GSList，向其添加两个条目，打印出列表的长度，然后释 放它：
代码： 全选
//ex-gslist-1.c
#include <glib.h>
int main(int argc, char** argv) {
GSList* list = NULL;
g_printf("The list is now %d items long\n", g_slist_length(list));
list = g_slist_append(list, "first");
list = g_slist_append(list, "second");
g_printf("The list is now %d items long\n", g_slist_length(list));
g_slist_free(list);
return 0;
}
***** Output *****
The list is now 0 items long
The list is now 2 items long
关于以上代码的一些注解：
* 大部分 GLib 函数的格式都是 g_(container name)_(function name)。所以 ，要得到某个 GSList 的长度，可以调用 g_slist_length。
* 没有创建新的 GSList 的函数；而只需要声明一个指向 GSList 结构体的指 针并分配一个 NULL 值。
* g_slist_append 会返回列表的新起始地址，所以一定要保存那个返回值。
* g_slist_free 不考虑列表中是否存放了条目；快速查看源代码可以发现，如果 GSList 为 NULL，则 g_slist_free 只是立即返回。 g_slist_length 也可以作 用于空的列表；在那种情况下，它只是返回 0。
添加然后删除数据
可以添加数据；可能还会需要将其删除。这里是一个示例：
代码： 全选
//ex-gslist-2.c
#include <glib.h>
int main(int argc, char** argv) {
GSList* list = NULL;
list = g_slist_append(list, "second");
list = g_slist_prepend(list, "first");
g_printf("The list is now %d items long\n", g_slist_length(list));
list = g_slist_remove(list, "first");
g_printf("The list is now %d items long\n", g_slist_length(list));
g_slist_free(list);
return 0;
}
***** Output *****
The list is now 2 items long
The list is now 1 items long
这段代码中大部分看起来都比较熟悉，不过有一些地方需要考虑；
* 如果调用 g_slist_remove 时传递了一个并不在列表中的条目，那么列表将 不会发生变化。
* g_slist_remove 也会返回列表的新起始位置。
* 可以发现，“first”是调用 g_slist_prepend 添加的。这是个调用比 g_s list_append 更快；它是 O(1) 操作而不是 O(n) 操作，原因如前所述，进行附加 需要遍历整个列表。所以，如果使用 g_slist_prepend 更为方便，那么就应该使用它。
删除重复的条目
这里是当在一个列表中有重复的条目时会发生的问题：
代码： 全选
//ex-gslist-3.c
#include <glib.h>
int main(int argc, char** argv) {
GSList* list = NULL;
list = g_slist_append(list, "first");
list = g_slist_append(list, "second");
list = g_slist_append(list, "second");
list = g_slist_append(list, "third");
list = g_slist_append(list, "third");
g_printf("The list is now %d items long\n", g_slist_length(list));
list = g_slist_remove(list, "second");
list = g_slist_remove_all(list, "third");
g_printf("The list is now %d items long\n", g_slist_length(list));
g_slist_free(list);
return 0;
}
***** Output *****
The list is now 5 items long
The list is now 2 items long
所以，如果 GSList 包含了两个同样的指针，而调用了 g_slist_remove，那么只会
删除第一个指针。不过，可以使用 g_slist_remove_all 删除条目的所有指针。
最后一个、第 n 个 和第 n 个数据
在 GSList 中有了一些条目后，可以通过不同的方式提取它们。这里是一些示例，
并在 g_printf 语句中给出了解释。
代码： 全选
//ex-gslist-4.c
#include <glib.h>
int main(int argc, char** argv) {
GSList* list = NULL;
list = g_slist_append(list, "first");
list = g_slist_append(list, "second");
list = g_slist_append(list, "third");
g_printf("The last item is '%s'\n", g_slist_last(list)->data);
g_printf("The item at index '1' is '%s'\n", g_slist_nth(list, 1)->data);
g_printf("Now the item at index '1' the easy way: '%s'\n", g_slist_nth_data(list, 1));
g_printf("And the 'next' item after first item is '%s'\n", g_slist_next(list)->data);
g_slist_free(list);
return 0;
}
***** Output *****
The last item is 'third'
The item at index '1' is 'second'
Now the item at index '1' the easy way: 'second'
And the 'next' item after first item is 'second'
注意，有一些可以作用于 GSList 的快捷函数；可以简单地调用 g_slist_nth_data，而不需调用先 g_slist_nth 然后再反引用（dereference）返回的指针。
最后一个 g_printf 语句稍有不同。g_slist_next 不是一个函数调用，而是一个宏。它展开为一个指向 GSList 中下一元素的指针反引用。在这种情况下，可以看到，我们传递了 GSList 中的第一个元素，于是那个宏展并给出第二个元素。这也是一个快速的操作，因为没有函数调用的开销。
退一步：使用用户定义的类型
到现在为止我们一直在使用字符串；也就是说，我们只是将指向字符的指针放入到GSList 中。在下面的代码示例中，将会定义一个 Person 结构体，并将这个结构体的一些实例放入到 GSList 中：
代码： 全选
//ex-gslist-5.c
#include <glib.h>
#include <stdlib.h>
typedef struct {
char* name;
int shoe_size;
} Person;
int main(int argc, char** argv) {
GSList* list = NULL;
Person* tom = (Person*)malloc(sizeof(Person));
tom->name = "Tom";
tom->shoe_size = 12;
list = g_slist_append(list, tom);
Person* fred = g_new(Person, 1); // allocate memory for one Person struct
fred->name = "Fred";
fred->shoe_size = 11;
list = g_slist_append(list, fred);
g_printf("Tom's shoe size is '%d'\n", ((Person*)list->data)->shoe_size);
g_printf("The last Person's name is '%s'\n", ((Person*)g_slist_last(list)->data)->name);
g_slist_free(list);
free(tom);
g_free(fred);
return 0;
}
***** Output *****
Tom's shoe size is '12'
The last Person's name is 'Fred'
关于使用 GLib 和用户定义类型的一些注解：
* 可以像使用字符串一样在 GSList 使用用户定义类型。另外要注意，当从列表中取出条目时，需要进行一些强制类型转换。
* 这个示例使用了另一个 GLib 宏 —— g_new 宏 —— 来创建 Fred Person实例。这个宏只是展开并使用 malloc 为给定的类型分配适当数量的内存，但是这比手工输入 malloc 函数调用更为简洁。
* 最后，如果要分配内存，那么还需要释放它。可以看到上面的代码示例如何使用 GLib 函数 g_free 来为 Fred Person 实例完成此任务（因为它是使用 g_ne w 分配的）。在大部分情况下 g_free 只是会包装 free 函数，但是 GLib 也具备内存池功能，g_free 以及其他内存管理函数可以使用它们。
组合、反转，等等
GSList 附带了一些便利的工具，可以连接和反转列表。这里是它们的工作方式：
代码： 全选
//ex-gslist-6.c
#include <glib.h>
int main(int argc, char** argv) {
GSList* list1 = NULL;
list1 = g_slist_append(list1, "first");
list1 = g_slist_append(list1, "second");
GSList* list2 = NULL;
list2 = g_slist_append(list2, "third");
list2 = g_slist_append(list2, "fourth");
GSList* both = g_slist_concat(list1, list2);
g_printf("The third item in the concatenated list is '%s'\n", g_slist_nth_data(both, 2));
GSList* reversed = g_slist_reverse(both);
g_printf("The first item in the reversed list is '%s'\n", reversed->data);
g_slist_free(reversed);
return 0;
}
***** Output *****
The third item in the concatenated list is 'third'
The first item in the reversed list is 'fourth'
正如所预期的，两个列表首尾相连在一起，list2 中的第一个条目成为新的列表中的第三个条目。注意，并没有拷贝条目；它们只是被链接上，这样内存只需要释放一次。
另外，您会发现您只需要使用一个指针反引用（reversed->data）就可以打印出反向列表的第一个条目。由于 GSList 中的每一个条目都是一个指向某个 GSList 结构体的指针，所以要获得第一个条目并不需要调用函数。
简单遍历
这里是遍历 GSList 中所有内容的一个直观方法：
代码： 全选
//ex-gslist-7.c
#include <glib.h>
int main(int argc, char** argv) {
GSList* list = NULL, *iterator = NULL;
list = g_slist_append(list, "first");
list = g_slist_append(list, "second");
list = g_slist_append(list, "third");
for (iterator = list; iterator; iterator = iterator->next) {
g_printf("Current item is '%s'\n", iterator->data);
}
g_slist_free(list);
return 0;
}
***** Output *****
Current item is 'first'
Current item is 'second'
Current item is 'third'
迭代器（iterator）对象只是一个声明为指向 GSList 结构体的变量。这看似奇怪，不过却能满足要求。由于单向列表是一系列 GSList 结构体，所以迭代器与列表的类型应该相同。
另外，注意这个代码段使用的是通常的 GLib 用法习惯；在声明 GSList 本身的时候就声明了迭代器变量。
最后，for 循环的退出表达式检查迭代器是否为 NULL。这样是有效的，因为只有当循环传递了列表中的最后一个条目后它才会成为 NULL。
使用函数进行高级遍历
遍历列表的另一种方法是使用 g_slist_foreach，并提供一个将为列表中的每一个条目调用的函数。
代码： 全选
//ex-gslist-8.c
#include <glib.h>
void print_iterator(gpointer item, gpointer prefix) {
g_printf("%s %s\n", prefix, item);
}
void print_iterator_short(gpointer item) {
g_printf("%s\n", item);
}
int main(int argc, char** argv) {
GSList* list = g_slist_append(NULL, g_strdup("first"));
list = g_slist_append(list, g_strdup("second"));
list = g_slist_append(list, g_strdup("third"));
g_printf("Iterating with a function:\n");
g_slist_foreach(list, print_iterator, "-->");
g_printf("Iterating with a shorter function:\n");
g_slist_foreach(list, (GFunc)print_iterator_short, NULL);
g_printf("Now freeing each item\n");
g_slist_foreach(list, (GFunc)g_free, NULL);
g_slist_free(list);
return 0;
}
***** Output *****
Iterating with a function:
--> first
--> second
--> third
Iterating with a shorter function:
first
second
third
Now freeing each item
在这个示例中有很多好东西：
* 一条类似 GSList x = g_slist_append(NULL, [whatever]) 的语句让您能够一举声明、初始化并将第一个条目添加到列表。
* g_strdup 函数可以方便地复制字符串；如果使用了它，那么要记得释放。
* g_slist_foreach 允许传递一个指针，这样就可以根据列表中的每个条目有
效地为其赋与任意参数。例如，可以传递一个累加器并收集关于列表中每个条目的信息。遍历函数的唯一受限之处在于它至少要使用一个 gpointer 作为参数；现在可以了解在只接收一个参数时 print_interator_short 如何工作。
* 注意，代码使用一个内置的 GLib 函数作为 g_slist_foreach 的参数来释放所有字符串。在此示例中，所有需要做的只是将 g_free 强制类型转换为 GFunc 以使其生效。注意，仍然可以单独使用 g_slist_free 来释放 GSList 本身。
使用 GCompareFunc 排序
可以通过提供一个知道如何比较列表中条目的函数来对 GSLit 进行排序。下面的示例展示了对字符串列表进行排序的一种方法：
代码： 全选
//ex-gslist-9.c
#include <glib.h>
gint my_comparator(gconstpointer item1, gconstpointer item2) {
return g_ascii_strcasecmp(item1, item2);
}
int main(int argc, char** argv) {
GSList* list = g_slist_append(NULL, "Chicago");
list = g_slist_append(list, "Boston");
list = g_slist_append(list, "Albany");
list = g_slist_sort(list, (GCompareFunc)my_comparator);
g_printf("The first item is now '%s'\n", list->data);
g_printf("The last item is now '%s'\n", g_slist_last(list)->data);
g_slist_free(list);
return 0;
}
***** Output *****
The first item is now 'Albany'
The last item is now 'Chicago'
注意，如果第一个条目小于第二个，则 GCompareFunc 返回一个负值，如果相等则返回 0，如果第二个大于第一个则返回一个正值。只要您的比较函数符合此规范，在内部它可以做任何所需要的事情。
另外，由于各种其他 GLib 函数也遵循此模式，所以可以简单地委派给它们。实际上，在上面的示例中，可以简单地把 my_comparator 调用替换为 g_slist_sort(l ist, (GCompareFunc)g_ascii_strcasecmp) 等调用，会获得相同的结果。
查找元素
有一些方法可以在 GSList 查找元素。已经介绍了如何简单地遍历列表的全部内容，比较每个条目，直到找到了目标条目。如果已经拥有了要寻找的数据，而只是想要获得它在列表中的位置，那么可以使用 g_slist_find。最后，可以使用 g_slist_find_custom，它允许您使用一个函数来检查列表中的每一个条目。下面展示了g_slist_find 和 g_slist_find_custom：
代码： 全选
//ex-gslist-10.c
#include <glib.h>
gint my_finder(gconstpointer item) {
return g_ascii_strcasecmp(item, "second");
}
int main(int argc, char** argv) {
GSList* list = g_slist_append(NULL, "first");
list = g_slist_append(list, "second");
list = g_slist_append(list, "third");
GSList* item = g_slist_find(list, "second");
g_printf("This should be the 'second' item: '%s'\n", item->data);
item = g_slist_find_custom(list, NULL, (GCompareFunc)my_finder);
g_printf("Again, this should be the 'second' item: '%s'\n", item->data);
item = g_slist_find(list, "delta");
g_printf("'delta' is not in the list, so we get: '%s'\n", item ? item->data : "(null)");
g_slist_free(list);
return 0;
}
***** Output *****
This should be the 'second' item: 'second'
Again, this should be the 'second' item: 'second'
'delta' is not in the list, so we get: '(null)'
注意，g_slist_find_custom 也使用了一个可以指向任意内容的指针作为第二个参数，所以，如果需要，可以传递进来一些内容以帮助查找函数。另外，GCompare 函数是最后一个参数，而不是第二个参数，因为它在 g_slist_sort 之中。最后，失败的查找会返回 NULL。
通过插入进行高级添加
既然已经接触过几次 GCompareFunc，一些更有趣的插入操作会更有意义。使用 g_slist_insert 可以将条目插入到指定的位置，使用 g_slist_insert_before 可以将条目插入到特定位置之前，使用 g_slist_insert_sorted 可以进行有序插入。这里是样例：
代码： 全选
//ex-gslist-11.c
#include <glib.h>
int main(int argc, char** argv) {
GSList* list = g_slist_append(NULL, "Anaheim "), *iterator = NULL;
list = g_slist_append(list, "Elkton ");
g_printf("Before inserting 'Boston', second item is: '%s'\n", g_slist_nth(list, 1)->data);
list=g_slist_insert(list, "Boston ", 1);
g_printf("After insertion, second item is: '%s'\n", g_slist_nth(list, 1)->data);
list = g_slist_insert_before(list, g_slist_nth(list, 2), "Chicago ");
g_printf("After an insert_before, third item is: '%s'\n", g_slist_nth(list, 2)->data);
g_printf("After inserting 'Denver', here's the final list:\n");
g_slist_foreach(list, (GFunc)g_printf, NULL);
g_slist_free(list);
return 0;
}
***** Output *****
Before inserting 'Boston', second item is: 'Elkton '
After insertion, second item is: 'Boston '
After an insert_before, third item is: 'Chicago '
After inserting 'Denver', here's the final list:
Anaheim Boston Chicago Denver Elkton
由于 g_slist_insert_sorted 使用了 GCompareFunc，所以复用内置的 GLib 函数g_ascii_strcasecmp 也很简单。现在您应该已经能理解为什么在每个条目的末尾有额外的空间；在代码示例的最后加入了另一个 g_slist_foreach 示例，这一次是使用 GFunc 作为参数。
自定义数据结构排序 (根据字符)
代码： 全选
#include <glib.h>
typedef struct {
char* name;
int shoe_size;
} Person;
gint my_comparator(gconstpointer item1, gconstpointer item2) {
return g_ascii_strcasecmp(((Person*)item1)->name, ((Person*)item2)->name);
}
int main(int argc, char** argv) {
GSList* list = NULL;
Person* tom = (Person*)g_malloc(sizeof(Person));
tom->name = "Tom";
tom->shoe_size = 12;
list = g_slist_append(list, tom);
Person* fred = g_new(Person, 1); // allocate memory for one Person struct
fred->name = "Fred";
fred->shoe_size = 11;
list = g_slist_append(list, fred);
Person* god = g_new(Person, 1); // allocate memory for one Person struct
god->name = "zod";
god->shoe_size = 15;
list = g_slist_append(list, god);
list = g_slist_sort(list, (GCompareFunc)my_comparator);
g_printf("Tom's shoe size is '%d'\n", ((Person*)list->data)->shoe_size);
g_printf("The last Person's name is '%s'\n", ((Person*)g_slist_last(list)->data)->name);
g_slist_free(list);
g_free(tom);
g_free(fred);
g_free(god);
return 0;
}
***** Output *****
Tom's shoe size is '11'
The last Person's name is 'zod'
自定义数据结构排序（根据数字）
代码： 全选
#include <glib.h>
typedef struct {
char* name;
int shoe_size;
} Person;
gint my_comparator(gconstpointer item1, gconstpointer item2) {
if(((Person*)item1)->shoe_size > ((Person*)item2)->shoe_size)
{
return 1;
}
else
{
return 0;
}
// return g_ascii_strcasecmp(((Person*)item1)->name, ((Person*)item2)->name);
}
int main(int argc, char** argv) {
GSList* list = NULL;
Person* tom = (Person*)g_malloc(sizeof(Person));
tom->name = "Tom";
tom->shoe_size = 10;
list = g_slist_append(list, tom);
Person* fred = g_new(Person, 1); // allocate memory for one Person struct
fred->name = "yred";
fred->shoe_size = 11;
list = g_slist_append(list, fred);
Person* god = g_new(Person, 1); // allocate memory for one Person struct
god->name = "zod";
god->shoe_size = 15;
list = g_slist_append(list, god);
list = g_slist_sort(list, (GCompareFunc)my_comparator);
g_printf("Tom's shoe size is '%d'\n", ((Person*)list->data)->shoe_size);
g_printf("The last Person's name is '%s'\n", ((Person*)g_slist_last(list)->data)->name);
g_slist_free(list);
g_free(tom);
g_free(fred);
g_free(god);
return 0;
}
在先前提到的三个开放源代码的实际应用程序中，可以发现在很多地方使用了 GSList。大部分用法相当普通，有很多插入、附加、删除，等等。不过有一些更有趣的东西。
Gaim 使用 GSList 来保存当前会话以及大部分插件中的各种内容：
* gaim-1.2.1/src/away.c 使用有序的 GSList 来保存“离开消息”（客户机离线期间收到的消息）。它使用了一个定制的 GCompareFunc，即 sort_awaymsg_list，用于保存那些以发送者名称排序的消息。
* gaim-1.2.1/src/protocols/gg/gg.c 使用 GSList 来保存允许帐号的一个列表；然后它使用一个定制的查找器来确认某个帐号在列表中。定制的查找器简单地委派 g_ascii_strcasecmp，所以有可能会弃用它，并将 g_ascii_strcasecmp 直接传递给 g_slist_find_custom。
Evolution 同样使用了很多 GSList：
* evolution-data-server-1.0.2/calendar/libecal/e-cal-component.c 使用GSList 来存会议参与者。有时，它会反复调用 g_slist_prepend，并在结束时使用 g_slist_reverse 令条目按期望排序，以此构建那个 GSList。如前所述，这样做比使用 g_slist_append 添加条目更快。
* evolution-2.0.2/addressbook/gui/contact-editor/e-contact-editor.c在一种卫述句（guard clause）中使用 g_slist_find；它在信号处理器中使用它，以确保它在一个信号回调中接收到的 EContactEditor 在被作为参数传递到某个函数之前能够保存。
GIMP 也以一些适宜的方式使用了 GSList：
* gimp-2.2.4/plug-ins/maze/algorithms.c 在迷宫生成（maze-generations ）算法中使用 GSList 追踪单元（cells）。
* gimp-2.2.4/app/widgets/gimpclipboard.c 使用 GSList 来保存剪贴板象素缓冲区格式（比如 PNG 和 JPEG）；它向 g_slist_sort 传递一个定制的 GCompar eFunc。
* gimp-2.2.4/app/core/gimppreviewcache.c 使用 GSList 作为一种基于大小的队列；它在 GSList 中保存图象预览，使用 g_slist_insert_sorted 优先插入较小的图象。同一文件中的另一个函数会遍历同一个 GSList 并比较每一个条目的表面区域，找出要删除的最小那一个，以此来整理缓存。
