【数据结构与算法】单链表

单链表详解从概念到实现文章目录单链表详解从概念到实现1. 单链表的基本概念2. 单链表的结点结构3.单链表的一系列用法3.1链表的打印及初始化3.2 尾插3.3头插3.4 尾删3.5 头删3.6查找3.7在指定位置之前插入数据3.8 在指定位置之后插入结点3.9 删除pos结点3.10 删除pos之后的结点3.11 销毁链表4. 顺序表与链表的比较1. 单链表的基本概念单链表也是一种线性表。逻辑结构线性的 / 物理结构非线性的概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。2. 单链表的结点结构链表是由结点组成的结点由两个部分组成存储的数据指针存储下一个结点的地址一个一个的结点就相当于一节一节的车厢3.单链表的一系列用法3.1链表的打印及初始化//链表的打印voidSLTPrint(SLTNode*phead){SLTNode*pcurphead;while(pcur){printf(%d - ,pcur-data);pcurpcur-next;}printf(NULL\n);}SLTNode*SLTBuyNode(SLTDataType x){//根据x创建新结点SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail!);exit(1);}newnode-datax;newnode-nextNULL;returnnewnode;}放入测试函数测试一下创建出一个新链表这里要说一下传值和传址只要看不到这个操作符就是传值传值形参是实参的值的拷贝传址形参的改变要影响实参SLTPrint(plist)中没有用取地址操作符plist就是一个结构体指针在这里就是传值调用3.2 尾插一是链表不为空二是链表为空voidSLTPushBack(SLTNode**pphead,SLTDataType x){SLTNode*newnodeSLTBuyNode(x);//链表为空if(*ppheadNULL){*ppheadnewnode;}else{//找尾结点SLTNode*ptail*pphead;while(ptail-next){ptailptail-next;}//ptail newnodeptail-nextnewnode;}}思考下面的问题为什么这里形参的改变没有影响实参3.3头插voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnodeSLTBuyNode(x);newnode-next*pphead;*ppheadnewnode;}3.4 尾删voidSLTPopBack(SLTNode**pphead){assert(pphead*pphead);//只有一个结点if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;}else{SLTNode*prevNULL;SLTNode*ptail*pphead;while(ptail-next){prevptail;ptailptail-next;}//prev ptailprev-nextNULL;free(ptail);ptailNULL;}}3.5 头删voidSLTPopFront(SLTNode**pphead){assert(pphead*pphead);SLTNode*next(*pphead)-next;free(*pphead);*ppheadnext;}3.6查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*pcurphead;while(pcur){if(pcur-datax){returnpcur;}pcurpcur-next;}}3.7在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(ppheadpos);//当pos指向第一个结点时是头插if(pos*pphead){SLTPushFront(pphead,x);}else{SLTNode*newnodeSLTBuyNode(x);//找pos的前一个指针SLTNode*prev*pphead;while(prev-nextpos){prevprev-next;}//prev-- newnode-- posprev-nextnewnode;newnode-nextpos;}}3.8 在指定位置之后插入结点voidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnodeSLTBuyNode(x);newnode-nextpos-next;pos-nextnewnode;}3.9 删除pos结点voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(ppheadpos);//pos就是头结点if(pos*pphead){SLTPopFront(pphead);}else{SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}//prev pos pos-nextprev-nextpos-next;free(pos);posNULL;}}3.10 删除pos之后的结点voidSLTEraseAfter(SLTNode*pos){assert(pospos-next);//pos del del-nextSLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}3.11 销毁链表voidSListDestroy(SLTNode**pphead){SLTNode*pcur*pphead;while(pcur){SLTNode*nextpcur-next;free(pcur);pcurnext;}*ppheadNULL;}以上就是单链表各种功能的实现4. 顺序表与链表的比较1. 顺序表中间 /头部的插入删除时间复杂度ON 链表头部插入删除O1 在尾部频繁的插入和删除用顺序表更好 在头部频繁的插入和删除用链表更好 2. 顺序表增容需要申请新空间拷贝数据释放旧空间会有不小的消耗 链表无需增容 3. 顺序表增容一般是呈2倍增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入五个数据后面没有数据插入了那么就浪费了95个数据空间。 链表不存在空间浪费不同点顺序表链表存储空间上物理上一定连续逻辑上连续物理上不一定连续随机访问支持:O1不支持O(N)任意位置插入或删除元素可能需要搬移元素效率低 (ON)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低