单向链表以及如何使用GLib中的GSList实现单向链表

单向链表是一种基础的数据结构，也是一种简单而灵活的数据结构，本文讨论单向链表的基本概念及实现方法，并着重介绍使用GLib的GSList实现单向链表的方法及步骤，本文给出了多个实际范例源代码，旨在帮助学习基于GLib编程的读者较快地掌握GSList的使用方法，本文程序在 ubuntu 20.04 下编译测试完成，gcc 版本号 9.4.0；本文适合初学者阅读。

1 单向链表及其实现

在文章《使用GLib进行C语言编程的实例》中，简单介绍了 GLib，建议阅读本文前先阅读这篇文章；
单向链表是一种基础的数据结构，‌它由一系列节点组成，‌每个节点都包含数据部分和指向下一个节点的指针；
这种链表的特点是数据只能在一个方向上流动，‌即从头节点开始，‌通过每个节点的指针依次访问后续节点，‌直到链表的末尾；
在单向链表中，‌头节点是链表的起始点，‌它存储了链表的第一个数据元素以及指向下一个节点的指针；
随后的每个节点都存储了自己的数据和一个指向下一个节点的指针，‌这样形成了链表的结构；
链表的最后一个节点，‌也就是尾节点，‌它的指向下一个节点的指针指向 NULL，‌表示链表的结束。‌
单向链表的主要操作包括：‌
1. 插入节点：‌可以在链表的头部、‌尾部或中间某个位置插入新的节点。‌
2. 删除节点：‌可以删除链表中的任意节点，‌并通过调整指针来保持链表的完整性。‌
3. 遍历链表：‌通过从头节点开始，‌依次访问每个节点，‌直到到达链表的末尾。‌
4. 查找节点：‌根据特定的条件或值，‌在链表中查找节点。‌
单向链表的优势在于其动态的内存分配和高效的插入与删除操作，‌特别是在链表中间或头部插入和删除节点时，‌只需调整指针，‌无需移动其他数据；
然而，‌单向链表的访问效率较低，‌因为访问特定位置的元素需要从头节点开始遍历。‌
总的来说，‌单向链表是一种简单而灵活的数据结构，‌适用于需要频繁插入和删除操作，‌但访问操作相对较少的场景。‌
下面程序是一个简单的单向链表的 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)删除，然后显示整个链表；
最后释放整个链表；
运行截图：

2 GLib 中单向链表结构 GSList

GLib API version 2.0 手册 (点击查看手册)
GLib API 手册中 GSList 部分 (点击查看手册)
在 GLib 中，‌单向链表是通过GSList结构体实现的。‌GSList是一个简单的单向链表结构，‌用于存储各种类型的数据；

GSList 定义如下：

1
2
3
4


struct GSList {
    gpointer data;
    GSList *next;
}

data 为单向链表的数据指针，可以指向任何类型或结构的数据；
next 为指向该单向链表下一个节点的指针；
GLib 为单向链表结构 GSList 的操作提供了大量的函数，本文仅就其中的一部分函数进行介绍；

添加、插入新节点
- g_slist_append() 在单向链表的最后添加一个新节点；
  1
  
  GSList *g_slist_append(GSList *list, gpointer data)
  - list - 指向单向链表的指针
  - data - 指向添加节点的数据
  - 返回指向单向链表的起始指针；
  - 说明：在单向链表的最后添加节点，必须要遍历整个链表才能找到链表的尾部，这种做法效率很低，通常的做法是使用 g_slist_prepend() 在链表的起始位置添加节点，当所有节点添加完毕后，再使用 g_slist_reverse() 将整个链表反转；
- g_slist_prepend() 在单向链表的最前面添加一个新节点；
  1
  
  GSList *g_slist_prepend(GSList *list, gpointer data)
  - list - 指向单向链表的指针
  - data - 指向添加节点的数据
  - 返回指向单向链表的指针，在单向链表的开头添加一个节点，单向链表的指针是肯定会变化的；
- g_slist_insert() 在单向链表的中间插入一个新节点；
  1
  
  GSList *g_slist_insert(GSList *list, gpointer data, gint position)
  - list - 指向单向链表的指针
  - data - 指向添加节点的数据
  - position - 插入节点的位置，如果是负数或者超过了该单向链表的节点的数量，新节点将插到单向链表的最后；
  - 返回该单向链表的起始指针；
