链表相关知识

一、什么是链表？
链表是一种动态数据结构，由一系列“节点”组成。每个节点包含两个部分：数据域（data）：用于存储数据。
指针域（next）：指向下一个节点。
链表不像数组那样在内存中连续存放，而是通过指针将零散的内存块串联起来使用。

二.单链表的结构定义

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
typedef struct Node {int data;            // 数据域struct Node* next;   // 指针域，指向下一个节点
} Node;

三.链表的基本操作及实现

1. 创建一个新节点

Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (!newNode) {printf("Memory allocation failed.\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}

2. 头插法插入节点

void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}

3. 尾插法插入节点

void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}

4. 在指定位置插入节点

void insertAtPosition(Node** head, int position, int data) {if (position < 0) {printf("Invalid position.\n");return;}if (position == 0) {insertAtHead(head, data);return;}Node* newNode = createNode(data);Node* temp = *head;for (int i = 0; temp != NULL && i < position - 1; i++) {temp = temp->next;}if (temp == NULL) {printf("Position out of bounds.\n");free(newNode);return;}newNode->next = temp->next;temp->next = newNode;
}

5. 删除节点（按值删除第一个匹配项）

void deleteNodeByValue(Node** head, int key) {Node* temp = *head;Node* prev = NULL;// 如果头节点就是要删除的节点if (temp != NULL && temp->data == key) {*head = temp->next;free(temp);return;}// 寻找要删除的节点while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}if (temp == NULL) {printf("Value not found in list.\n");return;}prev->next = temp->next;free(temp);
}

6. 查找节点

Node* searchNode(Node* head, int key) {Node* temp = head;while (temp != NULL) {if (temp->data == key)return temp;temp = temp->next;}return NULL;
}

7. 打印链表

void printList(Node* head) {Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}

8. 销毁链表

void destroyList(Node** head) {Node* current = *head;Node* next;while (current != NULL) {next = current->next;free(current);current = next;}*head = NULL;
}

完整测试代码

int main() {Node* head = NULL;insertAtTail(&head, 10);insertAtTail(&head, 20);insertAtHead(&head, 5);insertAtPosition(&head, 2, 15); // 在位置2插入15printf("链表内容：\n");printList(head);printf("\n删除值为20的节点：\n");deleteNodeByValue(&head, 20);printList(head);printf("\n查找值为15的节点：\n");Node* found = searchNode(head, 15);if (found)printf("找到值 %d\n", found->data);elseprintf("未找到\n");destroyList(&head);return 0;
}

输出结果

链表内容：
5 -> 10 -> 15 -> 20 -> NULL删除值为20的节点：
5 -> 10 -> 15 -> NULL查找值为15的节点：
找到值 15