单向链表是一种基础的数据结构，也是一种简单而灵活的数据结构，本文讨论单向链表的基本概念及实现方法，并着重介绍使用GLib的GList实现单向链表的方法及步骤，本文给出了多个实际范例源代码，旨在帮助学习基于GLib编程的读者较快地掌握GSList的使用方法，本文程序在 ubuntu 20.04 下编译测试完成，gcc 版本号 9.4.0；本文适合初学者阅读。
1 单向链表及其实现
-
单向链表是一种基础的数据结构，它由一系列节点组成，每个节点都包含数据部分和指向下一个节点的指针；
-
这种链表的特点是数据只能在一个方向上流动，即从头节点开始，通过每个节点的指针依次访问后续节点，直到链表的末尾；
-
在单向链表中，头节点是链表的起始点，它存储了链表的第一个数据元素以及指向下一个节点的指针；
-
随后的每个节点都存储了自己的数据和一个指向下一个节点的指针，这样形成了链表的结构；
-
链表的最后一个节点，也就是尾节点，它的指向下一个节点的指针指向 NULL，表示链表的结束。
-
单向链表的主要操作包括：
- 插入节点：可以在链表的头部、尾部或中间某个位置插入新的节点。
- 删除节点：可以删除链表中的任意节点，并通过调整指针来保持链表的完整性。
- 遍历链表：通过从头节点开始，依次访问每个节点，直到到达链表的末尾。
- 查找节点：根据特定的条件或值，在链表中查找节点。
-
单向链表的优势在于其动态的内存分配和高效的插入与删除操作，特别是在链表中间或头部插入和删除节点时，只需调整指针，无需移动其他数据；
-
然而，单向链表的访问效率较低，因为访问特定位置的元素需要从头节点开始遍历。
-
总的来说，单向链表是一种简单而灵活的数据结构，适用于需要频繁插入和删除操作，但访问操作相对较少的场景。
-
下面程序是一个简单的单向链表的 C 语言标准库实现，sllist-c.c(点击文件名下载源程序)
-
编译：
gcc -Wall -g sllist-c.c -o sllist-c -
运行：
./sllist-c -
该程序实现了单向链表的插入、删除、遍历和查找；
-
该程序首先建立一个单向链表，并在链表中加入 4 个节点，数据分别为：1、2、3、5，然后显示整个链表；
-
在第 2 个节点(数据为 3，索引号为 2)的后面插入节点，数据为 4，然后显示整个链表；
-
将第 2 个节点(数据为 3，索引号为 2)删除，然后显示整个链表；
-
最后释放整个链表；
-
运行截图：
GLib__GSList_31">2 GLib 中单向链表结构 GSList
- GLib API version 2.0 手册 (点击查看手册)
- GLib API 手册中 GSList 部分 (点击查看手册)
- 在 GLib 中，单向链表是通过GSList结构体实现的。GSList是一个简单的单向链表结构，用于存储各种类型的数据；
- GSList 定义如下：
struct GSList {gpointer data;GSList *next; } - data 为单向链表的数据指针，可以指向任何类型或结构的数据；
- next 为指向该单向链表下一个节点的指针；
- GLib 为单向链表结构 GSList 的操作提供了大量的函数，本文仅就其中的一部分函数进行介绍；
- 添加、插入新节点
g_slist_append()在单向链表的最后添加一个新节点；GSList *g_slist_append(GSList *list, gpointer data)g_slist_prepend()在单向链表的最前面添加一个新节点；GSList *g_slist_prepend(GSList *list, gpointer data)g_slist_insert()在单向链表的中间插入一个新节点；GSList *g_slist_insert(GSList *list, gpointer data, gint position)g_slist_insert_before()在包含指定数据的节点之前插入一个新节点；GSList *g_slist_insert_before(GSList *slist, GSList *sibling, gpointer data)
- 删除节点
g_slist_remove_link()从单向链表中删除一个节点，但并不释放该节点占用的内存GSList *g_slist_remove_link(GSList *list, GSList *link_)g_slist_delete_link()从单向链表中删除一个节点，并释放该节点占用的内存；GSList *g_slist_delete_link(GSList *list, GSList *link_)g_slist_remove()从单向链表中删除指定数据的一个节点，如果链表中有指定数据的节点有多个，将只删除第一个；GSList *g_slist_remove(GSList *list, gconstpointer data)g_slist_remove_all()从单向链表中删除指定数据的所有节点；GSList *g_slist_remove_all(GSList *list, gconstpointer data)
- 遍历链表
- 查找节点
- 释放链表
- 其它
GSList__184">3 如何使用 GSList 实现单向链表
-
该程序实现的功能与文章开头的程序 sllist-c.c 完全一样，但程序看上去要简洁很多，我们不妨把源程序列在这里
#include <stdio.h> #include <glib.h>void print_node(gpointer data, gpointer user_data) {printf("%d -> ", GPOINTER_TO_INT(data)); }void print_list(GSList *list) {g_slist_foreach(list, &print_node, NULL);printf("NULL\n"); }int main() {GSList *list = NULL;printf("Append 4 nodes, the data are 1, 2, 3, 5.\n");list = g_slist_append(list, GINT_TO_POINTER(1));list = g_slist_append(list, GINT_TO_POINTER(2));list = g_slist_append(list, GINT_TO_POINTER(3));list = g_slist_append(list, GINT_TO_POINTER(5));print_list(list);printf("Insert a new node after node with the data 3.\n");list = g_slist_insert(list, GINT_TO_POINTER(4), 3);print_list(list);printf("Remove node with the data 3.\n");list = g_slist_remove(list, GINT_TO_POINTER(3));print_list(list);// Free the listg_slist_free(list);return 0; } -
编译：
gcc -Wall -g sllist-glib.c -o sllist-glib `pkg-config --cflags --libs glib-2.0` -
其中，
pkg-config --cflags --libs glib-2.0的含义在文章《使用GLib进行C语言编程的实例》中做过介绍； -
运行：
./sllist-glib -
该程序实现了单向链表的插入、删除、遍历和查找；
-
print_list()中使用g_slist_foreach()对链表进行遍历，对链表中的每个节点数据，将调用函数print_node()； -
运行截图：
4 单向链表的应用场景
GLib__GSList__FIFO__257">5 基于 GLib 的 GSList 实现的 FIFO 队列
-
FIFO(First Input First Output)队列，也就是先进先出队列，是一种简单的机制，操作一个 FIFO 队列需要队列的头指针和尾指针；
-
当向 FIFO 队列中加入数据时，数据添加到队列的尾指针处，当从队列中取出数据时，要从队列的头指针处取；
-
FIFO 队列的重要参数是队列的最大长度，当队列中数据的数量达到队列的最大长度时，则不能再向队列中添加数据；
-
FIFO 队列的两个重要判断就是判断队列为空(队列中没有数据)或者队列已满(数据数量达到最大长度)；
-
源程序 queue-glib.c(点击文件名下载源程序) 基于 GLib 的 GSList 实现了一个简单的 FIFO 队列；
-
该程序实现了 FIFO 队列的两个基本操作：入队操作和出队操作，基于 GLib 使得程序相当的简单；
#include <stdio.h> #include <glib.h>#define QUEUE_MAX_LEN 10 GSList *queue_head, *queue_tail; // head and tail pointers of the queue guint32 queue_max_len; // Max. length of the queuevoid queue_init(int maxn) {queue_head = queue_tail = NULL;queue_max_len = maxn; }gboolean queue_put(gpointer data) {guint queue_len = g_slist_length(queue_head); // length of the queueif (queue_len >= queue_max_len) {// the queue is fullreturn FALSE;} else {queue_head = g_slist_append(queue_head, data); // append a node with data to the queuequeue_tail = g_slist_last(queue_head); // get the pointer of last node}return TRUE; }gpointer queue_get() {guint queue_len = g_slist_length(queue_head); // length of the queueif (queue_len == 0) {// the queue is emptyreturn NULL;}gpointer queue_data = queue_tail->data; // data pointer of the last nodequeue_head = g_slist_delete_link(queue_head, queue_tail); // delete the last nodeif (queue_head == NULL) {queue_tail = queue_head; // the queue is empty} else {queue_tail = g_slist_last(queue_head); // get the pointer of last node}return queue_data; }int main(int argc, char **argv) {guint64 len;if (argc >= 2) {len = g_ascii_strtoll(argv[1], NULL, 10); // Convert string to intif (len <= 0 || len > (QUEUE_MAX_LEN * 10)) {len = QUEUE_MAX_LEN;}} else {len = QUEUE_MAX_LEN;}printf("Max. length of the queue is %ld.\n", len);queue_init(len); // Initialize the queueguint16 i;// append some data to the queuefor (i = 0; i < (queue_max_len << 1); ++i) {if (queue_put(GINT_TO_POINTER(i + 1))) {printf("Put data %d into the queue.\n", i + 1);} else {printf("The queue is full.\n");break;}}// get some data from the queuefor (i = 0; i < (queue_max_len << 1); ++i) {gpointer queue_data = queue_get();if (queue_data != NULL) {printf("Get data %d from the queue.\n", GPOINTER_TO_INT(queue_data));} else {printf("The queue is empty.\n");break;}}return 0; } -
可以看出，用 GLib 实现的 FIFO 队列非常简洁；
-
编译：
gcc -Wall -g queue-glib.c -o queue-glib `pkg-config --cflags --libs glib-2.0` -
其中，
pkg-config --cflags --libs glib-2.0的含义在文章《使用GLib进行C语言编程的实例》中做过介绍； -
运行：
./queue-glib 8 -
运行截图：
-
该程序并不完整，如果实际运用，至少要加一个互斥锁，以保证 FIFO 队列的线程安全；
-
使用 GLib 的 GSList 实现的 FIFO 队列，其中的数据并不需要是相同的数据类型，因为队列中存储的数据的指针，这一点在某些应用场景下会带来一些方便，但也会增加开销，而且在数据使用完成后有可能需要释放额外申请的内存空间。
email: hengch@163.com
![[全网首篇]关于 VMSA-2024-0019 安全公告（CVE-2024-38812、CVE-2024-38813）的说明与解决方案](https://i-blog.csdnimg.cn/direct/cbe84a2bcbed4b8d87e651bb154c426b.png)