- g_slist_insert_before() 在包含指定数据的节点之前插入一个新节点；
  1
  
  GSList *g_slist_insert_before(GSList *slist, GSList *sibling, gpointer data)
  - slist - 指向单向链表的指针
  - data - 指向添加节点的数据
  - sibling - 指向一个节点的指针，将在这个节点前插入新节点
  - 返回该单向链表的起始指针；
删除节点
- g_slist_remove_link() 从单向链表中删除一个节点，但并不释放该节点占用的内存
  1
  
  GSList *g_slist_remove_link(GSList *list, GSList *link_)
  - list - 指向单向链表的指针；
  - link_ - 指向单向链表中一个节点的指针，该节点将被删除；
  - 返回该单向链表的起始指针；
  - 该函数并不释放被删除的节点内存，被删除的节点的 next 指针将指向 NULL，所以可以认为被删除的节点变成了一个只有一个节点的新的单向链表；
- g_slist_delete_link() 从单向链表中删除一个节点，并释放该节点占用的内存；
  1
  
  GSList *g_slist_delete_link(GSList *list, GSList *link_)
  - list - 指向单向链表的指针；
  - link_ - 指向单向链表中一个节点的指针，该节点将被删除；
  - 返回该单向链表的起始指针；
  - 该函数与 g_slist_remove_link() 的唯一区别是该函数在删除节点后释放了被删除节点占用的内存；
- g_slist_remove() 从单向链表中删除指定数据的一个节点，如果链表中有指定数据的节点有多个，将只删除第一个；
  1
  
  GSList *g_slist_remove(GSList *list, gconstpointer data)
  - list - 指向单向链表的指针
  - data - 指向要删除节点的数据
  - 返回该单向链表的起始指针；
- g_slist_remove_all() 从单向链表中删除指定数据的所有节点；
  1
  
  GSList *g_slist_remove_all(GSList *list, gconstpointer data)
  - list - 指向单向链表的指针
  - data - 指向要删除节点的数据
  - 返回该单向链表的起始指针；
遍历链表
- g_slist_foreach() 遍历单向链表，每个节点都会调用一个指定函数；
  1
  
  void g_slist_foreach(GSList *list, GFunc func, gpointer user_data)
  - list - 指向单向链表的指针
  - func - 一个指向函数的指针，遍历到单向链表的每个节点时，都会调用这个函数；
  - GFunc 的定义如下：
  1
  
  void (* GFunc) (gpointer data, gpointer user_data)
  - GFunc 的定义表明，传递给 func 的参数有两个，一个是 data - 指向当前节点的节点数据指针，另一个就是指向自定义参数 user_data 的指针
  - user_data - 指针指向调用 func 时传递的用户参数；
查找节点
- g_slist_find() 查找链表中包含给定数据的节点；
  1
  
  GSList *g_slist_find(GSList *list, gconstpointer data)
  - list - 指向单向链表的指针
  - data - 指向要查找节点的数据
  - 返回在单向链表中找到的节点的指针，如果没有找到相应节点，返回 NULL;
- g_slist_index() 获取包含给定数据的节点的位置(从 0 开始)；
  1
  
  gint g_slist_index(GSList *list, gconstpointer data)
  - list - 指向单向链表的指针；
  - data - 指向要查找节点的数据；
  - 返回数据为 data 的节点在单向链表中的位置(从 0 开始)，如果没找到相应节点，则返回 -1；
- g_slist_position() 获取给定节点在链表中的位置(从 0 开始)；
  1
  
  gint g_slist_position(GSList *list, GSList *llink)
  - list - 指向单向链表的指针；
  - llink - 指向单向链表中的一个节点的指针；
  - 返回 llink 指向的节点在单向链表中的位置(从 0 开始)，如果没找到相应节点，则返回 -1；
