初始化双向链表创建哨兵位

注意这⾥的“带头”跟前⾯我们说的“头结点”是两个概念实际前⾯的在单链表阶段称呼不严

带头链表⾥的头结点实际为“哨兵位”哨兵位结点不存储任何有效元素只是站在这⾥“放哨

实现双向链表

创建3个文件list.h头文件list.c存放函数的文件test.c测试文件

双向链表数据

tab-arr存放x数值双向链表是带循环的所以节点头和节点尾要指向自己

//创建双向链表

NULL){perror(malloc);exit(1);}tab-arr

x;tab-next

双向链表要带头所以我们需要创建一个哨兵位head这个哨兵位不能修改。

//初始化

cjsxlb(x);//先让新节点的头连接前一个节点tab-prev

r;//在让新节点的前一个节点连接新的节点头r-prev-next

tab;

cjsxlb(x);//让新节点的尾指向哨兵位下一个节点tab-next

tab;}

我们不能删除哨兵位所以我们需要布尔类型来判断当前节点是不是只有一个哨兵位只有哨兵位不能删除。

//bool

{assert(r);//哨兵位指向的下一个节点等于哨兵位返回真return

r-next

{assert(r);//布尔类型判断assert(!list(r));//把最后一个节点给addSL*

add

{assert(r);//布尔类型判断assert(!list(r));//哨兵位的下一个节点SL*

add

r-next;//add下一个节点的头指向哨兵位add-next-prev

NULL;}

NULL){printf(没有找到\n);}else{printf(找到了\n);}*/

指定位置后插入

cjsxlb(x);//新节点的尾指向tab的下一个节点add-next

tab;//tab下一个节点的头指向addtab-next-prev

add;}

这个的原理和头删除一样把哨兵位当做tab的上一个节点就可以了。

//指定位置删除

第三步释放add或tab空间,都是指向一块空间的然后置为NULL。

//指定位置删除

tab;//把add上一个节点的尾指向add的下一个节点add-prev-next

add-next;//把add的下一个节点的头指向add的上一个节点add-next-prev

NULL;

add-next;//释放free(add);//下一个节点赋值给addadd

NULL;//把add置为空add

add-next;//释放free(add);//下一个节点赋值给addadd

NULL;//把add置为空add

二级指针可以传地址过去可以修改到实参销毁数据相当于销毁了实参。

//xiaoh(add);//二级指针xiaoh(add);//一级指针add

NULL;

不同点顺序表链表单链表存储空间上物理上⼀定连续逻辑上连续但物理上不⼀定连续随机访问⽀持O(1)不⽀持O(N)任意位置插⼊或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插⼊动态顺序表空间不够时需要扩

list.h

NULL){perror(malloc);exit(1);}tab-arr

x;tab-next

cjsxlb(x);//先让新节点的头连接前一个节点tab-prev

r;//在让新节点的前一个节点连接新的节点头r-prev-next

tab;

cjsxlb(x);//让新节点的尾指向哨兵位下一个节点tab-next

tab;}//布尔类型

{assert(r);//哨兵位指向的下一个节点等于哨兵位返回真return

r-next

{assert(r);//布尔类型判断assert(!list(r));//把最后一个节点给addSL*

add

{assert(r);//布尔类型判断assert(!list(r));//哨兵位的下一个节点SL*

add

r-next;//add下一个节点的头指向哨兵位add-next-prev

NULL;}//查找

cjsxlb(x);//新节点的尾指向tab的下一个节点add-next

tab;//tab下一个节点的头指向addtab-next-prev

add;}//指定位置删除

tab;//把add上一个节点的尾指向add的下一个节点add-prev-next

add-next;//把add的下一个节点的头指向add的上一个节点add-next-prev

NULL;

add-next;//释放free(add);//下一个节点赋值给addadd

NULL;//把add置为空add

99);尾删除//weisc(add);头删除//tosc(add);SL*

tab

NULL){printf(没有找到\n);}else{printf(找到了\n);}*///指定位置后插入//zhidcr(tab,

99);//day(add);//指定位置删除zhidsc(tab);day(add);//xiaoh(add);//二级指针xiaoh(add);//一级指针add

NULL;}int