• 【数据结构】单链表

    在这里插入图片描述

    前言
    单链表是一种数据结构，其中每个元素（通常称为节点）都包含一个数据字段和一个指向下一个节点的指针。

    文章目录

    一、初识单链表

    单链表就像一段火车，每节车厢都由前面一节车厢牵引，单链表的其中一个节点可以看作一节车厢，车厢内的货物就是节点存储的数据，而车厢的挂钩就是指针，这个“指针”可以由前面一节车厢找到后面一节车厢，但是不能通过后面一节车厢找到前面一节车厢。

    在这里插入图片描述

    单链表通常由结构体（struct）和指针来实现：

    //在头文件中定义
typedef struct Node {
    int data;           // 节点存储的数据
    struct Node* next;  // 指向下一个节点的指针
};

    • 1
    • 2
    • 3
    • 4
    • 5

    二、单链表的操作

    2.1 初始化链表

    头文件中定义链表

    typedef int dataType;//将类型转换成dataType，方便修改，使用不同数据

typedef struct Node {
    int data;           // 节点存储的数据
    struct Node* next;  // 指向下一个节点的指针
}Node;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    主函数内创建头节点
    在这里插入图片描述

    Node* head = NULL;//创建一个头节点，这里不使用哨兵位

    • 1

    使用哨兵节点的好处：

    1. 简化代码：在插入和删除操作时，不需要单独处理链表头。这使得代码更简洁、易读和易于维护。

    2. 统一处理：由于所有节点（包括链表头）现在都有一个前置节点（即哨兵节点），一些操作可以更统一地执行。

    3. 减少错误：代码简化通常会降低出错的可能性。

    4. 方便返回新的头节点：在某些链表操作（如排序、反转等）后，链表的实际头节点可能会改变。使用哨兵节点可以很容易地找到新的头节点，即哨兵节点的 next 指针所指向的节点。

    用于创建新节点的函数，在插入操作中可以方便调用

    Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        perror("Error in createNode\n");//createNode函数发生错误
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    2.2 插入操作

    通常插入操作有头插，尾插和指定位置插入

    头插

    void insertHead(Node** head,dataType data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        perror("Error in insertNode");//insertNode函数发生错误
        return NULL;
    }
    newNode->next = *head;
    *head = newNode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    尾插

    void insertTail(Node** head, dataType data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        perror("Error in insertTail");//insertTail函数发生错误
        return NULL;
    }

    //当仅有head一个头节点时
    if (*head == NULL) {  
        *head = newNode;
        return;
    }
    Node* temp = *head;   //始终保持head指针不变

    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    指定位置插入

    //指定位置插入,第一个节点下标为1，头节点为0