释放链表
- g_slist_free() 释放链表使用的所有内存，该函数不会释放节点中动态分配的内存；
  1
  
  void g_slist_free(GSList *list)
  - list - 指向单向链表的指针；
  - 该函数仅释放 GSList 占用的内存，并不释放单向链表中各个节点动态申请的内存，如果链表中有动态申请内存，考虑使用 g_slist_free_full() 或手动释放内存；
- g_slist_free_full() 释放链表使用的所有内存，并对每个节点的数据调用指定的销毁函数
  1
  
  void g_slist_free_full(GSList *list, GDestroyNotify free_func)
  - list - 指向单向链表的指针；
  - free_func - 销毁函数，对单向链表中的每个节点数据将调用该函数，可用于释放节点中动态分配的内存；
  - GDestroyNotify 的定义如下：
  1
  
  void (* GDestroyNotify) (gpointer data)
  - 所以在调用 free_func 时会将指向节点数据的指针传递给该函数；
其它
- g_slist_length() 获取单向链表的长度；
  1
  
  guint g_slist_length(GSList *list)
  - list - 指向单向链表的指针；
  - 返回单向链表中节点的数量。
- g_slist_last() 获取单向链表的最后一个节点；
  1
  
  GSList *g_slist_last(GSList *list)
  - list - 指向单向链表的指针；
  - 返回单向链表的最后一个节点的指针，如果单向链表没有节点，则返回 NULL；
- g_slist_concat() 连接两个单向链表；
  1
  
  GSList *g_slist_concat(GSList *list1, GSList *list2)
  - list1 - 指向第 1 个单向链表的指针；
  - list2 - 指向准备连接到第 1 个单向链表后面的单向链表的指针；
  - 返回连接好的单向链表的指针，
- g_slist_reverse() 反转装个单向链表
  1
  
  GSList *g_slist_reverse(GSList *list)
  - list - 指向单向链表的指针；
  - 返回该单向链表的起始指针；

3 如何使用 GSList 实现单向链表

文章的一开始有一个使用标准 C 语言函数库的单向链表的实例，使用 GLib 的 GSList 操作单向链表要容易得多；
下面程序是使用 C 语言，基于 GLib 实现的单向链表，sllist-glib.c(点击文件名下载源程序)

该程序实现的功能与文章开头的程序 sllist-c.c 完全一样，但程序看上去要简洁很多，我们不妨把源程序列在这里

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#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 list
    g_slist_free(list);

    return 0;
}

在这个程序中我们特别要介绍两个宏：GINT_TO_POINTER() 和 GPOINTER_TO_INT()
- 在前面我们介绍过 GSList 这个结构，这也是实现单向链表的关键结构，在这个结构中有一个字段 gpointer data，gpointer 是 GLib 中的一个数据类型，其实就是一个 void *，也就是指针类型；
- 一个指针类型在不同的系统和硬件环境下可能长度不同，但至少是 32 位，所以我们可以在这个指针类型的字段上存储一个数字变量，但是这种转换是挺麻烦的，需要概念清晰，否则可能会使程序崩溃；
- 这样做的好处是，如果一个单向链表的节点数据是一个数字类型，那我们就没必要再去为这个数字申请内存，然后再把这个数字的指针传给 GSList，那么在释放这个 GSList 时也就不需要释放数据占用的内存了；
- 举例说明正常情况下，应该如何在单向链表的一个节点上存储一个数字：
  1 2 3 4 5 6 7 8
  
  GSList item; gint *p = malloc(sizeof(gint)); *p = 10; item.data = p; item.next = NULL; ...... free(item.data); ......
- 为了能够在指针类型上存储一个数字变量，GLib 定义了两个宏：
  1. GINT_TO_POINTER(value) 用于将整数类型变量 value 的值存储到一个指针类型的变量中：gpointer p = GINT_TO_POINTER(10) 将把 10 存放到一个指针类型的变量 p 中，而不是 p 所指向的内存；
  2. GPOINTER_TO_INT(p) 用于将指针类型变量 p 中的值转换为一个整数：gint value = GPOINTER_TO_INT(p) 将把指针类型变量 p 中的值存储到整数类型的变量 value 中

编译：

1

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 单向链表的应用场景

