链表的三种实现源代码

链表是一种重要的数据结构，它在计算机科学中扮演着至关重要的角色，特别是在处理动态数据集合时。链表与数组不同，不连续存储元素，而是通过指针连接各个节点，每个节点包含数据和指向下一个节点的引用。在C语言中，链表的实现通常涉及到结构体和指针操作。下面我们将详细探讨链表的三种实现方式。 1. 单链表： 单链表是最基础的链表类型，每个节点只有一个指向后继节点的指针。在C语言中，我们可以定义一个结构体来表示链表节点： ```c typedef struct Node { int data; struct Node* next; } Node; ``` 创建单链表通常包括创建新节点、插入节点和遍历链表等操作。例如，插入一个节点可以在链表的开头或结尾： ```c Node* insert_at_start(Node* head, int value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = head; return newNode; } Node* insert_at_end(Node* head, int value) { if (!head) { return insert_at_start(head, value); } Node* curr = head; while (curr->next) { curr = curr->next; } curr->next = (Node*)malloc(sizeof(Node)); curr->next->data = value; curr->next->next = NULL; return head; } ``` 2. 双向链表： 双向链表增加了对前驱节点的引用，使得在链表中的前后移动更加灵活。结构体需要额外的`prev`指针： ```c typedef struct Node { int data; struct Node* next; struct Node* prev; } Node; ``` 插入节点时，需要同时更新前后节点的指针： ```c Node* insert_after(Node* node, int value) { if (!node) { return NULL; } Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = node->next; newNode->prev = node; if (node->next) { node->next->prev = newNode; } node->next = newNode; return head; } ``` 3. 循环链表： 循环链表是单链表的一种变体，最后一个节点的`next`指针指向链表的第一个节点，形成一个循环。实现循环链表时，插入和删除操作需要额外处理头节点的情况： ```c typedef struct Node { int data; struct Node* next; } Node; void make_circular(Node* head) { if (head && head->next) { head->next->next = head; } } Node* insert_at_circular_position(Node* head, int pos, int value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; if (!head) { head = newNode; } else { Node* curr = head; for (int i = 1; i < pos && curr->next != head; i++) { curr = curr->next; } newNode->next = curr->next; curr->next = newNode; if (newNode->next == head) { make_circular(head); } } return head; } ``` 这三种链表各有特点，适用于不同的场景。单链表简单易用，适用于大多数情况；双向链表提供了更灵活的导航，但需要更多的内存；循环链表在需要遍历循环或表示周期性序列时非常有用。理解和掌握这些链表实现方式是数据结构学习的重要一步，对于编写高效算法和优化内存管理至关重要。