链表

链表

链表（Linked List）：一种线性表数据结构，通过一组任意可连续或不连续的存储单元，存储同类型数据。

简而言之，链表 是线性表的链式存储实现。

链表的优缺点：

  • 优点：链表无需预先分配存储空间，按需动态申请，能够有效避免空间浪费；在插入、删除等操作上，链表通常比数组更高效，尤其是在需要频繁修改数据结构时表现突出。
  • 缺点：链表除了存储数据本身外，还需额外存储指针信息，因此整体空间开销大于数组；同时，链表不支持随机访问，查找元素时需要从头遍历，效率较低。

单向链表

介绍

单向链表：是一种基本的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。在物理存储上，节点可连续也可能不连续，但逻辑上它们是顺序连接的。单向链表的操作包括创建、插入、删除、查找和销毁等。

优势：

  • 动态大小、按需分配
  • 头部插入/删除为 O(1)
  • 不需要连续内存

劣势：

  • 随机访问为 O(n)
  • 额外指针开销
  • 遍历删除需维护前驱

单向链表的结构如下图：链表通过指针将一组任意的存储单元串联起来。每个数据元素及其所在的存储单元构成一个「链节点」。为了将所有节点连接成链，每个链节点除了存放数据元素本身，还需要额外存储一个指向其直接后继节点的指针，称为后继指针next。

image-20251012174353005

链表与结点结构体定义

1
2
3
4
5
6
7
8
9
10
11
/*结点定义*/
typedef struct ListNode {
    int value;               /* 节点数据 */
    struct ListNode* next;   /* 指向下一个节点 */
} ListNode;

/*链表定义*/
typedef struct List {
    ListNode* head;          /* 头指针 */
    size_t    size;          /* 当前元素个数 */
} List;

关键点：

  • head == NULL 表示空链表。
  • size 便于 O(1) 获取长度，也用于边界检查。

API设计与实现思路

按功能分组(本实现以int为元素类型，默认线程不安全)

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
/* 基础管理 */
void list_init(List* list);
void list_destroy(List* list);     /* 等价于clear后释放资源（这里仅清空节点） */
void list_clear(List* list);
size_t list_size(const List* list);
bool list_empty(const List* list);

/* 末端与首端操作 */
bool list_push_front(List* list, int value);
bool list_push_back(List* list, int value);
bool list_pop_front(List* list, int* out_value);
bool list_pop_back(List* list, int* out_value);

/* 位置与值操作 */
bool list_insert(List* list, size_t index, int value);         /* 0..size 有效 */
bool list_remove_at(List* list, size_t index, int* out_value); /* 0..size-1 有效 */
size_t list_remove_value(List* list, int value, bool remove_all);

/* 查询与遍历 */
long list_find_first(const List* list, int value); /* 返回索引，未找到返回-1 */
void list_foreach(const List* list, void (*fn)(int value, void* user), void* user);

/* 其他实用 */
void list_reverse(List* list);
void list_print(const List* list);

术语：cur 当前节点，prev 前驱节点，nxt 保存的后继节点；“重连指针”指修改 next 指向以保持链表连通。

API 原型 作用 核心实现思路/步骤 时间复杂度 边界/注意点
create_node static ListNode* create_node(int value) 内部工具：创建新节点 malloc 分配节点；赋值 value；next 置 NULL；返回指针（失败返回 NULL） O(1) 仅内部使用；检查分配失败
list_size size_t list_size(const List* list) 获取链表元素个数 返回 list->size；若 list 为 NULL 返回 0 O(1) 只读，不修改结构
list_empty bool list_empty(const List* list) 判断链表是否为空 返回 list_size(list) == 0 O(1) list 为 NULL 视为空
list_init void list_init(List* list) 初始化链表对象 将 head 置 NULL，size 置 0 O(1) 传入指针不能为空；栈上对象使用前必须 init
list_clear void list_clear(List* list) 清空所有节点 从 head 线性遍历，逐个 free；最后 head=NULL, size=0 O(n) 可多次调用；对空表安全
list_add_front bool list_add_front(List* list, int value) 头插 create_node；node->next = head；head = node；size++ O(1) list==NULL 或分配失败返回 false
list_add_back bool list_add_back(List* list, int value) 尾插 create_node；若空表 head=node；否则从 head 遍历到尾，尾->next=node；size++ O(n) 单向链表无 tail 时需要遍历
list_delete_front bool list_delete_front(List* list, int* out_value) 头删 判空；保存 head 值到 out_value（可选）；head=head->next；free(旧头)；size– O(1) 空表返回 false
list_delete_back bool list_delete_back(List* list, int* out_value) 尾删 判空；用 previous/current 遍历到尾；写回 out_value；若前驱为 NULL 表示单节点，head=NULL；否则 previous->next=NULL；free(尾)；size– O(n) 仅一个节点时要特殊处理
list_insert bool list_insert(List* list, size_t index, int value) 指定位置插入 边界：index>size 返回 false；index=0 调用头插；index=size 调用尾插；否则遍历到 index-1，node->next=cur->next；cur->next=node；size++ O(n) 合法范围 0..size（含 size）
list_remove_at bool list_remove_at(List* list, size_t index, int* out_value) 指定位置删除 越界：index>=size 返回 false；index0 调头删；index=size-1 调尾删；否则遍历到 index-1，目标=cur->next；写回 out_value；cur->next=目标->next；free(目标)；size– O(n) 合法范围 0..size-1
list_remove_value size_t list_remove_value(List* list, int value, bool remove_all) 按值删除（删一个或删全部） 先处理连续头部命中：移动 head、free、size–、计数++，若不删全则返回；再从头遍历，用 current->next 作为候选，命中则跳过并 free，计数++，若不删全则 break，否则继续 O(n) 返回删除数量；空表返回 0；避免变量名使用 delete
list_find_first long list_find_first(const List* list, int value) 查找首个等于 value 的索引 从 head 线性扫描，命中返回索引（从 0 开始）；未找到返回 -1 O(n) 返回类型为 long；list==NULL 返回 -1
list_foreach void list_foreach(const List* list, void (fn)(int, void), void* user) 遍历回调 逐节点调用 fn(current->value, user) O(n) fn 不能为空；回调中若修改链表需谨慎
list_reverse void list_reverse(List* list) 原地反转 迭代三指针：previous=NULL, current=head；循环内保存 next=current->next；current->next=previous；previous=current；current=next；结束后 head=previous O(n)，额外 O(1) 对空表/单节点安全
list_print void list_print(const List* list) 打印链表 以 [a, b, c] (size=n) 形式遍历输出 O(n) 调试用途；list==NULL 打印空

单向链表源码实现

github仓库：https://github.com/keqiudi/LinkList/tree/master/single_linklist

list.h

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
/**
 * @file    list.h
 * @brief   基于单向链表（int 元素）的通用接口声明
 * @details 提供链表的初始化、销毁、增删改查、遍历与反转等基础操作；默认线程不安全。
 *          若需在多线程环境中使用，请在调用层加锁。
 *
 * @note    复杂度（单向链表）：
 *          - 头部插入/删除：O(1)
 *          - 尾部插入/删除、按位访问、按值删除：O(n)
 */

#ifndef LIST_H
#define LIST_H

#include <stddef.h>  /* size_t */
#include <stdbool.h> /* bool   */

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @brief 链表节点
 */
typedef struct ListNode {
    int value;               /**< 节点存储的数据元素 */
    struct ListNode* next;   /**< 指向下一个节点的指针 */
} ListNode;

/**
 * @brief 链表头结点（容器）
 */
typedef struct List {
    ListNode* head;  /**< 头指针 */
    size_t    size;  /**< 当前元素个数 */
} List;

/* ======================= 基础管理 ======================= */

/**
 * @brief  初始化链表（将指针置空，大小置零）
 * @param  list 指向链表对象
 */
void list_init(List* list);

/**
 * @brief  销毁链表（等价于清空全部节点）
 * @param  list 指向链表对象
 * @note   本实现不另持外部资源，等价于 list_clear
 */
void list_destroy(List* list);

/**
 * @brief  清空链表中的全部节点
 * @param  list 指向链表对象
 */
void list_clear(List* list);

/**
 * @brief  获取链表大小
 * @param  list 指向链表对象（可为 NULL）
 * @return 元素个数；若 list 为 NULL 返回 0
 */
size_t list_size(const List* list);