单向链表是一种基础的数据结构，具有节点之间按顺序相连的特性，在特定场景下非常有用，以下是一些典型的应用场景：
1. 动态数据集
  
  当数据量不确定且频繁增删时，单向链表比数组更适用，它可以方便地在任意位置插入或删除节点，而不需要像数组那样移动大量元素；
2. 队列和栈的实现
  
  单向链表常用于实现队列(FIFO)和栈(LIFO)，因为它支持高效的插入和删除操作，尤其在头部或尾部进行操作时性能更好；
3. 浏览历史记录或撤销操作
  
  在一些应用程序中，如浏览器的历史记录，单向链表可以用来保存用户的浏览路径或操作步骤，方便逐步返回或撤销；
4. 分配器管理内存块
  
  操作系统的内存管理器中，单向链表经常被用于管理空闲的内存块(free lists)，通过链表可以快速地找到可用的内存块；
由于单向链表的简单结构，它在上述场景下既灵活又高效，特别是当增删操作频繁时。

5 基于 GLib 的 GSList 实现的 FIFO 队列

FIFO(First Input First Output)队列，也就是先进先出队列，是一种简单的机制，操作一个 FIFO 队列需要队列的头指针和尾指针；
当向 FIFO 队列中加入数据时，数据添加到队列的首指针处，当从队列中取出数据时，要从队列的尾指针处取；
FIFO 队列的重要参数是队列的最大长度，当队列中数据的数量达到队列的最大长度时，则不能再向队列中添加数据；
FIFO 队列的两个重要判断就是判断队列为空(队列中没有数据)或者队列已满(数据数量达到最大长度)；
源程序 queue-glib.c(点击文件名下载源程序) 基于 GLib 的 GSList 实现了一个简单的 FIFO 队列；

该程序实现了 FIFO 队列的两个基本操作：入队操作和出队操作，基于 GLib 使得程序相当的简单；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


#include <stdio.h>
#include <glib.h>

#define QUEUE_MAX_LEN           10

typedef struct {
    GSList *head;               // head pointer of the queue
    GSList *tail;               // tail pointer of the queue
    gint size;                  // size of the queue
    gint max_size;              // max. size of the queue
} Queue;

// Initialize the queue
Queue *queue_init(int maxn) {
    Queue *queue = malloc(sizeof(Queue));
    queue->head = NULL;
    queue->tail = NULL;
    queue->size = 0;
    queue->max_size = maxn;
    return queue;
}

// Enqueue operation(Add a node at the head)
gboolean enqueue(Queue *queue, gint data) {
    if (queue->size >= queue->max_size) {
        return FALSE;
    }
    queue->head = g_slist_prepend(queue->head, GINT_TO_POINTER(data));
    if (queue->tail == NULL) {
        queue->tail = queue->head;
    }
    queue->size++;
    return TRUE;
}

// Dequeue operation(get a node from tail and then delete it)
gint dequeue(Queue *queue) {
    if (queue->tail == NULL) {
        return -1;                  // the queue is empty
    }
    gint data = GPOINTER_TO_INT(queue->tail->data);

    queue->head = g_slist_delete_link(queue->head, queue->tail);
    queue->tail = g_slist_last(queue->head);
    queue->size--;

    return data;
}

int main(int argc, char **argv) {
    guint64 len;
    if (argc >= 2) {
        len = g_ascii_strtoll(argv[1], NULL, 10);           // Convert string to int
        if (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 *queue = queue_init(len);            // Initialize the queue

    guint16 i;
    // append some data to the queue
    for (i = 0; i < (queue->max_size << 1); ++i) {
        if (enqueue(queue, (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 queue
    for (i = 0; i < (queue->max_size << 1); ++i) {
        gint queue_data = dequeue(queue);
        if (queue_data >= 0) {
            printf("Get data %d from the queue.\n", queue_data);
        } else {
            printf("The queue is empty.\n");
            break;
        }
    }

    free(queue);

    return 0;
}

可以看出，用 GLib 实现的 FIFO 队列非常简洁；

编译：

1

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

donation

文章目录

1 单向链表及其实现

2 GLib 中单向链表结构 GSList

3 如何使用 GSList 实现单向链表

4 单向链表的应用场景

5 基于 GLib 的 GSList 实现的 FIFO 队列