C语言：数据结构链表基本操作（增、删、改、查、遍历）

一、数据结构-链表介绍

链表：在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由一系列节点（链表中每一个元素称为节点/结点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

链表可以分为单向链表和双向链表两种形式。在单向链表中，每个节点只保存指向下一个节点的指针，而在双向链表中，每个节点同时保存指向上一个节点和下一个节点的指针。

二、链表操作

插入：在链表的任意位置插入一个节点；删除：从链表中删除一个节点；查找：在链表中查找指定的数据；修改：修改链表中节点的数据；遍历：按照顺序依次访问链表中的每个节点。

三、创建和释放

1. 创建节点

// 创建一个新节点Node* createNode(ElemType data){Node* newNode = (Node*)malloc(sizeof(Node));if(newNode != NULL){newNode -> data = data; // 设置数据newNode -> next = NULL; // 新节点的下一个节点为空}return newNode;}

2. 创建空链表

// 创建一个空链表linkedList* createLinkedList(){linkedList* list = (linkedList*)malloc(sizeof(linkedList));if(list != NULL){list -> head = NULL; // 头指针为空list -> length = 0; // 链表长度为0}return list;}

3. 释放空间

// 释放链表的内存void freeLinkedList(linkedList* list){if(list == NULL)return;Node* current = list -> head;while(current != NULL){Node* temp = current;current = current -> next;free(temp); // 释放节点内存}free(list); // 释放链表内存}

四、链表操作各部分代码实现

1. 插入

// 在链表的指定位置插入节点void insertNode(linkedList* list, int pos, ElemType data){if(list == NULL || pos < 0 || pos > list -> length)return;Node* newNode = createNode(data); // 创建新节点if(newNode == NULL)return;if(pos == 0){newNode -> next = list -> head; // 将新节点插入到链表头部list -> head = newNode; // 更新头指针}else{Node* current = list -> head;for(int i =0; i < pos - 1; i++) // 找到插入位置的前一个节点{current = current -> next;}newNode -> next = current -> next; // 新节点指向原来位置的节点current -> next = newNode; // 前一个节点指向新节点}list -> length ++; // 链表长度加 1}

2. 删除

// 删除链表的指定位置的节点void deleteNode(linkedList* list, int pos){if(list == NULL || pos < 0 || pos >= list -> length) return;Node* temp;if(pos == 0){temp = list -> head; // 保存头节点list -> head = list -> head -> next; // 更新头指针}else{Node* current = list -> head;for(int i = 0; i < pos - 1; i++) // 找到要删除节点的前一个节点{current = current -> next;}temp = current -> next; // 保存要删除的节点current -> next = temp -> next; // 前一个节点指向要删除节点的下一个节点}free(temp); // 释放节点内存list -> length--; // 链表长度减1}

3. 修改

// 查找链表中指定数据的位置int findNode(linkedList* list, ElemType data){if(list == NULL)return -1;Node* current = list -> head;int pos = 0;while(current != NULL) // 遍历链表{if(current -> data == data) // 找到数据相同的节点return pos;current = current -> next;pos++;}return -1; // 数据不存在}

4. 查找

// 查找链表中指定数据的位置int findNode(linkedList* list, ElemType data){if(list == NULL)return -1;Node* current = list -> head;int pos = 0;while(current != NULL) // 遍历链表{if(current -> data == data) // 找到数据相同的节点return pos;current = current -> next;pos++;}return -1; // 数据不存在}

5. 遍历

// 遍历，打印链表的所有节点数据void printLinkedList(linkedList* list){if(list == NULL)return;Node* current = list -> head;while(current != NULL){printf("%d ",current -> data);current = current -> next;}printf("\n");}

五、完整代码

#include <stdio.h>#include <stdlib.h>typedef int ElemType;// 定义链表节点typedef struct Node{ElemType data;struct Node* next;}Node; // 定义链表结构typedef struct{Node* head; // 头指针int length; // 链表长度}linkedList;// 创建一个新节点Node* createNode(ElemType data){Node* newNode = (Node*)malloc(sizeof(Node));if(newNode != NULL){newNode -> data = data; // 设置数据newNode -> next = NULL; // 新节点的下一个节点为空}return newNode;}// 创建一个空链表linkedList* createLinkedList(){linkedList* list = (linkedList*)malloc(sizeof(linkedList));if(list != NULL){list -> head = NULL; // 头指针为空list -> length = 0; // 链表长度为0}return list;}// 在链表的指定位置插入节点void insertNode(linkedList* list, int pos, ElemType data){if(list == NULL || pos < 0 || pos > list -> length)return;Node* newNode = createNode(data); // 创建新节点if(newNode == NULL)return;if(pos == 0){newNode -> next = list -> head; // 将新节点插入到链表头部list -> head = newNode; // 更新头指针}else{Node* current = list -> head;for(int i =0; i < pos - 1; i++) // 找到插入位置的前一个节点{current = current -> next;}newNode -> next = current -> next; // 新节点指向原来位置的节点current -> next = newNode; // 前一个节点指向新节点}list -> length ++; // 链表长度加 1}// 删除链表的指定位置的节点void deleteNode(linkedList* list, int pos){if(list == NULL || pos < 0 || pos >= list -> length) return;Node* temp;if(pos == 0){temp = list -> head; // 保存头节点list -> head = list -> head -> next; // 更新头指针}else{Node* current = list -> head;for(int i = 0; i < pos - 1; i++) // 找到要删除节点的前一个节点{current = current -> next;}temp = current -> next; // 保存要删除的节点current -> next = temp -> next; // 前一个节点指向要删除节点的下一个节点}free(temp); // 释放节点内存list -> length--; // 链表长度减1}// 更新链表的指定位置的节点数据void updateNode(linkedList* list, int pos, ElemType data){if(list == NULL || pos < 0 || pos >= list -> length) return;Node* current = list -> head;for(int i = 0; i < pos; i++) // 找到要更新的节点{current = current -> next;}current -> data = data; // 更新节点数据}// 查找链表中指定数据的位置int findNode(linkedList* list, ElemType data){if(list == NULL)return -1;Node* current = list -> head;int pos = 0;while(current != NULL) // 遍历链表{if(current -> data == data) // 找到数据相同的节点return pos;current = current -> next;pos++;}return -1; // 数据不存在}// 遍历，打印链表的所有节点数据void printLinkedList(linkedList* list){if(list == NULL)return;Node* current = list -> head;while(current != NULL){printf("%d ",current -> data);current = current -> next;}printf("\n");}// 释放链表的内存void freeLinkedList(linkedList* list){if(list == NULL)return;Node* current = list -> head;while(current != NULL){Node* temp = current;current = current -> next;free(temp); // 释放节点内存}free(list); // 释放链表内存}int main(){linkedList* list = createLinkedList(); // 创建一个链表insertNode(list, 0, 10);insertNode(list, 1, 20);insertNode(list, 2, 30);printLinkedList(list);updateNode(list, 1, 25);printLinkedList(list);deleteNode(list, 2);printLinkedList(list);int pos = findNode(list, 30);printf("pos = %d\n", pos);freeLinkedList(list);return 0;}