/**
 * @brief  判断链表是否为空
 * @param  list 指向链表对象
 * @return 为空返回 true，否则返回 false
 */
bool list_empty(const List* list);

/* =================== 末端与首端操作 =================== */

/**
 * @brief  头插：在表头插入一个元素
 * @param  list  链表指针
 * @param  value 待插入的值
 * @return 成功返回 true，分配失败返回 false
 * @complexity O(1)
 */
bool list_add_front(List* list, int value);

/**
 * @brief  尾插：在表尾插入一个元素
 * @param  list  链表指针
 * @param  value 待插入的值
 * @return 成功返回 true，分配失败返回 false
 * @complexity O(n)（单向链表需遍历到尾部）
 */
bool list_add_back(List* list, int value);

/**
 * @brief  头删：删除表头元素
 * @param  list      链表指针
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；若链表为空返回 false
 * @complexity O(1)
 */
bool list_delete_front(List* list, int* out_value);

/**
 * @brief  尾删：删除表尾元素
 * @param  list      链表指针
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；若链表为空返回 false
 * @complexity O(n)
 */
bool list_delete_back(List* list, int* out_value);

/* =================== 位置与值操作 =================== */

/**
 * @brief  按位置插入元素
 * @param  list  链表指针
 * @param  index 插入位置（合法范围 0..size），0 等价于头插，size 等价于尾插
 * @param  value 待插入的值
 * @return 成功返回 true；index 越界或分配失败返回 false
 * @complexity O(n)
 */
bool list_insert(List* list, size_t index, int value);

/**
 * @brief  按位置删除元素
 * @param  list      链表指针
 * @param  index     删除位置（合法范围 0..size-1）
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；越界或空表返回 false
 * @complexity O(n)
 */
bool list_remove_at(List* list, size_t index, int* out_value);

/**
 * @brief  按值删除元素（可删除首个或全部匹配项）
 * @param  list       链表指针
 * @param  value      要删除的目标值
 * @param  remove_all true 删除全部匹配项；false 仅删除首个
 * @return 实际删除的元素个数
 * @complexity O(n)
 */
size_t list_remove_value(List* list, int value, bool remove_all);

/* =================== 查询与遍历 =================== */

/**
 * @brief  查找首个等于 value 的元素位置
 * @param  list  链表指针
 * @param  value 目标值
 * @return 索引（0 开始）；未找到返回 -1
 * @complexity O(n)
 */
long list_find_first(const List* list, int value);

/**
 * @brief  遍历链表，对每个元素调用回调
 * @param  list 链表指针
 * @param  fn   回调函数，签名为 void (*)(int value, void* user)
 * @param  user 透传给回调的用户参数
 * @note   回调内若修改链表结构需格外小心，避免失效遍历指针
 */
void list_foreach(const List* list, void (*fn)(int value, void* user), void* user);

/* =================== 其他常用函数 =================== */

/**
 * @brief  原地反转链表
 * @param  list 链表指针
 * @complexity O(n)，额外空间 O(1)
 */
void list_reverse(List* list);

/**
 * @brief  打印链表内容（调试用途）
 * @param  list 链表指针
 * @note   实现依赖 stdio；生产环境可替换为自定义输出
 */
void list_print(const List* list);

#ifdef __cplusplus
}
#endif

#endif /* LIST_H */

list.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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
//
// Created by keqiu on 25-10-13.
//
#include "list.h"
#include <stdio.h>
#include <stdlib.h>


static ListNode* create_node(int value)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL)
    {
        return NULL;
    }
    node->value = value;
    node->next = NULL;

    return node;
}

void list_init(List* list)
{
    if (list == NULL){
        return;
    }
    list->head = NULL;
    list->size = 0;
}

