C语言中插入节点函数的详解与实现365

在C语言中，链表是一种常用的动态数据结构，其节点之间通过指针连接。插入节点操作是链表中最基本的操作之一，它允许在链表的特定位置插入新的节点。本文将深入探讨C语言中插入节点函数的实现，涵盖各种情况，并分析其时间复杂度和空间复杂度。

我们将主要关注单链表的插入操作，因为双向链表的插入操作较为复杂，需要考虑前驱节点和后继节点的指针更新。单链表的插入操作通常可以分为三种情况：头部插入、尾部插入和中间插入。

1. 头部插入

头部插入是指将新节点插入到链表的头部。这是最简单的一种插入操作，其时间复杂度为O(1)。```c
#include
#include
// 定义节点结构体
typedef struct Node {
int data;
struct Node *next;
} Node;
// 头部插入函数
void insertNodeAtHead(Node head, int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "内存分配失败!");
exit(1);
}
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
// 打印链表
void printList(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL");
}
int main() {
Node *head = NULL;
insertNodeAtHead(&head, 10);
insertNodeAtHead(&head, 20);
insertNodeAtHead(&head, 30);
printList(head); // 输出: 30 -> 20 -> 10 -> NULL
return 0;
}
```

在这个例子中，`insertNodeAtHead` 函数接收链表头指针的地址和要插入的数据作为参数。它首先动态分配一个新的节点，然后将新节点的数据设置为输入数据，并将新节点的 `next` 指针指向当前链表的头节点。最后，它将链表的头指针更新为新节点的地址。

2. 尾部插入

尾部插入是指将新节点插入到链表的尾部。与头部插入不同，尾部插入需要遍历整个链表找到尾节点，因此其时间复杂度为O(n)，其中n是链表的长度。```c
// 尾部插入函数
void insertNodeAtTail(Node head, int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "内存分配失败!");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
```

这段代码首先创建一个新的节点，然后检查链表是否为空。如果为空，则将新节点设置为头节点。否则，遍历链表找到尾节点，并将新节点添加到尾节点之后。

3. 中间插入

中间插入是指将新节点插入到链表的中间位置。这需要找到插入位置的前一个节点，然后将新节点插入到前一个节点和后一个节点之间。其时间复杂度也为O(n)。```c
// 中间插入函数，在第position个位置插入数据
void insertNodeAtPosition(Node head, int position, int data) {
if (position data = data;
if (position == 1) {
insertNodeAtHead(head, data);
return;
}
Node *prev = *head;
int count = 1;
while (prev != NULL && count < position -1) {
prev = prev->next;
count++;
}
if (prev == NULL) {
fprintf(stderr, "位置超出链表范围!");
free(newNode);
return;
}
newNode->next = prev->next;
prev->next = newNode;
}
```