void insertPosition(Node** head, dataType data, int position) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        perror("Error in insertTail");
        return;
    }

    if (position < 1) {  //位置错误
        printf("Invalid position!\n");
        return;
    }

    //头插
    if (position == 1) {  
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* temp = *head;

    for (int i = 1; i < position - 1; i++) {  
        if (temp == NULL) {
            printf("Position out of bounds!\n"); //位置越界
            return;
        }
        temp = temp->next;  //最后一次赋值，temp来到指定位置的前一位
    }

    
    if (temp == NULL) {
        printf("Position out of bounds!\n");  
        return;
    }

    newNode->next = temp->next; //temp->next是数据插入指定位置后的后一节点的地址
    temp->next = newNode;  //将节点地址newNodef赋给前一位节点的next
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    2.3 删除操作

    删除链表第一个有效节点

    void deleteHead(Node** head) {
    if (*head == NULL) {
        return;
    }

    Node* temp = *head; //*head第一个节点地址
    *head = (*head)->next; 
    free(temp);//释放空间
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    删除链表尾部节点

    void deleteTail(Node** head) {
    if (*head == NULL) {
        return;
    }
    Node* temp = *head;
    Node* prev = NULL; //prev尾节点的前一节点
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }
    if (prev != NULL) {  //prev为空说明仅有head一个头节点
        prev->next = NULL;
    }
    else {
        *head = NULL;
    }
    free(temp);//释放空间
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    删除链表指定位置的节点

    void deleteIndex(Node** head, int index) {
    if (index < 1) {
        printf("Invalid index. Must be greater than 0.\n");
        return;
    }

    if (index == 1) {
        deleteHead(head);
        return;
    }

    Node* temp = *head;
    Node* prev = NULL; //prev目标节点前一个节点

    for (int i = 1; i < index; ++i) {
        if (temp == NULL) {
            printf("Index out of range.\n");//超出范围
            return;
        }
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Index out of range.\n");//超出范围
        return;
    }

    prev->next = temp->next;
    free(temp);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    2.4 打印链表

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    2.5 查找节点

    Node* searchNode(Node** head, int data) {
    Node* temp = *head;

    int count = 1;
    while (temp != NULL) {
        if (temp->data == data) {
            printf("在第%d个节点\n", count);
            return temp;  // 返回找到的节点
        }
        temp = temp->next;
        count++;
    }
    printf("没找到\n");
    return NULL;  // 返回NULL表示没找到
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.6 修改节点数据

    void updateNode(Node** head, int newData,int index) {
    Node* temp = *head;

    int count = 1;
    while (temp != NULL) {     
        if (count == index) {
            temp->data = newData;
            return;
        }
        temp = temp->next;
        count++;
    }
    printf("访问越界\n");
    return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.7 销毁链表并释放内存

    void destroyList(Node** head) {
    Node* cur = *head;
    Node* nextNode;

    while (cur != NULL) {
        nextNode = cur->next;
        free(cur);
        cur = nextNode;
    }

    *head = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    三、完整代码

    list.h

    #include
#include
typedef int dataType;

typedef struct Node {
    int data;           // 节点存储的数据
    struct Node* next;  // 指向下一个节点的指针
}Node;


// 创建新节点
Node* createNode(int data);
//头插
void insertHead(Node** head, dataType data);
//尾插
void insertTail(Node** head, dataType data);
//指定插入
void insertPosition(Node** head, dataType data, int position);
//删除链表头部节点
void deleteHead(Node** head);
// 删除链表尾部节点
void deleteTail(Node** head);
// 删除链表指定位置的节点
void deleteIndex(Node** head, int index);

// 打印链表
void printList(Node** head);

// 修改节点数据
void updateNode(Node** head, int newData, int index);

// 查找节点
Node* searchNode(Node** head, int data);

// 销毁链表并释放内存
void destroyList(Node** head);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    list.c

    #include"list.h"

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        perror("Error in createNode\n");//createNode函数发生错误
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 头部插入节点
void insertHead(Node** head,dataType data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        perror("Error in insertHead");//insertHead函数发生错误
        return ;
    }
    newNode->next = *head;
    *head = newNode;
}

//尾插
void insertTail(Node** head, dataType data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        perror("Error in insertTail");//insertTail函数发生错误
        return ;
    }

    //当仅有head一个头节点时
    if (*head == NULL) {  
        *head = newNode;
        return;
    }
    Node* temp = *head;   //始终保持head指针不变

    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

//指定位置插入,第一个节点下标为1，头节点为0
void insertPosition(Node** head, dataType data, int position) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        perror("Error in insertTail");
        return;
    }

    if (position < 1) {  //位置错误
        printf("Invalid position!\n");
        return;
    }

    //头插
    if (position == 1) {  
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* temp = *head;

    for (int i = 1; i < position - 1; i++) {  
        if (temp == NULL) {
            printf("Position out of bounds!\n"); //位置越界
            return;
        }
        temp = temp->next;  //最后一次赋值，temp来到指定位置的前一位
    }

    
    if (temp == NULL) {
        printf("Position out of bounds!\n");  
        return;
    }

    newNode->next = temp->next; //temp->next是数据插入指定位置后的后一节点的地址
    temp->next = newNode;  //将节点地址newNodef赋给前一位节点的next
}

// 删除链表第一个有效节点
void deleteHead(Node** head) {
    if (*head == NULL) {
        return;
    }

    Node* temp = *head; //*head第一个节点地址
    *head = (*head)->next; 
    free(temp);
}

// 删除链表尾部节点
void deleteTail(Node** head) {
    if (*head == NULL) {
        return;
    }
    Node* temp = *head;
    Node* prev = NULL; //prev尾节点的前一节点
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }
    if (prev != NULL) {  //prev为空说明仅有head一个头节点
        prev->next = NULL;
    }
    else {
        *head = NULL;
    }
    free(temp);
}

// 删除链表指定位置的节点
void deleteIndex(Node** head, int index) {
    if (index == 1) {  
        deleteHead(head);
        return;
    }

    Node* temp = *head;
    Node* prev = NULL; //prev目标节点前一个节点
    for (int i = 1; i < index; i++) {
        if (temp == NULL) {
            printf("Index out of range\n");  //超出范围
            return;
        }
        prev = temp;
        temp = temp->next;
    }

    if (prev != NULL && temp !=NULL) {
        prev->next = temp->next;
        free(temp);
    }
    else {
        printf("Index out of range or prev is NULL.\n");
    }

}

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

// 查找节点
Node* searchNode(Node** head, int data) {
    Node* temp = *head;

    int count = 1;
    while (temp != NULL) {
        if (temp->data == data) {
            printf("在第%d个节点\n", count);
            return temp;  // 返回找到的节点
        }
        temp = temp->next;
        count++;
    }
    printf("没找到\n");
    return NULL;  // 返回NULL表示没找到
}

// 修改节点数据
void updateNode(Node** head, int newData,int index) {
    Node* temp = *head;

    int count = 1;
    while (temp != NULL) {     
        if (count == index) {
            temp->data = newData;
            return;
        }
        temp = temp->next;
        count++;
    }
    printf("访问越界\n");
    return;
}

// 销毁链表并释放内存
void destroyList(Node** head) {
    Node* cur = *head;
    Node* nextNode;

    while (cur != NULL) {
        nextNode = cur->next;
        free(cur);
        cur = nextNode;
    }

    *head = NULL;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203

    main.c

    #include"list.h"

int main() {
	Node* head = NULL;//创建一个头节点，说明这是一个带有头节点的单链表
	insertHead(&head,2);//在头部插入2，2->
	insertHead(&head,1);//在头部插入1, 1->2->
	insertTail(&head,3);//尾部插入3，1->2->3->
	insertTail(&head,5);//尾部插入5，1->2->3->5->
	insertPosition(&head,4,4);//第四个节点插入4，1->2->3->4->5->
	printList(&head);//1->2->3->4->5->
	
	searchNode(&head,3);//查找3在哪个节点
	printList(&head);

	updateNode(&head, 4, 3);//将第三个节点改为4，1->2->4->4->5->
	printList(&head);

	deleteHead(&head);//删除头节点，2->3->4->5->
	deleteTail(&head);//删除尾节点，2->3->4->
	deleteIndex(&head, 2);//删除第二个节点，2->4->
	
	destroyList(&head);


	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    在这里插入图片描述
    如果你喜欢这篇文章，点赞👍+评论+关注⭐️哦！
    欢迎大家提出疑问，以及不同的见解。

  • 相关阅读:
    Mysql深入优化 (一) --- 索引、视图、存储过程、触发器
    计算机网络--物理层练习题
    linux 在文件夹里搜索哪个文件包含一段内容
    Vue--Router--解决多路由复用同一组件页面不刷新问题
    JAVA计算机毕业设计手办销售系统源码+系统+mysql数据库+lw文档
    3D封装技术发展
    电脑快捷键
    CF1559E Mocha and Stars（dp+莫比乌斯反演）
    ​打造企业自己代码规范IDEA插件（中）
    字符串的使用方法之startwith()-以XX开头、endsWith()-以XX结尾、trim()-删除两端空格
  • 原文地址：https://blog.csdn.net/weixin_73551991/article/details/134021084