单链表的基本操作

article/2025/10/7 7:49:44

文章目录

  • 单链表(含头结点)
    • 一、单链表
    • 二、单链表的创建(有头结点)
    • 三、单链表的结点查找(按位置查找)
    • 四、单链表的插入操作
    • 五、链表的删除操作
    • 六、链表的逆置
    • 七、链表的置空
    • 八、链表的销毁

单链表(含头结点)

一、单链表

  • 1.1 关于单链表
    单链表是一种采用链式存储的线性结构，其数据元素是由结点结构体组成，结点包括数据域和指针域。
    相较于顺序表来说，单链表解脱了需要整片存储空间和存储空间大小固定的束缚；解决了插入、删除操作时对其他元素的操作问题。
    相应的对于顺序表来说，单链表的整体存储空间大小需求更多；同时查询数据元素的方法也较单一。
  • 2.1 单链表的结构体
    单链表的结构体是由数据域和指针域组成的，数据域存放要保存的数据，指针域保存下一个结点的地址(下一个结点为空，保存NULL)。
typedef struct LNode
{int data;struct LNode *next;
}linklist_t, LNode_t;

二、单链表的创建(有头结点)

  • 2.1 传参的方式创建单链表
void Create_Linklist(linklist_t **L){//先判断传入的参数是否正确if(NULL == L){printf("Parameter error\n");return;}//创建头结点*L = (linklist_t *)malloc(sizeof(linklist_t);if(NULL == *L){printf("Space request error\n");return;}(*L)->data = -1;(*L)->next = NULL;return;
}
  • 2.2 指针函数的方式创建单链表
linklist *Create_Linklist(void){linklist *L = (linklist *)malloc(sizeof(linklist));if(NULL == L){printf("Space request error\n");return NULL;}L->data = -1;L->next = NULL;return L;
}
  • 上述两种方法的区别
    在这里插入图片描述
  • 上述的两种方法仅仅是创建了带有头结点的单链表，想要得到想要的单链表还需要使用单链表的插入函数。

三、单链表的结点查找(按位置查找)

  • 3.1 单链表中元素的个数
    功能：统计单链表中元素个数
    参数：单链表的头结点
    返回值：成功返回单链表中元素个数；失败返回-1
//用于记录单链表中元素的个数
int Length_Linklist(linklist_t *L){//判断参数是否正确if(NULL == L){printf("Parameter error\n");return -1;}//num记录元素个数int num = 0;if(NULL == L->next){return num;}LNode_t *Q = L->next; num = 1;while(NULL != Q->next){Q = Q->next;num++;}return num;
}
  • 3.2 单链表的查找
    功能：查找单链表的指定结点的前一个结点
    参数：单链表的头指针、需要查找结点的位置参数
    返回值：成功返回的为该结点的前一个结点的结点指针；失败返回NULL
//如果第一个有效结点算作第 0 位则pos不用改动，如果第一个有效结点算作第 1 位，则pos = pos - 1;
//返回的为该结点的前一个结点的结点指针，主要也是为了方便之后的插入和删除操作
LNode_t *PosFind_Linklist(linklist_t *L, int pos){//判断参数是否正确if(NULL == L){printf("Parameter error\n");return NULL;}//注意这里是 "pos > num"，可能会返回的是尾结点(pos = num)，\这样写也主要是为了便于之后插入的方便，若只想查找元素数据可在该函数前加一个判断int Length_Linklist(L);if((pos < 0) || (pos > num)){printf("Parameter error\n");return NULL;}num = 0;LNode_t *N = L;while(num != pos){num++;N = N->next;}return N;
}

四、单链表的插入操作

  • 4.1 头插法
int HeadInsert_Linklist(linklist_t *L, int value){//判断参数是否正确if(NULL == L){printf("Parameter error\n");return 0;}//创建结点LNode_t *N = (LNode *)malloc(sizeof(LNode_t));N->data = value;N->next = NULL;//插入到头结点之后N->next = L->next;L->next = N;return 0;
}
  • 4.2 尾插法
int TailInsert_Linklist(linklist_t *L, int value){//判断参数是否正确if(NULL == L){printf("Parameter error\n");return -1;}//创建结点LNode_t *N = (LNode *)malloc(sizeof(LNode_t));N->data = value;N->next = NULL;//创建尾指针LNode_t *Q = L;//遍历找到链尾while(NULL != Q->next){Q = Q->next;}//链尾元素之后插入新结点Q->next = N;Q = Q->next;
}
  • 4.3 指定位置插入
    功能：将新结点插入到指定位置
    参数：单链表的头指针、新结点的位置、新结点数据域的值
    返回值：成功返回0；失败返回-1
