1.概念：
单链表（Singly Linked List）是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含两个部分：
-
数据域（Data）：存储节点的值或数据。
-
指针域（Next）：存储指向下一个节点的指针。
单链表的特点是每个节点只指向下一个节点，最后一个节点的指针域指向 null，表示链表的结束。
2.基本操作：
-
创建节点：
-
定义一个节点类，包含数据域和指针域。
-
-
插入节点：
-
在头部插入：将新节点的
next指向当前头节点，然后更新头节点为新节点。 -
在尾部插入：遍历链表找到最后一个节点，将其
next指向新节点。 -
在中间插入：找到插入位置的前一个节点，将新节点的
next指向后一个节点，再将前一个节点的next指向新节点。
-
-
删除节点：
-
删除头节点：将头节点指向下一个节点。
-
删除尾节点：遍历链表找到倒数第二个节点，将其
next指向null。 -
删除中间节点：找到要删除节点的前一个节点，将其
next指向要删除节点的下一个节点。
-
-
查找节点：
-
从头节点开始遍历链表，直到找到目标节点或到达链表末尾。
-
-
遍历链表：
-
从头节点开始，依次访问每个节点，直到
next为null。
-
3.代码实现：
#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct Node {int data; // 数据域struct Node* next; // 指针域，指向下一个节点
};// 创建一个新节点
struct Node* create_node(int data) {struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));if (new_node == NULL) {printf("内存分配失败！\n");exit(1);}new_node->data = data;new_node->next = NULL;return new_node;
}// 在链表头部插入节点
void insert_at_head(struct Node** head, int data) {struct Node* new_node = create_node(data);new_node->next = *head;*head = new_node;
}// 在链表尾部插入节点
void insert_at_tail(struct Node** head, int data) {struct Node* new_node = create_node(data);if (*head == NULL) {*head = new_node;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = new_node;
}// 删除链表中指定值的节点
void delete_node(struct Node** head, int key) {struct Node* temp = *head;struct 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("未找到值为 %d 的节点\n", key);return;}// 删除节点prev->next = temp->next;free(temp);
}// 查找链表中是否包含指定值
int search(struct Node* head, int key) {struct Node* current = head;while (current != NULL) {if (current->data == key) {return 1; // 找到}current = current->next;}return 0; // 未找到
}// 遍历并打印链表
void print_list(struct Node* head) {struct Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}// 释放链表内存
void free_list(struct Node* head) {struct Node* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}// 主函数
int main() {struct Node* head = NULL;// 插入节点insert_at_head(&head, 3);insert_at_head(&head, 2);insert_at_head(&head, 1);insert_at_tail(&head, 4);printf("链表内容: ");print_list(head); // 输出: 1 -> 2 -> 3 -> 4 -> NULL// 删除节点delete_node(&head, 3);printf("删除节点 3 后的链表: ");print_list(head); // 输出: 1 -> 2 -> 4 -> NULL// 查找节点int key = 2;if (search(head, key)) {printf("值为 %d 的节点存在\n", key);} else {printf("值为 %d 的节点不存在\n", key);}// 释放链表内存free_list(head);return 0;
}运行结果
链表内容: 1 -> 2 -> 3 -> 4 -> NULL
删除节点 3 后的链表: 1 -> 2 -> 4 -> NULL
值为 2 的节点存在3.优缺点：
优点：
-
动态分配内存，无需预先确定链表大小。
-
插入和删除操作效率高（时间复杂度为 O(1)，前提是已知位置）。
缺点：
-
访问元素需要从头节点开始遍历，时间复杂度为 O(n)。
-
需要额外的指针空间。
4.应用场景：
单链表适合频繁插入和删除的场景，但如果需要频繁随机访问元素，数组或双向链表可能更合适。