void list_clear(List* list)
{
    if (list == NULL){
        return;
    }
    ListNode* current = list->head;
    while (current)
    {
        ListNode* next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
    list->size = 0;
}


bool list_add_front(List* list,int value)
{
    if (list == NULL){
        return false;
    }

    ListNode* node = create_node(value);
    if (node == NULL){
        return false;
    }

    node->next = list->head;
    list->head = node;
    list->size++;
    return true;
}

bool list_add_back(List* list,int value)
{
    // 链表不为空
    if (list == NULL){
        return false;
    }
    ListNode* node = create_node(value);
    //节点创建失败
    if (node == NULL){
        return false;
    }
    //头节点为空
    if (list->head == NULL){
        list->head = node;
    }
    else
    {
        ListNode* current = list->head;
        while (current->next)
        {
            current = current->next;
        }
        current->next = node;
    }
    list->size++;
    return true;
}

bool list_delete_front(List* list, int* out_value)
{
    if (list == NULL || list->head == NULL){
        return false;
    }

    ListNode* head = list->head;
    if (out_value != NULL)
    {
        *out_value = head->value;
    }
    list->head = head->next;
    free(head);
    list->size--;
    return true;
}

bool list_delete_back(List* list, int* out_value)
{
    if (list == NULL || list->head == NULL){
        return false;
    }

    ListNode*  current = list->head;
    ListNode*  previous = NULL;
    while (current->next)
    {
        previous = current;
        current = current->next;
    }

    if (out_value != NULL){
        *out_value = current->value;
    }

    if (previous == NULL)
    {
        list->head = NULL; //只有头节点的情况
    }
    else
    {
        previous->next = NULL;
    }

    free(current);
    list->size--;
    return true;

}

bool list_insert(List* list, size_t index, int value)
{
    if (list == NULL){
        return false;
    }

    if (index > list->size){ /*只能插到0~size处*/
        return false;
    }

    if (index == 0){
        return list_add_front(list,value); // index为0直接在头部插入结点
    }
    if (index == list->size){
        return list_add_back(list,value); // index为size直接在尾部插入结点
    }

    ListNode* node = create_node(value);
    if (node == NULL){
        return false;
    }

    ListNode* current = list->head;
    for (int i=0;i<index-1;i++)
    {
        current = current->next;
    }
    node->next = current->next;
    current->next = node;
    list->size++;
    return true;
}

bool list_remove_at(List* list,size_t index,int* out_value)
{
    if (list == NULL || index >= list->size){  // index取值是0~size-1
        return false;
    }

    if (index == 0){
        return list_delete_front(list,out_value); // index=0 直接删除最前面的结点
    }
    if (index == list->size-1){
        return list_delete_back(list,out_value);
    }

    ListNode* current = list->head;
    for (int i=0;i<index-1;i++)
    {
        current = current->next; // 找到index处的前一个结点
    }

    ListNode* target = current->next; //index的结点
    if (out_value != NULL)
    {
        *out_value = target->value;
    }

    current->next = target->next;
    free(target);
    list->size--;
    return true;
}

size_t list_remove_value(List* list, int value, bool remove_all)
{
    if (list == NULL)
    {
        return 0;
    }

    size_t removed_num = 0; //移除结点数

    /* 处理头部连续匹配的情况 */
    while (list->head && list->head->value == value)
    {
        ListNode* head = list->head;
        list->head = head->next;
        free(head);
        list->size--;
        removed_num++;
        if (!remove_all)
        {
            return removed_num;
        }
    }

    /* 处理非头部的情况 */
    ListNode* current = list->head;
    while (current && current->next)
    {
        if (current->next->value == value)
        {
            ListNode* delete = current->next;
            current->next = delete->next;
            free(delete);
            list->size--;
            removed_num++;
            if (!remove_all)
            {
                break;
            }
        }
        else
        {
            current = current->next;
        }

    }

    return removed_num;
}

long list_find_first(const List* list, int value)
{
    if (list == NULL)
    {
        return -1;
    }

    int node_index = 0;
    ListNode* current = list->head;

    while (current)
    {
        if (current->value == value)
        {
            return node_index;
        }

        current = current->next;
        node_index++;
    }

    return -1;
}

void list_foreach(const List* list, void (*fn)(int value, void* user), void* user) {
    if (list == NULL || !fn)
    {
        return;
    }
    const ListNode* current = list->head;
    while (current)
    {
        fn(current->value, user);
        current = current->next;
    }
}

void list_reverse(List* list)
{
    if (list == NULL)
    {
        return;
    }

    ListNode* current = list->head;
    ListNode* previous = NULL;
    while (current)
    {
        ListNode* next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    list->head = previous;
}

void list_print(const List* list) {
    if (list ==NULL)
    {
        printf("[]\n"); return;
    }

    const ListNode* cur = list->head;
    printf("[");
    while (cur) {
        printf("%d", cur->value);
        if (cur->next) printf(", ");
        cur = cur->next;
    }
    printf("] (size=%zu)\n", list->size);
}


size_t list_size(const List* list)
{
    return list ? list->size:0;
}

void list_destroy(List* list)
{
    list_clear(list);
}

bool list_empty(const List* list)
{
    return list ? (list->size == 0) : true;
}

测试代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "list.h"
#include <stdio.h>
#include <assert.h>

/* 用于 foreach 的求和回调 */
static void sum_cb(int v, void* user) {
    int* acc = (int*)user;
    *acc += v;
}

int main(void) {
    List ls;
    list_init(&ls);

    /* 空表状态 */
    assert(list_empty(&ls) == true);
    assert(list_size(&ls) == 0);
    int tmp;
    assert(list_delete_front(&ls, &tmp) == false);
    assert(list_delete_back(&ls, &tmp) == false);
    assert(list_remove_at(&ls, 0, &tmp) == false);
    assert(list_remove_value(&ls, 123, true) == 0);

    /* 基本插入（头/尾） */
    assert(list_add_back(&ls, 1) == true);
    assert(list_add_back(&ls, 2) == true);
    assert(list_add_back(&ls, 3) == true);
    list_print(&ls);                       /* [1,2,3] */
    assert(list_size(&ls) == 3);
    assert(list_empty(&ls) == false);

    assert(list_add_front(&ls, 0) == true);/* [0,1,2,3] */
    list_print(&ls);
    assert(list_size(&ls) == 4);

    /* 指定位置插入：中间与尾部（index==size） */
    assert(list_insert(&ls, 2, 99) == true);            /* [0,1,99,2,3] */
    list_print(&ls);
    assert(list_insert(&ls, list_size(&ls), 42) == true); /* 尾部插入 => [...,3,42] */
    list_print(&ls);

    /* 查找 */
    long idx = list_find_first(&ls, 99);
    printf("find 99 at index = %ld\n", idx);
    assert(idx == 2);
    assert(list_find_first(&ls, -7) == -1);

    /* 按位删除：中间和尾部 */
    int val = 0;
    assert(list_remove_at(&ls, 2, &val) == true);       /* 删除 99 */
    assert(val == 99);
    list_print(&ls);

    assert(list_remove_at(&ls, list_size(&ls) - 1, &val) == true); /* 删尾 42 */
    assert(val == 42);
    list_print(&ls);

    /* 按值删除：先只删一个，再删全部 */
    assert(list_add_back(&ls, 2) == true);
    assert(list_add_back(&ls, 2) == true);              /* [...,2,2] */
    list_print(&ls);

    size_t removed = list_remove_value(&ls, 2, false);  /* 只删第一个 2 */
    printf("removed one 2 count=%zu\n", removed);
    assert(removed == 1);
    list_print(&ls);

    removed = list_remove_value(&ls, 2, true);          /* 删剩余所有 2 */
    printf("removed all 2 count=%zu\n", removed);
    assert(removed >= 1);
    list_print(&ls);

    /* 头删/尾删 */
    assert(list_delete_front(&ls, &val) == true);
    printf("delete_front=%d\n", val);
    list_print(&ls);

    assert(list_delete_back(&ls, &val) == true);
    printf("delete_back=%d\n", val);
    list_print(&ls);

    /* 反转：对多个元素、对单元素、对空表都应安全 */
    assert(list_add_back(&ls, 10) == true);
    assert(list_add_back(&ls, 20) == true);
    assert(list_add_back(&ls, 30) == true);
    list_print(&ls);

    list_reverse(&ls);
    printf("reversed: ");
    list_print(&ls);

    list_clear(&ls);
    list_reverse(&ls); /* 空表反转不应崩溃 */
    assert(list_empty(&ls));

    assert(list_add_back(&ls, 7) == true);
    list_reverse(&ls); /* 单元素反转不应改变内容 */
    assert(list_size(&ls) == 1);
    list_print(&ls);

    /* 遍历（foreach） */
    int sum = 0;
    list_foreach(&ls, sum_cb, &sum);
    printf("sum=%d\n", sum);
    assert(sum == 7);

    /* 清空与销毁 */
    list_clear(&ls);
    printf("cleared: ");
    list_print(&ls);
    assert(list_empty(&ls));
    list_destroy(&ls);

    printf("All tests passed!\n");
    return 0;
}

输出结果：

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
C:\Users\keqiu\myProjects\CLionProjects\C++\test\cmake-build-debug-mingw\test.exe
    
[1, 2, 3] (size=3)
[0, 1, 2, 3] (size=4)
[0, 1, 99, 2, 3] (size=5)
[0, 1, 99, 2, 3, 42] (size=6)
    
find 99 at index = 2
[0, 1, 2, 3, 42] (size=5)
[0, 1, 2, 3] (size=4)
[0, 1, 2, 3, 2, 2] (size=6)
removed one 2 count=1
[0, 1, 3, 2, 2] (size=5)
removed all 2 count=2
[0, 1, 3] (size=3)
delete_front=0
[1, 3] (size=2)
delete_back=3
[1] (size=1)
[1, 10, 20, 30] (size=4)
reversed: [30, 20, 10, 1] (size=4)
[7] (size=1)
sum=7
cleared: [] (size=0)
All tests passed!

双向链表

介绍

双向链表（Doubly Linked List）：链表的一种，也称为双链表。每个节点包含两条指针：后继指针 next 指向直接后继节点，前驱指针 prev 指向直接前驱节点；容器常维护首尾指针 head 与 tail，支持从两端高效操作与双向遍历。

  • 双向链表的特点：可以从任意节点高效地访问其前驱和后继节点，支持双向遍历，插入和删除操作更加灵活。

image-20251012175234596

链表结构体定义

双向链表与单向链表的区别就是：

1.每个结点结构体中新增一个前驱指针prev，指向上一个结点

2.在List结构体中新增一个tail尾指针，使尾插/尾删变为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 结点定义 */
typedef struct ListNode {
    int value;               /* 节点数据 */
    struct ListNode* next;   /* 指向后继 */
    struct ListNode* prev;   /* 指向前驱（双向新增） */
} ListNode;

/* 容器定义 */
typedef struct List {
    ListNode* head;          /* 头指针 */
    ListNode* tail;          /* 尾指针（双向新增） */
    size_t    size;          /* 当前元素个数 */
} List;

API设计与实现思路

双向链表的api设计与上方单向链表相同，这里具体说明双向链表哪些API与单向链表实现不同

与单向链表实现不同的 API 原型 作用 核心实现思路/步骤（与单向差异） 时间复杂度（双向 vs 单向） 边界/注意点
create_node static ListNode* create_node(int value) 内部工具：创建新节点 在单向基础上，新增初始化 prev=NULL O(1) / O(1) 失败返回 NULL；仅内部使用
list_clear void list_clear(List* list) 清空所有节点 同样逐个 free；额外将 tail 也置为 NULL O(n) / O(n) 清空后需满足 headtailNULL
list_add_front bool list_add_front(List* list, int value) 头插 node->next=head；若原表非空，head->prev=node；否则 tail=node；更新 head=node O(1) / O(1) 维护端点与双向指针 head->prev==NULL
list_add_back bool list_add_back(List* list, int value) 尾插 node->prev=tail；若原表非空，tail->next=node；否则 head=node；更新 tail=node O(1) / O(n) 借助 tail 将尾插从 O(n) 降为 O(1)
list_delete_front bool list_delete_front(List* list, int* out_value) 头删 head=head->next；若新 head 非空则 head->prev=NULL；否则 tail=NULL；free 旧头 O(1) / O(1) 删到空表需同步置空 tail
list_delete_back bool list_delete_back(List* list, int* out_value) 尾删 tail=tail->prev；若新 tail 非空则 tail->next=NULL；否则 head=NULL；free 旧尾 O(1) / O(n) 借助 prev 将尾删从 O(n) 降为 O(1)
list_insert bool list_insert(List* list, size_t index, int value) 指定位置插入 越界：index>size false；index=0 头插；index=size 尾插；否则在 index 位置前插：node->next=cur；node->prev=cur->prev；cur->prev->next=node；cur->prev=node O(min(i,n−i)) / O(n) 可从近端起步（head/tail）降低步数
list_remove_at bool list_remove_at(List* list, size_t index, int* out_value) 指定位置删除 越界：index>=size false；index=0 头删；index=size−1 尾删；否则 target->prev->next=target->next；target->next->prev=target->prev；free(target) O(min(i,n−i)) / O(n) 同时重连前驱与后继
list_remove_value size_t list_remove_value(List* list, int value, bool remove_all) 按值删除（删一/删全） 线性扫描，命中时同时维护两向链接：若有前驱则前驱->next=cur->next 否则 head=cur->next；若有后继则后继->prev=cur->prev 否则 tail=cur->prev；free(cur) O(n) / O(n) 一次处理头/尾/中间/唯一节点四种情况
list_reverse void list_reverse(List* list) 原地反转 逐节点交换 next/prev：nxt=cur->next；cur->next=cur->prev；cur->prev=nxt；cur=nxt；结束后交换 head 与 tail O(n)/O(n)，额外 O(1) 反转逻辑与单向“三指针法”不同
list_print void list_print(const List* list) 打印链表 从 head 到 tail 遍历，常用 “a <-> b <-> c” 体现双向 O(n) / O(n) 调试用途；仅显示风格差异

双向链表源码实现

github仓库：https://github.com/keqiudi/LinkList/tree/master/double_linklist

doublelist.h

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/**
 * @file    doublelist.h
 * @brief   基于双向链表（int 元素）的通用接口声明
 * @details 提供链表的初始化、销毁、首尾/按位插入删除、按值删除、查找、遍历、反转、打印等功能。
 *          采用 head + tail 结构，首尾操作为 O(1)；按位操作为 O(min(i, n-i))（可从近端起步）。
 *          默认线程不安全，若需在多线程环境中使用，请在调用层加锁。
 *
 * @note    复杂度（双向链表）：
 *          - 头部/尾部 插入与删除：O(1)
 *          - 按位插入/删除：O(min(i, n-i))
 *          - 按值删除、查找、遍历：O(n)
 */

#ifndef DOUBLELIST_H
#define DOUBLELIST_H

#include <stddef.h>  /* size_t */
#include <stdbool.h> /* bool   */

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @brief 链表节点
 */
typedef struct ListNode {
    int value;                /**< 节点存储的数据元素 */
    struct ListNode* next;    /**< 指向后继节点 */
    struct ListNode* prev;    /**< 指向前驱节点 */
} ListNode;

/**
 * @brief 链表容器
 */
typedef struct List {
    ListNode* head;           /**< 头指针；空表为 NULL */
    ListNode* tail;           /**< 尾指针；空表为 NULL */
    size_t    size;           /**< 当前元素个数 */
} List;

/* ======================= 基础管理 ======================= */

/**
 * @brief  初始化链表（将指针置空，大小置零）
 * @param  list 指向链表对象
 */
void list_init(List* list);

/**
 * @brief  销毁链表（等价于清空全部节点）
 * @param  list 指向链表对象
 * @note   本实现不另持外部资源，等价于 list_clear
 */
void list_destroy(List* list);

/**
 * @brief  清空链表中的全部节点
 * @param  list 指向链表对象
 */
void list_clear(List* list);

/**
 * @brief  获取链表大小
 * @param  list 指向链表对象（可为 NULL）
 * @return 元素个数；若 list 为 NULL 返回 0
 */
size_t list_size(const List* list);

/**
 * @brief  判断链表是否为空
 * @param  list 指向链表对象
 * @return 为空返回 true，否则返回 false
 */
bool list_empty(const List* list);

/* =================== 末端与首端操作 =================== */

/**
 * @brief  头插：在表头插入一个元素
 * @param  list  链表指针
 * @param  value 待插入的值
 * @return 成功返回 true，分配失败返回 false
 * @complexity O(1)
 */
bool list_add_front(List* list, int value);

/**
 * @brief  尾插：在表尾插入一个元素
 * @param  list  链表指针
 * @param  value 待插入的值
 * @return 成功返回 true，分配失败返回 false
 * @complexity O(1)
 */
bool list_add_back(List* list, int value);

/**
 * @brief  头删：删除表头元素
 * @param  list      链表指针
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；若链表为空返回 false
 * @complexity O(1)
 */
bool list_delete_front(List* list, int* out_value);

/**
 * @brief  尾删：删除表尾元素
 * @param  list      链表指针
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；若链表为空返回 false
 * @complexity O(1)
 */
bool list_delete_back(List* list, int* out_value);

/* =================== 位置与值操作 =================== */

/**
 * @brief  按位置插入元素
 * @param  list  链表指针
 * @param  index 插入位置（合法范围 0..size），0 等价于头插，size 等价于尾插
 * @param  value 待插入的值
 * @return 成功返回 true；index 越界或分配失败返回 false
 * @complexity O(min(index, size-index))
 */
bool list_insert(List* list, size_t index, int value);

/**
 * @brief  按位置删除元素
 * @param  list      链表指针
 * @param  index     删除位置（合法范围 0..size-1）
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；越界或空表返回 false
 * @complexity O(min(index, size-index))
 */
bool list_remove_at(List* list, size_t index, int* out_value);

/**
 * @brief  按值删除元素（可删除首个或全部匹配项）
 * @param  list       链表指针
 * @param  value      要删除的目标值
 * @param  remove_all true 删除全部匹配项；false 仅删除首个
 * @return 实际删除的元素个数
 * @complexity O(n)
 */
size_t list_remove_value(List* list, int value, bool remove_all);

/* =================== 查询与遍历 =================== */

/**
 * @brief  查找首个等于 value 的元素位置
 * @param  list  链表指针
 * @param  value 目标值
 * @return 索引（0 开始）；未找到返回 -1
 * @complexity O(n)
 */
long list_find_first(const List* list, int value);

/**
 * @brief  遍历链表，对每个元素调用回调
 * @param  list 链表指针
 * @param  fn   回调函数，签名为 void (*)(int value, void* user)
 * @param  user 透传给回调的用户参数
 * @note   回调内若修改链表结构需格外小心，避免失效遍历指针
 */
void list_foreach(const List* list, void (*fn)(int value, void* user), void* user);

/* =================== 其他常用函数 =================== */

/**
 * @brief  原地反转链表
 * @param  list 链表指针
 * @complexity O(n)，额外空间 O(1)
 */
void list_reverse(List* list);

/**
 * @brief  打印链表内容（调试用途）
 * @param  list 链表指针
 * @note   实现依赖 stdio；生产环境可替换为自定义输出
 */
void list_print(const List* list);

#ifdef __cplusplus
}
#endif

#endif /* DOUBLELIST_H */

doublelist.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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
#include "doublelist.h"
#include <stdio.h>
#include <stdlib.h>

static ListNode* create_node(int value)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL)
    {
        return NULL;
    }
    node->value = value;
    node->next = NULL;
    node->prev = NULL; // 双向链表新增
    return node;
}

