摘要：链表是一种基础且重要的数据结构，它由一系列节点（Node）组成，这些节点在内存中不必是连续存储的。每个节点包含数据域和指向下一个（或上一个）节点的指针域。链表因其动态性（可以方便地插入和删除元素而无需移动大量数据）而被广泛应用于各种编程场景。
链表是一种基础且重要的数据结构，它由一系列节点（Node）组成，这些节点在内存中不必是连续存储的。每个节点包含数据域和指向下一个（或上一个）节点的指针域。链表因其动态性（可以方便地插入和删除元素而无需移动大量数据）而被广泛应用于各种编程场景。
本教程将介绍三种基本类型的链表：单向链表、双向链表和循环链表。
数据域 (Data)：存储实际数据。指针域 (Next)：存储指向下一个节点的地址。最后一个节点的指针域通常为 NULL。Head| +------+-----+ +------+-----+ +------+-----+ +--->| Data | Next|---->| Data | Next|---->| Data | NULL|+------+-----+ +------+-----+ +------+-----+ Node 1 Node 2 Node 3 (Tail) #include #include // 单向链表节点定义typedefstruct SNode {int data; // 数据域，这里假设为int类型struct SNode *next; // 指针域，指向下一个节点} SNode, *SLinkedList; // SNode是结构体类型名，SLinkedList是指向SNode的指针类型 SNode* create_snode(int value) {SNode *new_node = (SNode*)malloc(sizeof(SNode));if (new_node == NULL) {perror("Failed to allocate memory for new snode");return NULL;}new_node->data = value;new_node->next = NULL;return new_node;}头插法 (Insert at Head)：新节点成为新的头节点。尾插法 (Insert at Tail)：新节点添加到链表末尾。在指定位置后插入 (Insert After a Given Node)：删除指定值的节点：需要找到该节点及其前驱节点。voiddelete_snode_by_value(SLinkedList*head_ref, intkey) {SNode*temp=*head_ref, *prev=NULL;
// 如果头节点就是要删除的节点
if (temp!=NULL&&temp->data==key) {
*head_ref=temp->next; // 改变头指针
free(temp); // 释放旧头节点
return;
}
// 查找要删除的节点，并记录其前驱
while (temp!=NULL&&temp->data!=key) {
prev=temp;
temp=temp->next;
}
// 如果没有找到该节点
if (temp==NULL) {
printf("Node with value %d not found.\n", key);
return;
}
// 从链表中移除节点
prev->next=temp->next;
free(temp); // 释放内存
} void print_slist(SLinkedList head) {SNode *current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");}SNode* find_snode(SLinkedList head, int key) {SNode *current = head;while (current != NULL) {if (current->data == key) {return current;}current = current->next;}return NULL; // 未找到}void free_slist(SLinkedList *head_ref) {SNode *current = *head_ref;SNode *next_node;while (current != NULL) {next_node = current->next;free(current);current = next_node;}*head_ref = NULL; // 将头指针置为NULL}int main_singly { // Renamed to avoid conflict if all examples are in one fileSLinkedList list_head = NULL;insert_snode_at_tail(&list_head, 10);insert_snode_at_head(&list_head, 5);insert_snode_at_tail(&list_head, 20);insert_snode_after(find_snode(list_head, 10), 15);printf("Singly Linked List: ");print_slist(list_head);delete_snode_by_value(&list_head, 10);printf("After deleting 10: ");print_slist(list_head);SNode *found = find_snode(list_head, 15);if (found) {printf("Found node with value: %d\n", found->data);}free_slist(&list_head);printf("After freeing list: ");print_slist(list_head);return 0;}
双向链表的每个节点包含三部分：
数据域 (Data)。指向下一个节点的指针域 (Next)。指向上一个节点的指针域 (Prev)。第一个节点的 prev 指针通常为 NULL，最后一个节点的 next 指针通常为 NULL。 Head Tail| |v v NULL | Data| Next|---->| Prev | Data| Next|---->| Prev | Data| NULLltltNode 1 Node 2 Node 3// 双向链表节点定义typedef struct DNode {int data;struct DNode *prev;struct DNode *next;} DNode, *DLinkedList;DNode* create_dnode(int value) {DNode *new_node = (DNode*)malloc(sizeof(DNode));if (new_node == NULL) {perror("Failed to allocate memory for new dnode");return NULL;}new_node->data = value;new_node->prev = NULL;new_node->next = NULL;return new_node;}头插法void insert_dnode_at_head(DLinkedList *head_ref, int value) {DNode *new_node = create_dnode(value);
if (new_node == NULL) return;
new_node->next = *head_ref;
if (*head_ref != NULL) {
(*head_ref)->prev = new_node;
}
*head_ref = new_node;
}尾插法void insert_dnode_at_tail(DLinkedList *head_ref, int value) {
DNode *new_node = create_dnode(value);
if (new_node == NULL) return;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
DNode *last = *head_ref;
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
new_node->prev = last;
}在指定节点后插入void insert_dnode_after(DNode *prev_node, int value) {
if (prev_node == NULL) {
printf("Previous node cannot be NULL.\n");
return;
}
DNode *new_node = create_dnode(value);
if (new_node == NULL) return;
new_node->next = prev_node->next;
new_node->prev = prev_node;
prev_node->next = new_node;
if (new_node->next != NULL) { // 如果 prev_node 不是尾节点
new_node->next->prev = new_node;
}
}在指定节点前插入void insert_dnode_before(DLinkedList *head_ref, DNode *next_node, int value) {
if (next_node == NULL) {
printf("Next node cannot be NULL for insertion before.\n");
// (Could also mean insert at tail if list is not empty, or head if list is empty)
// For simplicity, we assume next_node is a valid existing node or we are inserting at head.
if (*head_ref == NULL) { // If list is empty, this is like head insertion
insert_dnode_at_head(head_ref, value);
return;
}
// If next_node is NULL but list is not, it's ambiguous. Let's disallow for now.
return;
}
Dnode *new_node = create_dnode(value);
if (new_node == NULL) return;
new_node->prev = next_node->prev;
new_node->next = next_node;
next_node->prev = new_node;
if (new_node->prev != NULL) { // 如果 next_node 不是头节点
new_node->prev->next = new_node;
} else { // new_node 成为新的头节点
*head_ref = new_node;
}
}
删除节点 del_node 时，需要处理其前驱 del_node->prev 和后继 del_node->next。
void delete_dnode(DLinkedList *head_ref, DNode *del_node) {if (*head_ref == NULL || del_node == NULL) {return;}// 如果要删除的是头节点if (*head_ref == del_node) {*head_ref = del_node->next;}// 修改 del_node 的后继节点的前驱指针 (如果 del_node 不是尾节点)if (del_node->next != NULL) {del_node->next->prev = del_node->prev;}// 修改 del_node 的前驱节点的后继指针 (如果 del_node 不是头节点)if (del_node->prev != NULL) {del_node->prev->next = del_node->next;}free(del_node);}// 辅助函数：按值查找并删除void delete_dnode_by_value(DLinkedList *head_ref, int key) {DNode *current = *head_ref;while (current != NULL) {if (current->data == key) {delete_dnode(head_ref, current);return; // 假设只删除第一个匹配项}current = current->next;}printf("Node with value %d not found for deletion.\n", key);}void print_dlist_forward(DLinkedList head) {DNode *current = head;printf("Forward: NULL ");while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("NULL\n");}void print_dlist_backward(DLinkedList head) {if (head == NULL) {printf("Backward: NULL\n");return;}DNode *last = head;while (last->next != NULL) { // 找到尾节点last = last->next;}printf("Backward: NULL ");DNode *current = last;while (current != NULL) {printf("%d ", current->data);current = current->prev;}printf("NULL\n");}与单向链表类似。
void free_dlist(DLinkedList *head_ref) {DNode *current = *head_ref;DNode *next_node;while (current != NULL) {next_node = current->next;free(current);current = next_node;}*head_ref = NULL;}int main_doubly { // RenamedDLinkedList dlist_head = NULL;insert_dnode_at_head(&dlist_head, 10);insert_dnode_at_tail(&dlist_head, 20);insert_dnode_at_head(&dlist_head, 5);// 假设要插在10之后: find 10, then insert_dnode_afterDNode *node_10 = dlist_head; // 5 -> 10 -> 20, node_10 is 5while(node_10 != NULL && node_10->data != 10) node_10 = node_10->next;if(node_10) insert_dnode_after(node_10, 15); // 5 -> 10 -> 15 -> 20printf("Doubly Linked List (Forward): "); print_dlist_forward(dlist_head);printf("Doubly Linked List (Backward): "); print_dlist_backward(dlist_head);delete_dnode_by_value(&dlist_head, 10);printf("After deleting 10 (Forward): "); print_dlist_forward(dlist_head);free_dlist(&dlist_head);printf("After freeing list (Forward): "); print_dlist_forward(dlist_head);return 0;}循环链表可以是单向的也可以是双向的。其特点是链表的最后一个节点的 next 指针（对于单向循环链表）或 next 和 prev 指针（对于双向循环链表）不再指向 NULL，而是指向链表的头节点。
最后一个节点的 next 指针指向头节点。
Head| +------+-----+ +------+-----+ +------+-----+ +--->| Data | Next|---->| Data | Next|---->| Data | Next|--++------+-----+ +------+-----+ +------+-----+ |Node 1 Node 2 Node 3 |^ || |++最后一个节点的 next 指针指向头节点，头节点的 prev 指针指向尾节点。
++ | | v Head ^ Tail Prev | Data| Next|---->| Prev | Data| Next|---->| Prev | Data| Nextltlt |Node 1 Node 2 Node 3 |^ || |++节点结构定义操作循环链表时，需要特别注意循环的终止条件，以及在修改头尾连接时正确更新指针。 通常，我们会维护一个指向尾节点的指针（tail），这样可以方便地在O(1)时间内访问头节点（tail->next）和尾节点。
在空链表中插入第一个节点void insert_scircular_empty(SLinkedList *tail_ref, int value) {SNode *new_node = create_snode(value);
if (new_node == NULL) return;
*tail_ref = new_node;
new_node->next = new_node; // 指向自身形成循环
}头插法 (在 tail->next 前插入)void insert_scircular_at_head(SLinkedList *tail_ref, int value) {
if (*tail_ref == NULL) { // 如果链表为空
insert_scircular_empty(tail_ref, value);
return;
}
SNode *new_node = create_snode(value);
if (new_node == NULL) return;
new_node->next = (*tail_ref)->next; // 新节点的next指向原来的头
(*tail_ref)->next = new_node; // 尾节点的next指向新头
}尾插法 (在 tail 后插入，新节点成为新尾)void insert_scircular_at_tail(SLinkedList *tail_ref, int value) {
if (*tail_ref == NULL) {
insert_scircular_empty(tail_ref, value);
return;
}
SNode *new_node = create_snode(value);
if (new_node == NULL) return;
new_node->next = (*tail_ref)->next; // 新节点的next指向原来的头
(*tail_ref)->next = new_node; // 原尾节点的next指向新节点
*tail_ref = new_node; // 更新尾指针
}
删除操作比较复杂，需要考虑删除的是头节点、尾节点还是一般节点，以及链表只有一个节点的情况。
// 删除单向循环链表中指定值的节点 (假设 tail_ref 指向尾节点)void delete_scircular_by_value(SLinkedList *tail_ref, int key) {if (*tail_ref == NULL) {printf("List is empty.\n");return;}SNode *current = (*tail_ref)->next; // 从头节点开始SNode *prev = *tail_ref; // prev 初始化为尾节点// 循环查找，直到回到头节点或找到do {if (current->data == key) {// 情况1: 链表只有一个节点且是目标节点if (current == *tail_ref && current->next == current) {free(current);*tail_ref = NULL;return;}// 情况2: 删除的是头节点 (current == (*tail_ref)->next)if (current == (*tail_ref)->next) {(*tail_ref)->next = current->next; // 尾节点指向新的头}// 情况3: 删除的是尾节点 (current == *tail_ref)else if (current == *tail_ref) {prev->next = current->next; // 前一个节点指向头*tail_ref = prev; // 更新尾指针}// 情况4: 删除的是中间节点else {prev->next = current->next;}free(current);return;}prev = current;current = current->next;} while (current != (*tail_ref)->next); // 循环条件printf("Node with value %d not found.\n", key);}void print_scircular_list(SLinkedList tail) {if (tail == NULL) {printf("Circular List is empty.\n");return;}SNode *current = tail->next; // 从头节点开始printf("Head -> ");do {printf("%d -> ", current->data);current = current->next;} while (current != tail->next); // 直到再次回到头节点printf("(Head)\n");}void free_scircular_list(SLinkedList *tail_ref) {if (*tail_ref == NULL) return;SNode *current = (*tail_ref)->next; // 头节点SNode *head = current;SNode *next_node;// 断开循环，使其变成一个普通的单向链表，方便释放(*tail_ref)->next = NULL; while (current != NULL) {next_node = current->next;free(current);current = next_node;}*tail_ref = NULL;}int main_scircular { // RenamedSLinkedList sc_tail = NULL;insert_scircular_at_tail(&sc_tail, 10);insert_scircular_at_head(&sc_tail, 5); // 5 (H) -> 10 (T) -> 5insert_scircular_at_tail(&sc_tail, 20); // 5 (H) -> 10 -> 20 (T) -> 5insert_scircular_at_head(&sc_tail, 1); // 1 (H) -> 5 -> 10 -> 20 (T) -> 1printf("Singly Circular Linked List: ");print_scircular_list(sc_tail);delete_scircular_by_value(&sc_tail, 10); // 1 (H) -> 5 -> 20 (T) -> 1printf("After deleting 10: ");print_scircular_list(sc_tail);delete_scircular_by_value(&sc_tail, 1); // 5 (H) -> 20 (T) -> 5printf("After deleting 1 (head): ");print_scircular_list(sc_tail);delete_scircular_by_value(&sc_tail, 20); // 5 (H, T) -> 5printf("After deleting 20 (tail): ");print_scircular_list(sc_tail);delete_scircular_by_value(&sc_tail, 5); // Emptyprintf("After deleting 5 (last element): ");print_scircular_list(sc_tail);// Re-populate for freeing testinsert_scircular_at_tail(&sc_tail, 100);insert_scircular_at_tail(&sc_tail, 200);free_scircular_list(&sc_tail);printf("After freeing list: ");print_scircular_list(sc_tail);return 0;}// To run all examples, you might call them from a main function:/*int main {printf("--- Singly Linked List Demo ---\n");main_singly;printf("\n--- Doubly Linked List Demo ---\n");main_doubly;printf("\n--- Singly Circular Linked List Demo ---\n");main_scircular;return 0;}*/链表是理解更复杂数据结构和算法的基础。单向链表是最简单的形式，双向链表提供了更灵活的前后遍历和删除能力（但开销更大），循环链表则适用于需要循环访问或从尾部快速访问头部的场景（如循环队列、时间片轮转调度）。
掌握链表的各种操作（创建、插入、删除、查找、遍历、释放）是C语言程序员必备的技能。在实际应用中，选择哪种链表取决于具体的需求和性能考量。
来源：如水滴人生