int PosInsert_Linklist(linklist_t *L, int pos, int value){//如果第一个有效结点算作第 0 位则pos不用改动，如果第一个有效结点算作 1 位，则pos = pos - 1;//寻找插入位置的前一个结点LNode_t *Q = PosFind_Linklist(L, pos);//创建结点LNode_t *N = (LNode_t *)malloc(sizeof(LNode_t));if(NULL == N){printf("Space request error\n");return -1;}N->data = value;N->next = NULL;//插入新结点N->next = Q->next;Q->next = N;return 0;
}

如果要是一次性成型的话可以将链表的创建和插入写在一起，如果需要后续进行增删改建议还是分开写。然后设置 mode_flag 进行快速插入、删除或者单个插入、删除。

五、链表的删除操作

  • 5.1 链表的头删法
int HeadDelete_Linklist(linklist_t *L){//判断参数是否正确if(NULL == L){printf("Parameter error\n");return -1;}if(0 == Length_Linklist(L)){           // Length_Linklist() 函数在上文“3.1 单链表中元素的个数”中printf("linklist is empty\n");return -1;}//头删int value = 0;LNode_t *N = L->next;L->next = N->next;N->next = NULL;value = N->data;free(N);N = NULL;return value;
}
  • 5.2 链表的尾删法
int TailDelete_Linklist(linklist_t *L){//判断参数是否正确if(NULL == L){printf("Parameter error\n");return -1;}if(0 == Length_Linklist(L)){            /// Length_Linklist() 函数在上文“3.1 单链表中元素的个数”中printf("linklist is empty\n");return -1;}//每次都要遍历到尾部结点的前一个结点int i = 0；int num = Length_Linklist(L);          LNode_t *N = L;while(i != num-1){i++;N = N->next;}//尾删int value = 0;value = N->next->data;free(N->next);N = NULL;return value;
}
  • 5.3 任意位置删除
int PosDelete_Linklist(linklist *L, int pos){//如果第一个有效结点算作第 0 位则pos不用改动，如果第一个有效结点算作 1 位，则pos = pos - 1;//判断参数是否正确int num = Length_Linklist(L);           // Length_Linklist() 函数在上文“3.1 单链表中元素的个数”中if((pos < 0) || (pos >= num)){printf("Parameter error\n");return -1;}//遍历找到 pos 位置的前一个结点LNode_t *N = PosFind_Linklist(L, pos);//删除int value = 0;LNode_t *P = N->next;value = P->data;N->next = p->next;P->next = NULL;free(P);P = NULL;return value;
}

六、链表的逆置

归根结底就是将单链表头删/尾删的方式出单链表表，然后再头插/尾插的方式入另一个单链表。
当然一个单链表也是可以实现链表的逆置的，逆置的时候第1个结点要到表尾，可以设置一个指针一直指向这个结点，对该结点之后的结点进行删除然后头插，直到后续无结点逆置完成。

  • 6.1 单一链表
int Reverse_Linklist(linklist_t *L){if(NULL == L){printf("Parameter error\n");return -1;}if(NULL == L->next){printf("linklist is empty\n");return 0;}LNode_t *N = L->next;LNode_t *Q = N;while(NULL != N->next){Q = N->next;N->next = Q->next;Q->next = L->next;L->next = Q;}return 0;
}
  • 6.2 两个链表
int Reverse_Linklist(linklist **L){if(NULL == L || NULL == *L){printf("Parameter error\n");return -1;}if(NULL == (*L)->next){printf("linklist is empty\n");return 0;}LNode_t *N = L;linklist *Q = NULL;while(NULL != L->next){N = L->next;L->next = N->next;N->next = Q->next;Q->next = N;}(*L) = Q;Q = NULL;return 0;
}

七、链表的置空

简单来说就是将单链表除头结点之外的结点全部删除，其实现方式无非就是当链表不为空的时候就循环头删结点，直到链表为空。

int SetEmpty_Linklist(linklist_t *L){if(NULL == L){printf("Parameter error\n");return -1;}if(NULL == L->next){printf("Linklist is empty\n");return 0;}while(NULL != L->next){HeadDelete_Linklist(L);}return 0;
}

八、链表的销毁

有了上述的基础，离链表的销毁其实只差删除头结点和将头结点指针指向NULL。