void list_init(List* list)
{
    if (list == NULL){
        return;
    }
    list->head = NULL;
    list->tail = NULL; // 双向链表新增
    list->size = 0;
}

void list_clear(List* list)
{
    if (list == NULL){
        return;
    }
    ListNode* current = list->head;
    while (current)
    {
        ListNode* next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
    list->tail = NULL; // 双向链表新增
    list->size = 0;
}

void list_destroy(List* list)
{
    list_clear(list);
}

size_t list_size(const List* list)
{
    return list ? list->size:0;
}

bool list_empty(const List* list)
{
    return list ? (list->size == 0) : true;
}


bool list_add_front(List* list,int value)
{
    if (list == NULL){
        return false;
    }

    ListNode* node = create_node(value);
    if (node == NULL){
        return false;
    }

    node->next = list->head; // 新插入结点的后继指向原head结点

    if (list->head == NULL)
    {
        list->tail = node; // 如果原本链表结点数为0,直接将该结点作为tail
    }
    else
    {
        list->head->prev = node; // 双向链表新增: 原head结点的前驱指向新插入的结点
    }

    list->head = node; //更新头结点
    list->size++;
    return true;
}

bool list_add_back(List* list,int value)
{
    // 链表不为空
    if (list == NULL){
        return false;
    }
    ListNode* node = create_node(value);
    //节点创建失败
    if (node == NULL){
        return false;
    }

    node->prev = list->tail; // 双向链表新增: 新插入结点的前驱指向原尾结点
    if (list->tail == NULL)
    {
        list->head = node; //空表处理, 让head也指向该结点
    }
    else
    {
        list->tail->next = node; //尾结点不为空，直接更尾插结点
    }

    list->tail = node;
    list->size++;
    return true;
}

bool list_delete_front(List* list, int* out_value)
{
    if (list == NULL || list->head == NULL){
        return false;
    }

    ListNode* head = list->head; // 获取头结点指针
    if (out_value != NULL)
    {
        *out_value = head->value;
    }

    list->head = head->next; // 更新头结点
    if (list->head == NULL)
    {
        list->tail = NULL; // 如果更新头结点后链表空了，让head == tail
    }
    else
    {
        list->head->prev = NULL; //  维护新头的前驱为空
    }

    free(head);
    list->size--;
    return true;
}

bool list_delete_back(List* list, int* out_value)
{
    if (list == NULL || list->head == NULL){
        return false;
    }

    ListNode* tail = list->tail; // 获取尾结点指针
    if (out_value != NULL)
    {
        *out_value = tail->value;
    }

    list->tail = tail->prev; // 更新尾结点
    if (list->tail == NULL)
    {
        list->head = NULL; // 如果更新尾结点后链表空了，让head == tail
    }
    else
    {
        list->tail->next = NULL; // 维护新尾结点的后继为空
    }

    free(tail);
    list->size--;
    return true;

}

/* 根据index所处位置，分别选择从哪端开始遍历 */
static ListNode* list_node_at(List* list, size_t index)
{
    if (list == NULL || index >= list->size) // index只能到size-1处
    {
        return NULL;
    }

    if (index <= list->size/2)
    {
        ListNode* current = list->head; // 索引在前半部分直接从头结点开始
        for (size_t i = 0;i<index;i++)
        {
            current = current->next;
        }
        return current;
    }
    else
    {
        ListNode* current = list->tail; // 索引在后半部分直接从尾结点开始
        for (size_t i = list->size-1 ;i>index;i--)
        {
            current = current->prev;
        }
        return current;
    }

}

bool list_insert(List* list, size_t index, int value)
{
    if (list == NULL || index > list->size){
        return false;
    }

    if (index == 0){
        return list_add_front(list,value); // index为0代表头插
    }
    if (index == list->size){
        return list_add_back(list,value); //  index为list->size代表尾插
    }

    ListNode* current = list_node_at(list,index); // 获取index位置处结点
    if (current == NULL)
    {
        return false;
    }

    ListNode* node = create_node(value);
    if (node == NULL){
        return false;
    }

    node->next = current;       // 插入结点的后继指向处理
    node->prev = current->prev; // 插入结点的前驱指向处理
    current->prev->next = node; // 前驱结点的后继指向插入结点
    current->prev = node;       // 当前结点的前驱指向插入结点

    list->size++;
    return true;
}

bool list_remove_at(List* list,size_t index,int* out_value)
{
    if (list == NULL || index >= list->size){  // index取值是0~size-1
        return false;
    }

    if (index == 0){
        return list_delete_front(list,out_value); // index=0 直接删除最前面的结点
    }
    if (index == list->size-1){
        return list_delete_back(list,out_value); // index=size-1 直接删除尾部的结点
    }

    ListNode* target = list_node_at(list,index); // 获得index处的结点
    if (target == NULL)
    {
        return false;
    }
    if (out_value != NULL)
    {
        *out_value = target->value;
    }

    target->prev->next = target->next; // 处理前驱结点的后继指向
    target->next->prev = target->prev; // 处理后继结点的前驱指向
    free(target);
    list->size--;
    return true;
}

size_t list_remove_value(List* list, int value, bool remove_all)
{
    if (list == NULL)
    {
        return 0;
    }

    size_t removed_num = 0; //移除结点数

    ListNode* current = list->head;

    while (current)
    {
        if (current->value == value)
        {
            ListNode* delete = current;  // 当前结点为需要删除的结点
            ListNode* delete_next = current->next;

            if (delete->prev == NULL) // 头结点判定
            {
                list->head = delete->next; // 头结点的处理
            }
            else
            {
                delete->prev->next = delete->next; // 非头结点的前驱结点处理
            }

            if (delete->next == NULL) //尾结点判定
            {
                list->tail = delete->prev; //尾结点处理
            }
            else
            {
                delete->next->prev = delete->prev;  // 非尾结点的后继结点处理
            }

            free(delete);
            list->size--;
            removed_num++;
            if (!remove_all)
            {
                break; // 没有指定移除所以直接退出
            }
            current = delete_next; // 移动到下一个结点
        }
        else
        {
            current = current->next;
        }
    }

    return removed_num;
}

long list_find_first(const List* list, int value)
{
    if (list == NULL)
    {
        return -1;
    }

    int node_index = 0;
    ListNode* current = list->head;

    while (current)
    {
        if (current->value == value)
        {
            return node_index;
        }

        current = current->next;
        node_index++;
    }

    return -1;
}

void list_foreach(const List* list, void (*fn)(int value, void* user), void* user) {
    if (list == NULL || !fn)
    {
        return;
    }
    const ListNode* current = list->head;
    while (current)
    {
        fn(current->value, user);
        current = current->next;
    }
}

void list_reverse(List* list)
{
    if (list == NULL)
    {
        return;
    }

    ListNode* current = list->head;
    while (current)
    {
        ListNode* next = current->next; // 保存下一个结点
        current->next = current->prev; // 反转时下一个结点应该指向上一个结点位置
        current->prev = next; // 反转时上一个结点应该指向下一个结点位置
        current = next; // 前进到到原本的下一个结点
    }

    // 头尾结点交换
    ListNode* temp = list->head;
    list->head = list->tail;
    list->tail = temp;
}

void list_print(const List* list) {
    if (list ==NULL)
    {
        printf("[]\n"); return;
    }

    const ListNode* cur = list->head;
    printf("[");
    while (cur) {
        printf("%d", cur->value);
        if (cur->next) printf(", ");
        cur = cur->next;
    }
    printf("] (size=%zu)\n", list->size);
}

测试代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include "doublelist.h"
#include <stdio.h>
#include <assert.h>

static void sum_cb(int v, void* user) {
    int* acc = (int*)user;
    *acc += v;
}

static void print_banner(const char* title) {
    printf("\n==== %s ====\n", title);
}

int main(void) {
    List ls;
    list_init(&ls);
    assert(list_empty(&ls));
    assert(list_size(&ls) == 0);

    int out = 0;

    print_banner("空表操作");
    assert(!list_delete_front(&ls, &out));
    assert(!list_delete_back(&ls, &out));
    assert(list_remove_value(&ls, 123, true) == 0);

    print_banner("首尾插入");
    assert(list_add_front(&ls, 1));           /* [1] */
    assert(list_add_front(&ls, 0));           /* [0,1] */
    assert(list_add_back(&ls, 2));            /* [0,1,2] */
    assert(list_add_back(&ls, 3));            /* [0,1,2,3] */
    list_print(&ls);
    assert(list_size(&ls) == 4);

    print_banner("按位插入");
    assert(list_insert(&ls, 2, 99));          /* [0,1,99,2,3] */
    list_print(&ls);
    assert(list_insert(&ls, list_size(&ls), 42)); /* 尾插 => [0,1,99,2,3,42] */
    list_print(&ls);

    print_banner("查找");
    long idx = list_find_first(&ls, 99);
    printf("find 99 at index=%ld\n", idx);
    assert(idx == 2);
    assert(list_find_first(&ls, -7) == -1);

    print_banner("按位删除（头/中/尾）");
    assert(list_remove_at(&ls, 0, &out));     /* 删除头 0 */
    assert(out == 0);
    list_print(&ls);

    assert(list_remove_at(&ls, 1, &out));     /* 删除中间：原 [1,99,2,3,42] 删除 99 */
    assert(out == 99);
    list_print(&ls);

    assert(list_remove_at(&ls, list_size(&ls) - 1, &out)); /* 删尾 42 */
    assert(out == 42);
    list_print(&ls);

    print_banner("按值删除（删一个/删全部）");
    assert(list_add_back(&ls, 2));
    assert(list_add_back(&ls, 2));            /* 末尾补两个 2 */
    list_print(&ls);

    size_t removed = list_remove_value(&ls, 2, false); /* 只删一个 2 */
    printf("removed one 2 = %zu\n", removed);
    assert(removed == 1);
    list_print(&ls);

    removed = list_remove_value(&ls, 2, true);        /* 删剩余所有 2 */
    printf("removed all 2 = %zu\n", removed);
    assert(removed >= 1);
    list_print(&ls);

    print_banner("反转与遍历");
    /* 现在链表约为 [1,2,3] 或类似，继续构造并反转 */
    assert(list_add_front(&ls, -1));
    assert(list_add_back(&ls, 10));
    list_print(&ls);

    list_reverse(&ls);
    printf("reversed: ");
    list_print(&ls);

    int sum = 0;
    list_foreach(&ls, sum_cb, &sum);
    printf("sum=%d\n", sum);

    print_banner("清空与复用");
    list_clear(&ls);
    assert(list_empty(&ls));
    list_print(&ls);

    /* 再次使用 */
    assert(list_add_back(&ls, 7));
    assert(list_add_back(&ls, 8));
    list_print(&ls);
    list_destroy(&ls);
    assert(list_size(&ls) == 0); /* destroy 等价 clear */

    printf("\nAll tests passed!\n");
    return 0;
}

输出结果：

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
C:\Users\keqiu\myProjects\CLionProjects\C\LinkList\double_linklist\build\double_linklist.exe

==== 空表操作 ====

==== 首尾插入 ====
[0, 1, 2, 3] (size=4)

==== 按位插入 ====
[0, 1, 99, 2, 3] (size=5)
[0, 1, 99, 2, 3, 42] (size=6)

==== 查找 ====
find 99 at index=2

==== 按位删除（头/中/尾） ====
[1, 99, 2, 3, 42] (size=5)
[1, 2, 3, 42] (size=4)
[1, 2, 3] (size=3)

==== 按值删除（删一个/删全部） ====
[1, 2, 3, 2, 2] (size=5)
removed one 2 = 1
[1, 3, 2, 2] (size=4)
removed all 2 = 2
[1, 3] (size=2)

==== 反转与遍历 ====
[-1, 1, 3, 10] (size=4)
reversed: [10, 3, 1, -1] (size=4)
sum=13

==== 清空与复用 ====
[] (size=0)
[7, 8] (size=2)

All tests passed!

进程已结束，退出代码为 0

循环单向链表

介绍

循环链表（Circular Linked List）：链表的一种变体。最后一个节点的后继指针指回到链表的“首元素”，形成一个环。最常见的工程实现是“单向循环链表 + tail 指针”（仅保存尾指针，首元素可由 head = tail->next 得到），常用于循环队列、轮询调度等。

  • 循环链表的特点：无论从哪个节点出发，都可以遍历到链表中的任意节点，实现了节点间的循环访问。

image-20251012175303425

链表结构体定义

循环链表不再保存头指针，而是仅保存tail指针，通过tail->next即可访问头结点

1
2
3
4
5
6
7
8
9
10
11
/*结点定义*/
typedef struct ListNode {
    int value;               /* 节点数据 */
    struct ListNode* next;   /* 指向下一个节点 */
} ListNode;

/* 容器：仅保存 tail，head 可由 tail->next 得出 */
typedef struct List {
    ListNode* tail;          /* 尾指针；空表为 NULL */
    size_t    size;          /* 元素个数 */
} List;

API设计与实现思路

单向循环链表的api设计与上方单向链表相同，这里具体说明单向循环链表哪些API与单向链表实现不同

与单向链表实现不同的 API 原型 作用 核心实现思路/步骤（与单向差异） 时间复杂度（循环 vs 单向） 边界/注意点
list_init void list_init(List* list) 初始化 置 tail=NULL, size=0（循环链表用 tail 表示端点） O(1) vs O(1) -
list_clear void list_clear(List* list) 清空 从 head=tail->next 开始，按“初始 size 次”释放，避免环上死循环；最后 tail=NULL O(n) vs O(n) 不能用“走到 NULL 停止”；按计数释放
list_add_front bool list_add_front(List* list, int v) 头插 空表：n->next=n; tail=n；非空：n->next=tail->next; tail->next=n（n 成为新 head） O(1) vs O(1) 新 head 用 tail->next 表示；不必更新 tail
list_add_back bool list_add_back(List* list, int v) 尾插 空表同上；非空：n->next=tail->next; tail->next=n; tail=n O(1) vs O(n) 借助 tail 将尾插降为 O(1)
list_delete_front bool list_delete_front(List* list, int* out) 头删 head=tail->next；单节点：free(tail), tail=NULL；否则：tail->next=head->next, free(head) O(1) vs O(1) 单节点与非单节点分支；保持环连通
list_delete_back bool list_delete_back(List* list, int* out) 尾删 单节点同头删；否则从 head 线性找到尾前驱 prev（prev->next==tail），prev->next=tail->next，free(tail)，tail=prev O(n) vs O(n) 必须线性找前驱；更新 tail
list_insert bool list_insert(List* list, size_t idx, int v) 按位插入 idx=0 调头插；idx=size 调尾插；否则从 head=tail->next 走到 idx-1，再线性插入 O(n) vs O(n) 遍历不以 NULL 终止；从 head 起步
list_remove_at bool list_remove_at(List* list, size_t idx, int* out) 按位删除 idx=0 调头删；idx=size-1 调尾删；否则从 head 走到 idx-1，删除其 next O(n) vs O(n) 注意单节点与删尾时 tail 的更新
list_remove_value size_t list_remove_value(List* list, int v, bool all) 按值删除 为避免死循环，用“初始 size 次计数”或“回到起点”终止；命中时 relink，若删尾则 tail=prev；删空则 tail=NULL O(n) vs O(n) 不可用“while(cur)”以 NULL 终止；删空置 tail=NULL
list_find_first long list_find_first(const List* list, int v) 查找首个索引 非空从 head 起“走 size 次”或 do-while 回到 head 为止 O(n) vs O(n) 终止条件为计数或回到起点，而非 cur==NULL
list_foreach void list_foreach(const List* list, void (fn)(int, void), void* user) 遍历回调 非空从 head 起遍历“size 次”调用回调 O(n) vs O(n) 回调若改结构需谨慎，避免破坏计数遍历
list_reverse void list_reverse(List* list) 原地反转 先“断环”（tail->next=NULL）→ 线性三指针反转 → “接回环”：新尾（原 head）->next=新头，tail=新尾 O(n) vs O(n) 空/单节点直接返回；断环/接环和 tail 更新别遗漏
list_print void list_print(const List* list) 打印 非空从 head 起“走 size 次”输出，常标注 circular O(n) vs O(n) 打印不以 NULL 终止，按 size 控制次数

循环单向链表源码实现

github仓库：https://github.com/keqiudi/LinkList/tree/master/circular_linklist

circularlist.h

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/**
 * @file    circularlist.h
 * @brief   基于单向循环链表（int 元素）的通用接口声明
 * @details 提供链表的初始化、销毁、增删改查、遍历与反转等基础操作；默认线程不安全。
 *          环形结构：仅保存 tail 指针，非空时 head = tail->next。
 *          若需在多线程环境中使用，请在调用层加锁。
 *
 * @note    复杂度（单向循环链表）：
 *          - 头部插入/删除：O(1)
 *          - 尾部插入：O(1)（借助 tail 指针）
 *          - 尾部删除、按位访问/插入/删除、按值删除：O(n)
 */

#ifndef CIRCULARLIST_H
#define CIRCULARLIST_H

#include <stddef.h>  /* size_t */
#include <stdbool.h> /* bool   */

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @brief 链表节点
 */
typedef struct ListNode
{
    int value;               /**< 节点存储的数据元素 */
    struct ListNode* next;   /**< 指向后继（环） */
} ListNode;

/**
 * @brief 链表容器（仅保存 tail；非空时 head = tail->next）
 */
typedef struct List
{
    ListNode* tail;          /**< 尾指针；空表为 NULL */
    size_t    size;          /**< 当前元素个数 */
} List;

/* ======================= 基础管理 ======================= */

/**
 * @brief  初始化链表（将指针置空，大小置零）
 * @param  list 指向链表对象
 */
void list_init(List* list);

/**
 * @brief  销毁链表（等价于清空全部节点）
 * @param  list 指向链表对象
 * @note   本实现不另持外部资源，等价于 list_clear
 */
void list_destroy(List* list);

/**
 * @brief  清空链表中的全部节点
 * @param  list 指向链表对象
 */
void list_clear(List* list);

/**
 * @brief  获取链表大小
 * @param  list 指向链表对象（可为 NULL）
 * @return 元素个数；若 list 为 NULL 返回 0
 */
size_t list_size(const List* list);

/**
 * @brief  判断链表是否为空
 * @param  list 指向链表对象
 * @return 为空返回 true，否则返回 false
 */
bool list_empty(const List* list);

/* =================== 末端与首端操作 =================== */

/**
 * @brief  头插：在表头插入一个元素
 * @param  list  链表指针
 * @param  value 待插入的值
 * @return 成功返回 true，分配失败返回 false
 * @complexity O(1)
 */
bool list_add_front(List* list, int value);

/**
 * @brief  尾插：在表尾插入一个元素
 * @param  list  链表指针
 * @param  value 待插入的值
 * @return 成功返回 true，分配失败返回 false
 * @complexity O(1)（借助 tail 指针）
 */
bool list_add_back(List* list, int value);

/**
 * @brief  头删：删除表头元素
 * @param  list      链表指针
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；若链表为空返回 false
 * @complexity O(1)
 */
bool list_delete_front(List* list, int* out_value);

/**
 * @brief  尾删：删除表尾元素
 * @param  list      链表指针
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；若链表为空返回 false
 * @complexity O(n)（需线性寻找尾结点的前驱）
 */
bool list_delete_back(List* list, int* out_value);

/* =================== 位置与值操作 =================== */

/**
 * @brief  按位置插入元素
 * @param  list  链表指针
 * @param  index 插入位置（合法范围 0..size），0 等价于头插，size 等价于尾插
 * @param  value 待插入的值
 * @return 成功返回 true；index 越界或分配失败返回 false
 * @complexity O(n)
 */
bool list_insert(List* list, size_t index, int value);

/**
 * @brief  按位置删除元素
 * @param  list      链表指针
 * @param  index     删除位置（合法范围 0..size-1）
 * @param  out_value 若非 NULL，则返回被删除的值
 * @return 成功返回 true；越界或空表返回 false
 * @complexity O(n)
 */
bool list_remove_at(List* list, size_t index, int* out_value);

/**
 * @brief  按值删除元素（可删除首个或全部匹配项）
 * @param  list       链表指针
 * @param  value      要删除的目标值
 * @param  remove_all true 删除全部匹配项；false 仅删除首个
 * @return 实际删除的元素个数
 * @complexity O(n)
 */
size_t list_remove_value(List* list, int value, bool remove_all);

/* =================== 查询与遍历 =================== */

/**
 * @brief  查找首个等于 value 的元素位置
 * @param  list  链表指针
 * @param  value 目标值
 * @return 索引（0 开始）；未找到返回 -1
 * @complexity O(n)
 */
long list_find_first(const List* list, int value);

/**
 * @brief  遍历链表，对每个元素调用回调
 * @param  list 链表指针
 * @param  fn   回调函数，签名为 void (*)(int value, void* user)
 * @param  user 透传给回调的用户参数
 * @note   回调内若修改链表结构需格外小心，避免失效遍历指针
 */
void list_foreach(const List* list, void (*fn)(int value, void* user), void* user);

/* =================== 其他常用函数 =================== */

/**
 * @brief  原地反转链表
 * @param  list 链表指针
 * @complexity O(n)，额外空间 O(1)
 */
void list_reverse(List* list);

/**
 * @brief  打印链表内容（调试用途）
 * @param  list 链表指针
 * @note   实现依赖 stdio；生产环境可替换为自定义输出
 */
void list_print(const List* list);

#ifdef __cplusplus
}
#endif

