1.链表的概念
链表是一种动态数据结构，由一系列节点（Node）通过指针连接而成，每个节点存储着数据和指向下一个节点的指针。链表最大的特点是节点的存储地址不连续，因此可以灵活地进行插入和删除操作，而不需要像数组那样移动其他元素。
链表的组成
节点（Node）：链表中的基本单元，每个节点包含两部分：
1.数据域（Data）：存储节点中的数据。
2.指针域（Next）：存储指向下一个节点的指针，指向链表的下一个节点。头节点（Head Node）：链表的第一个节点。通常我们会使用一个指针来指向链表的头节点，以便对链表进行操作。尾节点（Tail Node）：链表的最后一个节点，尾节点的指针域通常指向 NULL，表示链表的结束。
链表的特点：
动态内存分配：链表在需要时动态分配节点，内存利用率高。插入和删除效率高：在链表中插入或删除一个节点，只需要改变相关节点的指针，不需要像数组一样移动元素。随机访问困难：由于链表的节点地址不连续，因此无法通过下标直接访问某个节点，需要从头节点开始依次遍历，访问效率较低。
链表的构成
链表由一个个节点构成，每个节点一般采用结构体的形式组织，例如：
typedef struct student
｛
int num；
char name[20]； // 数据域
struct student *next；//指针域
}STU;
2.创建链表
#include
#include
// 定义链表节点结构
struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
};
// 头节点指针，初始化为空
struct Node* head = NULL;
// 尾插法插入节点
void insertAtTail(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // 为新节点分配内存
newNode->data = value; // 设置新节点的数据
newNode->next = NULL; // 新节点的next指向NULL（因为它将成为尾节点）
if (head == NULL) { // 如果链表为空
head = newNode; // 新节点成为头节点
} else {
struct Node* temp = head;
while (temp->next != NULL) { // 遍历链表，找到尾节点
temp = temp->next;
}
temp->next = newNode; // 将尾节点的next指向新节点
}
}
// 打印链表
void printList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n"); // 表示链表结束
}
// 释放链表内存
void freeList() {
struct Node* temp;
while (head != NULL) {
temp = head; // 临时保存当前节点
head = head->next; // 移动头指针到下一个节点
free(temp); // 释放当前节点
}
}
int main() {
// 插入节点
insertAtTail(1);
insertAtTail(2);
insertAtTail(3);
insertAtTail(4);
// 打印链表
printf("链表内容：");
printList();
// 释放链表内存
freeList();
return 0;
}
3.链表的遍历
4.链表的查找
查找的过程就是从链表头节点开始，逐个访问节点的数据，并与目标数据进行比较，直到找到相匹配的节点或到达链表的末尾。
由于链表的节点地址不连续，因此无法通过索引直接访问某个位置的节点，必须从头节点开始依次遍历。
// 查找指定值的节点
struct Node* find(int target) {
struct Node* temp = head;
while (temp != NULL) { // 从头节点开始遍历链表
if (temp->data == target) { // 如果找到目标数据
return temp; // 返回该节点
}
temp = temp->next; // 否则继续下一个节点
}
return NULL; // 未找到返回NULL
}
5.链表的删除
链表的删除操作是指从链表中移除一个节点，并正确地更新链表结构，以确保链表的连续性。删除节点时，我们需要找到目标节点，并将其前一个节点的指针指向目标节点的下一个节点。根据删除位置的不同，链表删除操作通常分为以下几种情况：
删除头节点： 这是指删除链表的第一个节点（即头节点），需要更新头指针使其指向链表的第二个节点。删除指定位置的节点： 删除链表中的某个特定节点时，需要找到该节点和它的前一个节点，然后修改前一个节点的指针，使其绕过目标节点直接指向下一个节点。删除尾节点： 删除链表的最后一个节点，需要找到倒数第二个节点，并将其 next 指针设为 NULL。
// 删除指定值的节点
void deleteNode(int value) {
struct Node* temp = head;
struct Node* prev = NULL;
// 情况1：删除头节点
if (temp != NULL && temp->data == value) {
head = temp->next; // 更新头节点
free(temp); // 释放原头节点内存
return;
}
// 情况2：删除非头节点
while (temp != NULL && temp->data != value) {
prev = temp; // 保存当前节点为前一个节点
temp = temp->next; // 移动到下一个节点
}
// 如果链表中不存在该值
if (temp == NULL) return;
// 将前一个节点的 next 指针绕过当前节点，指向当前节点的下一个节点
prev->next = temp->next;
free(temp); // 释放当前节点内存
}
6.链表插入节点
#include
#include
// 定义链表节点结构
struct Node {
int data;
struct Node* next;
};
// 头节点指针
struct Node* head = NULL;
// 顺序插入节点
void insertInOrder(int value) {
// 创建新节点
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
// 情况1：插入到头部或链表为空
if (head == NULL || head->data >= value) {
newNode->next = head;
head = newNode;
} else {
// 情况2：插入到链表的中间或尾部
struct Node* temp = head;
// 找到第一个大于或等于新节点的前一个节点
while (temp->next != NULL && temp->next->data < value) {
temp = temp->next;
}
// 插入节点到合适的位置
newNode->next = temp->next;
temp->next = newNode;
}
}
// 打印链表内容
void printList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// 释放链表内存
void freeList() {
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
// 顺序插入节点
insertInOrder(3);
insertInOrder(1);
insertInOrder(5);
insertInOrder(2);
insertInOrder(4);
printf("按顺序插入后的链表：\n");
printList();
// 释放链表内存
freeList();
return 0;
}
7.双向链表
双向链表是一种链表结构，其中每个节点不仅包含指向下一个节点的指针 next，还包含指向前一个节点的指针 prev。这种结构允许我们在链表中双向遍历，即可以从头节点遍历到尾节点，也可以从尾节点遍历回头节点。
typedef struct Node {
int data; // 数据域
struct Node* next; // 指向下一个节点的指针
struct Node* prev; // 指向前一个节点的指针
} Node;
删除节点： 在双向链表中删除节点时，需要注意更新被删除节点的前后节点的指针。
void deleteNode(Node** head, int value) {
Node* temp = *head;
while (temp != NULL && temp->data != value) { // 找到要删除的节点
temp = temp->next;
}
if (temp == NULL) return; // 未找到节点
if (temp->prev != NULL) { // 更新前一个节点的 next 指针
temp->prev->next = temp->next;
} else { // 删除的是头节点
*head = temp->next;
}
if (temp->next != NULL) { // 更新后一个节点的 prev 指针
temp->next->prev = temp->prev;
}
free(temp); // 释放被删除节点的内存
}
插入节点： 双向链表的插入操作根据插入位置不同，头部、尾部、中间
// 插入节点到指定位置
void insertNode(Node** head, int value, int position) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = NULL;
// 情况1：插入到头部
if (position == 0 || *head == NULL) {
newNode->next = *head; // 新节点的next指向当前头节点
if (*head != NULL) {
(*head)->prev = newNode; // 当前头节点的prev指向新节点
}
*head = newNode; // 更新头节点为新节点
return;
}
Node* temp = *head;
int i;
// 找到插入位置的前一个节点
for (i = 0; i < position - 1 && temp->next != NULL; i++) {
temp = temp->next;
}
// 情况2：插入到尾部（position 超过链表长度时）
if (temp->next == NULL) {
temp->next = newNode; // 当前尾节点的next指向新节点
newNode->prev = temp; // 新节点的prev指向当前尾节点
}
// 情况3：插入到中间位置
else {
newNode->next = temp->next; // 新节点的next指向插入位置的下一个节点
newNode->prev = temp; // 新节点的prev指向插入位置的前一个节点
temp->next->prev = newNode; // 插入位置的下一个节点的prev指向新节点
temp->next = newNode; // 前一个节点的next指向新节点
}
}