int Free_Linklist(linklist_t **L){if(NULL == *L){printf("Parameter error\n");return -1;}if(NULL != (*L)->next){SetEmpty_Linklist(*L);}free(*L);(*L) = NULL;return 0; 
}

http://chatgpt.dhexx.cn/article/xftyB16m.shtml

相关文章

单链表的操作（超详细），保证你看完不后悔

单链表的操作（超详细），保证你看完不后悔

&#x1f30d;新人小白的博客 ⌛️希望大家多多关注 &#x1f331;一起加油&#xff0c;共同成长 &#x1f383;以后会经常更新哒~&#x1f648; ⭐️个人主页&#xff1a; 收藏加关注&#xff0c;永远不迷路~⭐️ 数据结构系列&#x1f440; 一&#xff1a;顺序表的操作&…
阅读更多...
C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

C语言单链表实现初始化、创建、增、删、查等基本操作 #include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int ElemType; //定义单链表结构 typedef struct Node {ElemType data;//数据域struct Node *next;//指针域&#xff0c;指向下一…
阅读更多...
java线程池的工作原理_JAVA线程池原理详解一

java线程池的工作原理_JAVA线程池原理详解一

线程池的优点 1、线程是稀缺资源，使用线程池可以减少创建和销毁线程的次数，每个工作线程都可以重复使用。 2、可以根据系统的承受能力，调整线程池中工作线程的数量，防止因为消耗过多内存导致服务器崩溃。 线程池的创建 1 public ThreadPoolExecutor(int corePoolSize, 2 in…
阅读更多...
线程池原理解析

线程池原理解析

1、为什么要用线程池&#xff0c;线程池的作用&#xff08;意义&#xff09;&#xff0c;如果使用线程池会有什么好处&#xff0c;说说你对线程池的了解&#xff1f; 创建和销毁线程的代价是很大的&#xff0c;线程不像创建普通object对象那样&#xff0c;在堆中分配点内存就好…
阅读更多...
Java 线程池原理及四种常用的线程池使用

Java 线程池原理及四种常用的线程池使用

推荐阅读&#xff1a;Java线程池实现原理及其在美团业务中的实践 文章目录 什么是线程池使用线程池的好处线程池的实现原理流程图分析源码分析 线程池的使用向线程池中提交任务newCachedThreadPoolnewFixedThreadPoolnewScheduledThreadPoolnewSingleThreadExecutor自定义线程池…
阅读更多...
Tomcat线程池监控及线程池原理分析

Tomcat线程池监控及线程池原理分析

目录 一、背景 二、tomcat线程池监控 三、tomcat线程池原理 四、总结 一、背景 我们都知道稳定性、高可用对于一个系统来讲是非常重要的&#xff0c;而为了保证系统的稳定性&#xff0c;我们一般都会进行各方面的监控&#xff0c;以便系统有任何异常情况时&#xff0c;开发人员…
阅读更多...
Python学习：线程池原理及实现

Python学习：线程池原理及实现

传统多线程方案会使用“即时创建&#xff0c; 即时销毁”的策略。尽管与创建进程相比&#xff0c;创建线程的时间已经大大的缩短&#xff0c;但是如果提交给线程的任务是执行时间较短&#xff0c;而且执行次数极其频繁&#xff0c;那么服务器将处于不停的创建线程&#xff0c;销…
阅读更多...
超详细的线程池原理解析

超详细的线程池原理解析

说明 线程池作为常用的并发工具重要性不言而喻&#xff0c;本文针对线程池进行了抽丝剥茧般的深入解析&#xff0c;希望大家看后会有帮助。 1 ThreadPoolExecutor结构关系图 2 参数结构 public ThreadPoolExecutor( int corePoolSize,//核心线程数量int maximumPoolSize,…
阅读更多...
从简单代码入手，分析线程池原理

从简单代码入手，分析线程池原理

一、线程池简介 1、池化思想 在项目工程中&#xff0c;基于池化思想的技术应用很多&#xff0c;例如基于线程池的任务并发执行&#xff0c;中间件服务的连接池配置&#xff0c;通过对共享资源的管理&#xff0c;降低资源的占用消耗&#xff0c;提升效率和服务性能。 池化思想…
阅读更多...
线程池原理与实现

线程池原理与实现

目录 1. 线程池是什么 2. 线程池的优点&#xff1a; 3. 线程池的应用场景 4. 线程池的实现 4.1 线程池实现原理 4.2 线程池基本框架 4.3 结构体&#xff1a; 4.4 提供的接口 4.5 线程池测试代码 5 线程池提高demo thrd_pool.h thrd_pool.c main.c 运行结果 6 re…
阅读更多...
线程池原理——高频面试题

线程池原理——高频面试题

1.高频面试题&#xff1a; 1.为什么使用线程池&#xff0c;优势是什么&#xff1b; 2.线程池如何使用&#xff1b; 3.线程池的几个重要的参数介绍&#xff1b; 4.线程池底层工作原理&#xff1b; 5.线程池用过吗&#xff1f;生产上你如何设置合理参数&#xff1b; 2.线程…
阅读更多...
Android线程池原理详解

Android线程池原理详解

简介 但凡有点开发经验的同学都知道&#xff0c;频繁的创建和销毁线程是会给系统带来比较大的性能开销的。所以线程池就营运而生了。那么使用线程池有什么好处呢&#xff1f; 降低资源消耗 可以重复利用已创建的线程降低线程创建和销毁造成的消耗。提高响应速度 当任务到达时…
阅读更多...
Java面试题之：线程池原理

Java面试题之：线程池原理

Java面试题之&#xff1a;线程池原理 一、简介二、线程复用三、线程池的组成四、拒绝策略五、Java 线程池工作过程 一、简介 线程池做的工作主要是控制运行的线程的数量&#xff0c;处理过程中将任务放入队列&#xff0c;然后在线程创建后启动这些任务&#xff0c;如果线程数量…
阅读更多...
ThreadPoolExecutor线程池原理

ThreadPoolExecutor线程池原理

ThreadPoolExecutor线程池原理 线程池原理1. 线程池的简单介绍1.1 线程池是什么1.2 线程池解决的核心问题是什么 2. 线程池的实现原理2.1 线程池的执行流程2.2 源码分析 3. 线程池的使用3.1 线程池的创建3.2 向线程池提交任务3.3 生命周期管理3.4 关闭线程池3.5 合理地配置线程…
阅读更多...
线程池原理分析

线程池原理分析

使用线程池目的 在开发过程中&#xff0c;合理地使用线程池能够带来3个好处。 1.降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。 2.提高响应速度。当任务到达时&#xff0c;任务可以不需要等到线程创建就能立即执行。 3.提高线程的可管理性。线程是稀…
阅读更多...
Java 线程池原理总结

Java 线程池原理总结

Java 线程池原理总结 &#xff08;一&#xff09;什么是线程池 线程池做的工作主要是控制运行的线程的数量&#xff0c;处理过程中将任务放入队列&#xff0c;然后在线程创建后启动这些任务&#xff0c;如果线程数量超过了最大数量超出数量的线程排队等候&#xff0c;等其它线…
阅读更多...
线程池原理总结

线程池原理总结

【引言】 关于线程池&#xff0c;印象中好像自己有写过相关的总结博客。翻了翻之前的博客&#xff0c;确实&#xff0c;在去年十一月写过一篇《线程池使用总结》。 时隔一年&#xff0c;我已经离开了那家让我成长很多的公司&#xff0c;在那里&#xff0c;写了很多的代码&…
阅读更多...
线程池原理全解析

线程池原理全解析

目录 1 线程池简介 2 线程池 2.1 ThreadPoolExecutor类 2.2 ThreadPoolExecutor方法 3 线程池实现原理 3.1.线程池状态 3.2.任务的执行 总结过程 3.3.线程池中的线程初始化 3.4.任务缓存队列及排队策略 3.5.任务拒绝策略 3.6.线程池的关闭 3.7.线程池容量的动态调…
阅读更多...
一文带你清晰弄明白线程池的原理

一文带你清晰弄明白线程池的原理

不知道你是否还记得阿里巴巴的java代码规范中对多线程有这样一条强制规范: 【强制】线程资源必须通过线程池提供&#xff0c;不允许在程序中显示创建线程。 说明&#xff1a;使用线程池的好处是减少在创建和销毁线程池上所消耗的时间以及系统资源的开销&#xff0c;解决资源不足…
阅读更多...
线程池工作原理

线程池工作原理

一、线程池默认工作流程 1、线程在有任务的时候会创建核心的线程数corePoolSize 2、当线程满了&#xff08;有任务但是线程被使用完&#xff09;不会立即扩容,而是放到阻塞队列中,当阻塞队列满了之后才会继续创建线程。 3、如果队列满了,线程数达到最大线程数则会执行拒绝策…
阅读更多...
推荐文章

Copyright @ 2022~2023