#endif /* CIRCULARLIST_H */

circularlist.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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
#include "circular_list.h"
#include <stdio.h>
#include <stdlib.h>


static ListNode* create_node(int value)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL)
    {
        return NULL;
    }
    node->value = value;
    node->next = NULL;

    return node;
}

void list_init(List* list)
{
    if (list == NULL){
        return;
    }
    list->tail = NULL;
    list->size = 0;
}

void list_clear(List* list)
{
    if (list == NULL || list->tail == NULL){
        return;
    }
    /* 从 head 开始走 size 次逐个释放，避免死循环 */
    ListNode* current = list->tail->next; // 获取头结点
    for (size_t i=0;i<list->size;i++)
    {
        ListNode* next = current->next;
        free(current);
        current = next;
    }

    list->tail = NULL;
    list->size = 0;
}

void list_destroy(List* list) {
    list_clear(list);
}

size_t list_size(const List* list) {
    return list ? list->size : 0;
}

bool list_empty(const List* list) {
    return list ? (list->size == 0) : true;
}

bool list_add_front(List* list,int value)
{
    if (list == NULL){
        return false;
    }

    ListNode* node = create_node(value);
    if (node == NULL){
        return false;
    }

    if (list->tail == NULL)
    {
        /* 空表：自环 */
        node->next = node;
        list->tail = node;
    }
    else
    {
        node->next = list->tail->next;
        list->tail->next = node;
    }
    list->size++;

    return true;
}

