深入理解数据结构中的单向链表
————后面附有全部代码————
数据结构在计算机科学中扮演着重要角色，它用于组织和管理数据，提高数据的操作和访问效率。单向链表是一种简单但非常重要的数据结构。本文将深入探讨单向链表的定义、特点、基本操作。
一、什么是单向链表？
单向链表是一种线性数据结构，由一系列节点组成。每个节点包含两个部分：数据和指向下一个节点的引用（也称为指针）。节点之间通过这个引用连接在一起，形成链表结构。最后一个节点的引用指向空值，表示链表的结束。
二、单向链表的特点：
有空状态（只有头节点）但没有满状态（理论上是可以无限装节点）
优点
动态性：单向链表的长度可以动态地增加或减少，相比于静态数据结构，它更加灵活。
插入和删除操作高效：由于单向链表的节点包含了指向下一个节点的引用，插入和删除操作只需要修改节点的引用，时间复杂度为O(1)。
缺点
随机访问（修改和查询）低效：单向链表只能从头节点开始，按照顺序一个一个地访问节点，因此在查找特定节点时效率较低，时间复杂度为O(n)。
三、单向链表的基本操作：
①创建链表头节点
②判断链表是否为空
③插入元素（1.在头节点插入、2.在尾节点插入、3.在任意位置插入）
④删除元素（1.删除头节点、2.删除尾节点、3.删除任意节点）
⑤查找元素（1.按值查找下标、2. 按下标查找值）
⑥修改元素（1.按下标修改对应元素值、2.按原值修改新值）
⑦获取链表长度
⑧遍历链表
⑩清空表
四、分析
①创建链表头节点
②判断链表是否为空
③插入元素（1.在头节点插入、2.在尾节点插入、3.在任意位置插入）
1.在头节点插入
2.在尾节点插入
3.在任意位置插入
④删除元素（1.删除头节点、2.删除尾节点、3.删除任意节点）
1.删除头节点
2.删除尾节点
3.删除任意节点
⑤查找元素（1.按值查找、2. 按下标查找）
⑥修改元素（1.按下标修改对应元素值、2.按原值修改新值）
1.按下标修改对应元素值
2.按原值修改新值
⑦获取链表长度
⑧遍历链表
⑩清空表
全部代码
①接口文件linklist.h、②接口实现文件linklist.c、③主函数文件linklist_main.c
①linklist.h
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
#define typData int //宏定义数据类型，取别名为typData
// 链表节点结构体
typedef struct Node {
typData data;// 节点数据
int tail;//记录节点数
struct Node *next;//指向下一个节点的指针
} Linklist, *Plinklist;
// 创建链表
Plinklist createLinkedList(Plinklist *list);
// 判断链表是否为空
int isEmpty(Plinklist list);
// 在链表头部插入元素
void insertAtHead(Plinklist list, typData value);
// 在链表尾部插入元素
void insertAtTail(Plinklist list, typData value);
// 在指定位置插入元素
void insertAtPosition(Plinklist list, int position, typData value);
// 删除头节点
void deleteHead(Plinklist list);
// 删除尾节点
void deleteTail(Plinklist list);
// 删除指定位置的节点
void deleteAtPosition(Plinklist list, int position);
// 按值查找节点的位置
int findPositionByValue(Plinklist list, typData value);
// 按下标查找节点的值
int findValueByPosition(Plinklist list, int position);
// 修改指定位置的节点值
void modifyByPosition(Plinklist list, int position, typData value);
// 修改指定值的节点值
void modifyValue(Plinklist list, typData oidValue, typData newValue);
// 获取链表长度
int getLength(Plinklist list);
// 遍历链表并打印节点值
void traverse(Plinklist list);
// 清空链表
void clearList(Plinklist list);
#endif
②接口实现文件linklist.c
#include "linklist.h"
// 初始（创建）化链表
Plinklist createLinkedList(Plinklist *list) {
*list = (Plinklist)malloc(sizeof(Linklist)); // 创建头节点,头节点不存放数据
if((*list == NULL)){
perror("cretelinklist malloc");
}
(*list)->tail = 0;
(*list)->next = NULL; // 头节点的下一个节点置为空
return *list;
}
// 判断链表是否为空
int isEmpty(Plinklist list) {
if(list == NULL || list->tail == 0){
return 1;//真空
}else{
return 0;//非空
}
//return list->next == NULL;
}
// 在头部插入节点
void insertAtHead(Plinklist list, typData value) {
if(list == NULL){
puts("insert head arg err");
return ;
}
Plinklist newNode = (Plinklist)malloc(sizeof(Linklist)); // 创建新节点
if(newNode == NULL){
perror("insert head malloc");
return ;
}
newNode->data = value; // 设置新节点的数据值
newNode->next = list->next; // 新节点的下一个节点指向原头节点的下一个节点
list->next = newNode; // 头节点的下一个节点指向新节点，实现插入操作
list->tail++;
}
// 在尾部插入节点
void insertAtTail(Plinklist list, typData value) {
Plinklist newNode = (Plinklist)malloc(sizeof(Linklist)); // 创建新节点
newNode->data = value; // 设置新节点的数据值
Plinklist current = list; // 从头节点开始遍历链表，找到尾节点
while (current->next != NULL) {
current = current->next;
}
newNode->next = NULL; // 新节点的下一个节点置为空
current->next = newNode; // 尾节点的下一个节点指向新节点，实现插入操作
}
// 在任意位置插入节点
void insertAtPosition(Plinklist list, int position, typData value) {
if (position < 0) {
printf("无效的插入位置\n");
return;
}
Plinklist newNode = (Plinklist)malloc(sizeof(Linklist)); // 创建新节点
newNode->data = value; // 设置新节点的数据值
Plinklist current = list; // 从头节点开始遍历链表，找到插入位置的前一个节点
int count = 0;
while (current != NULL && count < position - 1) {
current = current->next;
count++;
}
if (current == NULL) {
printf("无效的插入位置\n");
return;
}
newNode->next = current->next; // 新节点的下一个节点指向插入位置的节点
current->next = newNode; // 插入位置的前一个节点的下一个节点指向新节点，实现插入操作
}
// 删除头节点
void deleteHead(Plinklist list) {
if (isEmpty(list)) {
printf("链表为空，无法删除头节点\n");
return;
}
Plinklist head = list->next; // 保存头节点的下一个节点
list->next = head->next; // 头节点的下一个节点指向头节点的下下一个节点，实现删除操作
free(head); // 释放头节点的内存
}
// 删除尾节点
void deleteTail(Plinklist list) {
if (isEmpty(list)) {
printf("链表为空，无法删除尾节点\n");
return;
}
Plinklist current = list; // 从头节点开始遍历链表，找到尾节点的前一个节点
while (current->next != NULL && current->next->next != NULL) {
current = current->next;
}
Plinklist tail = current->next; // 保存尾节点
current->next = NULL; // 尾节点的前一个节点的下一个节点置为空，实现删除操作
free(tail); // 释放尾节点的内存
}
// 删除任意位置的节点
void deleteAtPosition(Plinklist list, int position) {
if (isEmpty(list)) {
printf("链表为空，无法删除节点\n");
return;
}
Plinklist current = list; // 从头节点开始遍历链表，找到要删除节点的前一个节点
int count = 0;
while (current->next != NULL && count < position - 1) {
current = current->next;
count++;
}
if (current->next == NULL) {
printf("无效的删除位置\n");
return;
}
Plinklist nodeToDelete = current->next; // 保存要删除的节点
current->next = nodeToDelete->next; // 要删除节点的前一个节点的下一个节点指向要删除节点的后一个节点，实现删除操作
free(nodeToDelete); // 释放要删除节点的内存
}
// 按值查找元素的下标
int findPositionByValue(Plinklist list, typData value) {
Plinklist current = list->next; // 从第一个节点开始遍历链表
int position = 0;
while (current != NULL) {
if (current->data == value) {
return position; // 找到节点的数据值等于目标值，返回节点的下标
}
current = current->next;
position++;
}
return -1; // 未找到目标值，返回-1
}
// 按下标查找元素的值
int findValueByPosition(Plinklist list, int position) {
Plinklist current = list->next; // 从第一个节点开始遍历链表
int count = 0;
while (current != NULL && count < position) {
current = current->next;
count++;
}
if (current == NULL) {
printf("无效的下标\n");
return -1;
}
return current->data; // 返回找到的节点的数据值
}
// 修改指定位置的节点值
void modifyByPosition(Plinklist list, int position,typData value){
if (isEmpty(list)) {
printf("链表为空，无法修改元素\n");
return;
}
Plinklist current = list->next; // 从第一个节点开始遍历链表
int count = 0;
while (current != NULL && count < position) {
current = current->next;
count++;
}
if (current == NULL) {
printf("无效的下标\n");
return;
}
current->data = value; // 修改节点的数据值
}
// 修改指定值的节点值
void modifyValue(Plinklist list, typData oldValue, typData newValue) {
if (isEmpty(list)) {
printf("链表为空，无法修改节点值\n");
return;
}
Plinklist current = list->next; // 从第一个节点开始遍历链表
while (current != NULL) {
if (current->data == oldValue) {
current->data = newValue; // 找到节点的数据值等于旧值，更新节点的数据值为新值
return;
}
current = current->next;
}
printf("未找到目标值\n");
}
// 获取链表长度
int getLength(Plinklist list) {
if(list == NULL){
puts("getLength arg err");
return -1;
}
if(isEmpty(list)){
puts("表为空,长度为0");
return -1;
}
Plinklist current = list->next; // 从第一个节点开始遍历链表
return list->tail;
}
// 遍历链表
void traverse(Plinklist list) {
if(list == NULL){
puts("traverse arg eer");
return ;
}
if (isEmpty(list)) {
printf("链表为空\n");
return;
}
Plinklist current = list->next; // 从第一个节点开始遍历链表
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 清空链表并释放内存
void clearList(Plinklist list) {
Plinklist current = list->next; // 从第一个节点开始遍历链表
while (current != NULL) {
Plinklist temp = current;
current = current->next;
free(temp); // 释放节点的内存
}
list->next = NULL; // 头节点的下一个节点置为空，链表清空
}
③主函数文件linklist_main.c文章来源：https://www.toymoban.com/news/detail-796461.html
#include "linklist.h"
#include "linklist.c"
int main() {
Plinklist list;
createLinkedList(&list);
int choice, value, position, oldValue, newValue;
while (1) {
printf("\n*****************************链表操作菜单*****************************\n");
printf("1. 在头部插入元素 2. 在尾部插入元素 3. 在任意位置插入元素\n");
printf("4. 删除头节点 5. 删除尾节点 6. 删除任意位置的节点\n");
printf("7. 按值查找元素的位置 8. 按位置查找元素的值 9. 修改指定位置的节点值\n");
printf("10. 修改指定值的节点值 11. 获取链表长度 12. 遍历链表\n");
printf("13. 清空链表并退出程序\n");
printf("*********************************************************************\n");
printf("请输入操作编号：");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("请输入要插入的元素值：");
scanf("%d", &value);
insertAtHead(list, value);
traverse(list);
break;
case 2:
printf("请输入要插入的元素值：");
scanf("%d", &value);
insertAtTail(list, value);
traverse(list);
break;
case 3:
printf("请输入要插入的位置下标：");
scanf("%d", &position);
printf("请输入要插入的元素值：");
scanf("%d", &value);
insertAtPosition(list, position, value);
traverse(list);
break;
case 4:
deleteHead(list);
traverse(list);
break;
case 5:
deleteTail(list);
traverse(list);
break;
case 6:
printf("请输入要删除的位置下标：");
scanf("%d", &position);
deleteAtPosition(list, position);
traverse(list);
break;
case 7:
printf("请输入要查找的元素值：");
scanf("%d", &value);
position = findPositionByValue(list, value);
if (position != -1) {
printf("元素值 %d 的位置下标是：%d\n", value, position);
}
break;
case 8:
printf("请输入要查找的位置下标：");
scanf("%d", &position);
value = findValueByPosition(list, position);
if (value != -1) {
printf("位置下标 %d 上的元素值是：%d\n", position, value);
}
break;
case 9:
printf("请输入要修改的位置下标：");
scanf("%d", &position);
printf("请输入修改后的元素值下标：");
scanf("%d", &value);
modifyByPosition(list, position, value);
traverse(list);
break;
case 10:
printf("请输入要修改的元素值：");
scanf("%d", &oldValue);
printf("请输入修改后的元素值：");
scanf("%d", &newValue);
modifyValue(list, oldValue, newValue);
traverse(list);
break;
case 11:
printf("链表的长度是：%d\n", getLength(list));
break;
case 12:
traverse(list);
break;
case 13:
clearList(list);
exit(0);
default:
printf("无效的操作编号！\n");
break;
}
}
return 0;
}
五、结论：
单向链表作为一种常见的数据结构，在计算机科学和软件开发中有着广泛的应用。通过理解单向链表的定义、特点和基本操作，我们可以更好地应用它来解决实际问题。文章来源地址https://www.toymoban.com/news/detail-796461.html
到了这里，关于四、数据结构——单向链表的基本操作详解：创建、插入（头插法、尾插法、任意点插法）、删除（头删法、尾删法、任意位置删法）、查询（按值查下标、按下标查值）、遍历链表和清空链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
