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

单链表详解：从概念到实现

1. 单链表的基本概念

单链表，也是一种线性表。
逻辑结构：线性的 / 物理结构：非线性的

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

2. 单链表的结点结构

链表是由结点组成的，结点由两个部分组成：存储的数据+指针（存储下一个结点的地址）
一个一个的结点就相当于一节一节的车厢

3.单链表的一系列用法

3.1链表的打印及初始化

//链表的打印voidSLTPrint(SLTNode*phead){SLTNode*pcur=phead;while(pcur){printf("%d -> ",pcur->data);pcur=pcur->next;}printf("NULL\n");}SLTNode*SLTBuyNode(SLTDataType x){//根据x创建新结点SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail!");exit(1);}newnode->data=x;newnode->next=NULL;returnnewnode;}

放入测试函数测试一下，创建出一个新链表

这里要说一下传值和传址
&：只要看不到这个操作符，就是传值
传值：形参是实参的值的拷贝
传址：形参的改变要影响实参

SLTPrint(plist)中没有用取地址操作符&，plist就是一个结构体指针，在这里就是传值调用

3.2 尾插

一是链表不为空，二是链表为空

voidSLTPushBack(SLTNode**pphead,SLTDataType x){SLTNode*newnode=SLTBuyNode(x);//链表为空if(*pphead==NULL){*pphead=newnode;}else{//找尾结点SLTNode*ptail=*pphead;while(ptail->next){ptail=ptail->next;}//ptail newnodeptail->next=newnode;}}

思考下面的问题

为什么这里形参的改变没有影响实参？

3.3头插

voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnode=SLTBuyNode(x);newnode->next=*pphead;*pphead=newnode;}

3.4 尾删

voidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);//只有一个结点if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode*prev=NULL;SLTNode*ptail=*pphead;while(ptail->next){prev=ptail;ptail=ptail->next;}//prev ptailprev->next=NULL;free(ptail);ptail=NULL;}}

3.5 头删

voidSLTPopFront(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*next=(*pphead)->next;free(*pphead);*pphead=next;}

3.6查找

SLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*pcur=phead;while(pcur){if(pcur->data==x){returnpcur;}pcur=pcur->next;}}

3.7在指定位置之前插入数据

voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead&&pos);//当pos指向第一个结点时，是头插if(pos==*pphead){SLTPushFront(pphead,x);}else{SLTNode*newnode=SLTBuyNode(x);//找pos的前一个指针SLTNode*prev=*pphead;while(prev->next=pos){prev=prev->next;}//prev--> newnode--> posprev->next=newnode;newnode->next=pos;}}

3.8 在指定位置之后插入结点

voidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnode=SLTBuyNode(x);newnode->next=pos->next;pos->next=newnode;}

3.9 删除pos结点

voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(pphead&&pos);//pos就是头结点if(pos==*pphead){SLTPopFront(pphead);}else{SLTNode*prev=*pphead;while(prev->next!=pos){prev=prev->next;}//prev pos pos->nextprev->next=pos->next;free(pos);pos=NULL;}}

3.10 删除pos之后的结点

voidSLTEraseAfter(SLTNode*pos){assert(pos&&pos->next);//pos del del->nextSLTNode*del=pos->next;pos->next=del->next;free(del);del=NULL;}

3.11 销毁链表

voidSListDestroy(SLTNode**pphead){SLTNode*pcur=*pphead;while(pcur){SLTNode*next=pcur->next;free(pcur);pcur=next;}*pphead=NULL;}

以上就是单链表各种功能的实现

4. 顺序表与链表的比较

1. 顺序表：中间 /头部的插入删除，时间复杂度O（N） 链表：头部插入删除O（1） 在尾部频繁的插入和删除，用顺序表更好 在头部频繁的插入和删除，用链表更好 2. 顺序表增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗 链表无需增容 3. 顺序表增容一般是呈2倍增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入五个数据，后面没有数据插入了，那么就浪费了95个数据空间。 链表不存在空间浪费