bool list_add_back(List* list,int value)
{
    // 链表不为空
    if (list == NULL){
        return false;
    }
    ListNode* node = create_node(value);
    //节点创建失败
    if (node == NULL){
        return false;
    }

    if (list->tail == NULL)
    {
        /* 空表：自环 */
        node->next = node;
        list->tail = node;
    }
    else
    {
        node->next = list->tail->next; /* 新结点指向head */
        list->tail->next = node; /* 添加结点到尾部 */
        list->tail = node; /* 更新尾指针 */

    }
    list->size++;

    return true;
}

bool list_delete_front(List* list, int* out_value)
{
    if (list == NULL || list->tail == NULL){
        return false;
    }

    ListNode* head = list->tail->next;
    if (out_value != NULL)
    {
        *out_value = head->value;
    }

    /* 单节点处理 */
    if (head == list->tail)
    {
        free(head);
        list->tail = NULL;
    }
    else
    {
        list->tail->next = head->next; /* 跳过head */
        free(head);
    }

    list->size--;
    return true;
}

bool list_delete_back(List* list, int* out_value)
{
    if (list == NULL || list->tail == NULL){
        return false;
    }

    ListNode* tail = list->tail;
    if (out_value != NULL)
    {
        *out_value = tail->value;
    }

    /* 只有一个结点 */
    if (tail == tail->next)
    {
        free(tail);
        list->tail == NULL;
    }
    else
    {
        ListNode* prev = tail->next;
        while (prev->next != tail)
        {
            prev = prev->next;
        }

        prev->next = tail->next; // 更新队尾指向头结点
        free(tail); // 释放目标结点
        list->tail = prev; // 更新尾部结点
    }

    list->size--;
    return true;
}

