数据结构单链表的基本操作（数据结构单链表的基本操作完整代码）

## 数据结构单链表的基本操作### 简介线性表是一种常见的数据结构，用于存储线性关系的数据元素。单链表作为线性表的一种链式存储结构，通过指针将各个节点连接起来，具有插入删除操作效率高，内存空间利用灵活等优点。本文将详细介绍单链表的基本操作，包括：- 创建 - 查找 - 插入 - 删除 - 遍历### 一、创建单链表创建单链表需要定义节点结构体和头指针：1.

定义节点结构体:

节点结构体包含数据域和指针域，数据域用于存储数据元素，指针域用于指向下一个节点。```c typedef struct Node {int data; // 数据域，存储数据元素struct Node

next; // 指针域，指向下一个节点 } Node; ```2.

定义头指针:

头指针指向链表的第一个节点，如果链表为空，则头指针指向NULL。```c Node

head = NULL; // 初始化头指针为空 ```创建单链表可以使用头插法或尾插法：-

头插法:

将新节点插入到链表头部，时间复杂度为O(1)。 -

尾插法:

将新节点插入到链表尾部，时间复杂度为O(n)，需要遍历整个链表。### 二、查找节点查找节点可以通过遍历链表，逐个比较节点数据域与目标值是否相等来实现。```c Node

searchNode(Node

head, int target) {Node

p = head;while (p != NULL) {if (p->data == target) {return p; // 找到节点，返回节点指针}p = p->next;}return NULL; // 未找到节点，返回NULL } ```### 三、插入节点插入节点需要先找到插入位置，然后修改节点指针指向：1.

找到插入位置:

可以根据节点索引或节点数据域查找插入位置。 2.

修改指针指向:

将新节点的指针域指向插入位置的下一个节点，将插入位置的前一个节点的指针域指向新节点。```c // 在指定位置pos插入节点 bool insertNode(Node

head, int pos, int data) {if (pos < 1) {return false; // 插入位置不合法}if (pos == 1) {// 在头部插入Node

newNode = (Node

)malloc(sizeof(Node));newNode->data = data;newNode->next = head;head = newNode;return true;}// 找到插入位置的前一个节点Node

p = head;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL) {return false; // 插入位置不合法}// 创建新节点并插入Node

newNode = (Node

)malloc(sizeof(Node));newNode->data = data;newNode->next = p->next;p->next = newNode;return true; } ```### 四、删除节点删除节点需要先找到要删除的节点，然后修改节点指针指向：1.

找到要删除的节点:

可以根据节点索引或节点数据域查找要删除的节点。 2.

修改指针指向:

将要删除节点的前一个节点的指针域指向要删除节点的下一个节点。 3.

释放内存:

释放要删除节点的内存空间。```c // 删除指定位置pos的节点 bool deleteNode(Node

head, int pos) {if (pos < 1) {return false; // 删除位置不合法}if (pos == 1) {// 删除头部节点if (head == NULL) {return false; // 链表为空}Node

temp = head;head = head->next;free(temp);return true;}// 找到要删除节点的前一个节点Node

p = head;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL || p->next == NULL) {return false; // 删除位置不合法}// 删除节点Node

temp = p->next;p->next = temp->next;free(temp);return true; } ```### 五、遍历单链表遍历单链表可以使用循环结构，从头节点开始，依次访问每个节点，直到访问到尾节点为止。```c void traverseList(Node

head) {Node

p = head;while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n"); } ```### 总结本文介绍了数据结构单链表的基本操作，包括创建、查找、插入、删除和遍历。单链表作为一种常用的数据结构，在实际应用中发挥着重要作用。熟练掌握单链表的基本操作，对于学习和应用数据结构和算法至关重要。

数据结构单链表的基本操作

简介线性表是一种常见的数据结构，用于存储线性关系的数据元素。单链表作为线性表的一种链式存储结构，通过指针将各个节点连接起来，具有插入删除操作效率高，内存空间利用灵活等优点。本文将详细介绍单链表的基本操作，包括：- 创建 - 查找 - 插入 - 删除 - 遍历

一、创建单链表创建单链表需要定义节点结构体和头指针：1. **定义节点结构体:** 节点结构体包含数据域和指针域，数据域用于存储数据元素，指针域用于指向下一个节点。```c typedef struct Node {int data; // 数据域，存储数据元素struct Node *next; // 指针域，指向下一个节点 } Node; ```2. **定义头指针:** 头指针指向链表的第一个节点，如果链表为空，则头指针指向NULL。```c Node *head = NULL; // 初始化头指针为空 ```创建单链表可以使用头插法或尾插法：- **头插法:** 将新节点插入到链表头部，时间复杂度为O(1)。 - **尾插法:** 将新节点插入到链表尾部，时间复杂度为O(n)，需要遍历整个链表。

二、查找节点查找节点可以通过遍历链表，逐个比较节点数据域与目标值是否相等来实现。```c Node* searchNode(Node *head, int target) {Node *p = head;while (p != NULL) {if (p->data == target) {return p; // 找到节点，返回节点指针}p = p->next;}return NULL; // 未找到节点，返回NULL } ```

三、插入节点插入节点需要先找到插入位置，然后修改节点指针指向：1. **找到插入位置:** 可以根据节点索引或节点数据域查找插入位置。 2. **修改指针指向:** 将新节点的指针域指向插入位置的下一个节点，将插入位置的前一个节点的指针域指向新节点。```c // 在指定位置pos插入节点 bool insertNode(Node *head, int pos, int data) {if (pos < 1) {return false; // 插入位置不合法}if (pos == 1) {// 在头部插入Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = head;head = newNode;return true;}// 找到插入位置的前一个节点Node *p = head;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL) {return false; // 插入位置不合法}// 创建新节点并插入Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = p->next;p->next = newNode;return true; } ```

四、删除节点删除节点需要先找到要删除的节点，然后修改节点指针指向：1. **找到要删除的节点:** 可以根据节点索引或节点数据域查找要删除的节点。 2. **修改指针指向:** 将要删除节点的前一个节点的指针域指向要删除节点的下一个节点。 3. **释放内存:** 释放要删除节点的内存空间。```c // 删除指定位置pos的节点 bool deleteNode(Node *head, int pos) {if (pos < 1) {return false; // 删除位置不合法}if (pos == 1) {// 删除头部节点if (head == NULL) {return false; // 链表为空}Node *temp = head;head = head->next;free(temp);return true;}// 找到要删除节点的前一个节点Node *p = head;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL || p->next == NULL) {return false; // 删除位置不合法}// 删除节点Node *temp = p->next;p->next = temp->next;free(temp);return true; } ```

五、遍历单链表遍历单链表可以使用循环结构，从头节点开始，依次访问每个节点，直到访问到尾节点为止。```c void traverseList(Node *head) {Node *p = head;while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n"); } ```

总结本文介绍了数据结构单链表的基本操作，包括创建、查找、插入、删除和遍历。单链表作为一种常用的数据结构，在实际应用中发挥着重要作用。熟练掌握单链表的基本操作，对于学习和应用数据结构和算法至关重要。