bool list_insert(List* list, size_t index, int value)
{
    if (list == NULL){
        return false;
    }

    if (index > list->size){ /*只能插到0~size处*/
        return false;
    }

    /* index为0直接在头部插入结点 */
    if (index == 0){
        return list_add_front(list,value);

    }
    /* index为size直接在尾部插入结点 */
    if (index == list->size){
        return list_add_back(list,value);
    }

    /* 非端点插入 */
    ListNode* node = create_node(value);
    if (node == NULL){
        return false;
    }

    ListNode* current = list->tail->next; // 从头结点开始
    for (int i=0;i<index-1;i++)
    {
        current = current->next;
    }
    node->next = current->next;
    current->next = node;
    list->size++;
    return true;
}

bool list_remove_at(List* list,size_t index,int* out_value)
{
    if (list == NULL || index >= list->size){  // index取值是0~size-1
        return false;
    }

    /* index=0 直接删除头结点 */
    if (index == 0){
        return list_delete_front(list,out_value);
    }
    /* index=size-1 直接删除为尾结点 */
    if (index == list->size-1){
        return list_delete_back(list,out_value);
    }

    ListNode* current = list->tail->next; // 从头结点开始
    for (int i=0;i<index-1;i++)
    {
        current = current->next; // 找到index处的前一个结点
    }

    ListNode* target = current->next; //index的结点
    if (out_value != NULL)
    {
        *out_value = target->value;
    }

    current->next = target->next;
    free(target);
    list->size--;
    return true;
}

size_t list_remove_value(List* list, int value, bool remove_all)
{
    if (list == NULL || list->tail == NULL)
    {
        return 0;
    }

    size_t removed_num = 0; //删除结点数
    size_t times = list->size; // 最多遍历次数，避免死循环

    ListNode* current = list->tail->next; // 现在所在结点：从头结点开始
    ListNode* prev = list->tail; // 前驱结点

    for (size_t i=0;i<times;i++)
    {
        if (current == NULL)
        {
            break;  // 删空了直接退出
        }

        if (current->value == value)
        {
            ListNode* target = current;

            /* 单节点删除 */
            if (target == prev)
            {
                free(target);
                list->tail = NULL;
                list->size--;
                removed_num++;
                break;
            }
            /* 非单节点删除*/
            else
            {
                prev->next = target->next;
                if (target == list->tail)
                {
                    list->tail = prev; // 更新尾指针
                }

                current = target->next;
                free(target);
                list->size--;
                removed_num++;

                if (!remove_all)
                {
                    break;
                }
            }
        }
        else
        {
            prev = current;
            current = current->next;
        }

    }

    return removed_num;
}

long list_find_first(const List* list, int value)
{
    if (list == NULL || list->tail == NULL)
    {
        return -1;
    }

    ListNode* current = list->tail->next; // 从头结点开始
    for (long i=0;i<list->size;i++)
    {
        if (current->value == value)
        {
            return i;
        }
        current = current->next;
    }

    return -1;
}

void list_foreach(const List* list, void (*fn)(int value, void* user), void* user)
{
    if (list== NULL || list->tail ==NULL || !fn)
    {
        return;
    }

    const ListNode* cur = list->tail->next; /* 头结点 */
    for (size_t i = 0; i < list->size; ++i)
    {
        fn(cur->value, user);
        cur = cur->next;
    }
}


void list_reverse(List* list)
{
    if (list == NULL || list->tail == NULL)
    {
        return;
    }

    /* 单节点处理 */
    if (list->tail->next == list->tail)
    {
        return;
    }

    /* 断环 → 线性反转 → 接回环 */
    ListNode* head = list->tail->next; // 保存初始头结点
    list->tail->next = NULL; /* 断开，形成线性 [head ... NULL] */

    /* 线性反转 */
    ListNode* prev = NULL;
    ListNode* cur  = head;
    while (cur) {
        ListNode* nxt = cur->next; /* 1.先保存下一个结点 */
        cur->next = prev; /* 2.反转结点指向 */
        prev = cur; /* 3.更新上一个结点 */
        cur = nxt; /* 4.移动至下一个结点 */
    }
    /* 最后prev 为新头，head 为新尾 */
    head->next   = prev;   /* 新尾连回新头，形成环 */
    list->tail   = head;   /* 新尾为原 head */
}

void list_print(const List* list) {
    if (list == NULL || list->tail == NULL) {
        printf("[] (circular, size=0)\n");
        return;
    }
    const ListNode* cur = list->tail->next; /* head */
    printf("[");
    for (size_t i = 0; i < list->size; ++i) {
        printf("%d", cur->value);
        if (i + 1 < list->size) printf(" -> ");
        cur = cur->next;
    }
    printf("] (circular, size=%zu)\n", list->size);
}

测试代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "circular_list.h"
#include <stdio.h>
#include <assert.h>

/* 用于 foreach 的求和回调 */
static void sum_cb(int v, void* user) {
    int* acc = (int*)user;
    *acc += v;
}

int main(void) {
    List ls;
    list_init(&ls);

    /* 空表状态 */
    assert(list_empty(&ls) == true);
    assert(list_size(&ls) == 0);
    int tmp;
    assert(list_delete_front(&ls, &tmp) == false);
    assert(list_delete_back(&ls, &tmp) == false);
    assert(list_remove_at(&ls, 0, &tmp) == false);
    assert(list_remove_value(&ls, 123, true) == 0);

    /* 基本插入（头/尾） */
    assert(list_add_back(&ls, 1) == true);
    assert(list_add_back(&ls, 2) == true);
    assert(list_add_back(&ls, 3) == true);
    list_print(&ls);                       /* [1,2,3] */
    assert(list_size(&ls) == 3);
    assert(list_empty(&ls) == false);

    assert(list_add_front(&ls, 0) == true);/* [0,1,2,3] */
    list_print(&ls);
    assert(list_size(&ls) == 4);

    /* 指定位置插入：中间与尾部（index==size） */
    assert(list_insert(&ls, 2, 99) == true);            /* [0,1,99,2,3] */
    list_print(&ls);
    assert(list_insert(&ls, list_size(&ls), 42) == true); /* 尾部插入 => [...,3,42] */
    list_print(&ls);

    /* 查找 */
    long idx = list_find_first(&ls, 99);
    printf("find 99 at index = %ld\n", idx);
    assert(idx == 2);
    assert(list_find_first(&ls, -7) == -1);

    /* 按位删除：中间和尾部 */
    int val = 0;
    assert(list_remove_at(&ls, 2, &val) == true);       /* 删除 99 */
    assert(val == 99);
    list_print(&ls);

    assert(list_remove_at(&ls, list_size(&ls) - 1, &val) == true); /* 删尾 42 */
    assert(val == 42);
    list_print(&ls);

    /* 按值删除：先只删一个，再删全部 */
    assert(list_add_back(&ls, 2) == true);
    assert(list_add_back(&ls, 2) == true);              /* [...,2,2] */
    list_print(&ls);

    size_t removed = list_remove_value(&ls, 2, false);  /* 只删第一个 2 */
    printf("removed one 2 count=%zu\n", removed);
    assert(removed == 1);
    list_print(&ls);

    removed = list_remove_value(&ls, 2, true);          /* 删剩余所有 2 */
    printf("removed all 2 count=%zu\n", removed);
    assert(removed >= 1);
    list_print(&ls);

    /* 头删/尾删 */
    assert(list_delete_front(&ls, &val) == true);
    printf("delete_front=%d\n", val);
    list_print(&ls);

    assert(list_delete_back(&ls, &val) == true);
    printf("delete_back=%d\n", val);
    list_print(&ls);

    /* 反转：对多个元素、对单元素、对空表都应安全 */
    assert(list_add_back(&ls, 10) == true);
    assert(list_add_back(&ls, 20) == true);
    assert(list_add_back(&ls, 30) == true);
    list_print(&ls);

    list_reverse(&ls);
    printf("reversed: ");
    list_print(&ls);

    list_clear(&ls);
    list_reverse(&ls); /* 空表反转不应崩溃 */
    assert(list_empty(&ls));

    assert(list_add_back(&ls, 7) == true);
    list_reverse(&ls); /* 单元素反转不应改变内容 */
    assert(list_size(&ls) == 1);
    list_print(&ls);

    /* 遍历（foreach） */
    int sum = 0;
    list_foreach(&ls, sum_cb, &sum);
    printf("sum=%d\n", sum);
    assert(sum == 7);

    /* 清空与销毁 */
    list_clear(&ls);
    printf("cleared: ");
    list_print(&ls);
    assert(list_empty(&ls));
    list_destroy(&ls);

    printf("All tests passed!\n");
    return 0;
}

输出结果：

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
C:\Users\keqiu\myProjects\CLionProjects\C\LinkList\circular_linklist\build\circular_linklist.exe
    
[1 -> 2 -> 3] (circular, size=3)
[0 -> 1 -> 2 -> 3] (circular, size=4)
[0 -> 1 -> 99 -> 2 -> 3] (circular, size=5)
[0 -> 1 -> 99 -> 2 -> 3 -> 42] (circular, size=6)
find 99 at index = 2
[0 -> 1 -> 2 -> 3 -> 42] (circular, size=5)
[0 -> 1 -> 2 -> 3] (circular, size=4)
[0 -> 1 -> 2 -> 3 -> 2 -> 2] (circular, size=6)
removed one 2 count=1
[0 -> 1 -> 3 -> 2 -> 2] (circular, size=5)
removed all 2 count=2
[0 -> 1 -> 3] (circular, size=3)
delete_front=0
[1 -> 3] (circular, size=2)
delete_back=3
[1] (circular, size=1)
[1 -> 10 -> 20 -> 30] (circular, size=4)
reversed: [30 -> 20 -> 10 -> 1] (circular, size=4)
[7] (circular, size=1)
sum=7
cleared: [] (circular, size=0)
All tests passed!

进程已结束，退出代码为 0

循环双向链表

这个在循环单向链表的基础上进行修改即可，使用的时候再说吧