详解C语言中双向循环链表的实现

第详解C语言中双向循环链表的实现目录实现细节辅助理解图具体实现代码1、对链表进行初始化2、任意位置前的插入3、任意位置的删除4、头插和尾删完整代码头文件具体函数测试

实现细节

1、带一个哨兵位（哨兵节点，初始节点，不存储有效数据，用来方便后期数据的存储与查找）

2、与单向链表不同的是，双向链表中每个数据节点包含两个指针，分别指向前后两个节点

3、双向链表是循环的，其尾节点后不是空指针，而是与头部的哨兵节点通过指针相连

辅助理解图

具体实现代码

1、对链表进行初始化

初始化：哨兵位的前后指针均指向哨兵节点本身

voidListInit(ListNode**pphead)

*pphead=(ListNode*)malloc(sizeof(ListNode));

if(*pphead==NULL)

perror("ListInit");

exit(-1);

(*pphead)-date=-1;

(*pphead)-next=*pphead;

(*pphead)-prev=*pphead;

2、任意位置前的插入

注意：插入位置前后节点中的前后指针要进行相应的更换

voidAny_insert(ListNode*pos,Listtypedate)

ListNode*Prev=pos-prev;

//建立新节点

ListNode*NewNode=(ListNode*)malloc(sizeof(ListNode));

if(NewNode==NULL)

perror("Any_insert");

exit(-1);

NewNode-date=date;

NewNode-next=pos;

pos-prev=NewNode;

Prev-next=NewNode;

NewNode-prev=Prev;

3、任意位置的删除

细节点：当链表中没有数据时，就不用删除，因此需要建立一个函数进行判断

boolDetermine(ListNode*pphead)

{//判断链表中有无元素

assert(pphead);

returnpphead==pphead-next;

voidAny_delet(ListNode*pos)

assert(!Determine(pos));

ListNode*Next=pos-next;

ListNode*Prev=pos-prev;

Next-prev=Prev;

Prev-next=Next;

free(pos);

4、头插和尾删

此处的插入和删除，十分方便，即：对上面的任插和任删进行套用

头插如下：

voidHead_insert(ListNode*pphead,Listtypedate)

ListNode*NewNode=(ListNode*)malloc(sizeof(ListNode));

if(NewNode==NULL)

perror("Head_insert");

exit(-1);

//单独实现

//NewNode-date=date;

//NewNode-prev=pphead;

//NewNode-next=pphead-next;

//pphead-next-prev=NewNode;

//pphead-next=NewNode;

//进行任插的复用

Any_insert(pphead-next,date);

尾删如下：

voidTail_delet(ListNode*pphead)

assert(pphead);

//单独实现

//assert(Determine(pphead));

/*ListNode*tail=pphead-prev;

if(tail!=pphead)

ListNode*tailprev=tail-prev;

tailprev-next=pphead;

pphead-prev=tailprev;

free(tail);

//尾删的复用

Any_delet(pphead-prev);

完整代码

头文件

#pragmaonce

#includestdio.h

#includemalloc.h

#includestdlib.h

#includeassert.h

#includestdbool.h

typedefintListtype;

typedefstructListNode

structListNode*prev;

Listtypedate;

structListNode*next;

}ListNode;

voidListInit(ListNode**pphead);//链表初始化

voidListNode_ADD(ListNode*pphead,Listtypedate);//尾插

voidHead_insert(ListNode*pphead,Listtypedate);//头插

voidListNode_Print(ListNode*pphead);//链表打印

voidTail_delet(ListNode*pphead);//尾删

boolDetermine(ListNode*pphead);//判断表中有无数据

voidAny_insert(ListNode*pos,Listtypedate);//任插

voidAny_delet(ListNode*pos);//任删

voidList_Destory(ListNode*pos);//链表清空

具体函数

#define_CRT_SECURE_NO_WARNINGS1

#include"List.h"

//链表打印

voidListNode_Print(ListNode*pphead)

assert(pphead);

ListNode*phead=pphead;

pphead=pphead-next;

for(;pphead!=phead;pphead=pphead-next)

printf("%d",pphead-date);

printf("\n");

boolDetermine(ListNode*pphead)

{//判断链表中有无元素

assert(pphead);

returnpphead==pphead-next;

//链表初始化

voidListInit(ListNode**pphead)

*pphead=(ListNode*)malloc(sizeof(ListNode));

if(*pphead==NULL)

perror("ListInit");

exit(-1);

(*pphead)-date=-1;

(*pphead)-next=*pphead;

(*pphead)-prev=*pphead;

voidListNode_ADD(ListNode*pphead,Listtypedate)

//ListNode*NewNode=(ListNode*)malloc(sizeof(ListNode));

//if(NewNode==NULL)

//perror("ADD_malloc");

//exit(-1);

//NewNode-date=date;

//NewNode-prev=pphead-prev;

//pphead-prev-next=NewNode;

//pphead-prev=NewNode;

//NewNode-next=pphead;

//任插的复用

Any_insert(pphead,date);

voidHead_insert(ListNode*pphead,Listtypedate)

ListNode*NewNode=(ListNode*)malloc(sizeof(ListNode));

if(NewNode==NULL)

perror("Head_insert");

exit(-1);

//NewNode-date=date;

//NewNode-prev=pphead;

//NewNode-next=pphead-next;

//pphead-next-prev=NewNode;

//pphead-next=NewNode;

//进行任插的复用

Any_insert(pphead-next,date);

voidTail_delet(ListNode*pphead)

assert(pphead);

//assert(Determine(pphead));

/*ListNode*tail=pphead-prev;

if(tail!=pphead)

ListNode*tailprev=tail-prev;

tailprev-next=pphead;

pphead-prev=tailprev;

free(tail);

//尾删的复用

Any_delet(pphead-prev);

//在任意位置前插入

voidAny_insert(ListNode*pos,Listtypedate)

ListNode*Prev=pos-prev;

ListNode*NewNode=(ListNode*)malloc(sizeof(ListNode));

if(NewNode==NULL)

perror("Any_insert");

exit(-1);

NewNode-date=date;

NewNode-next=pos;

pos-prev=NewNode;

Prev-next=NewNode;

NewNode-prev=Prev;

//任意位置删除

voidAny_delet(ListNode*pos)

assert(!Determine(pos));

ListNode*Next=pos-next;

ListNode*Prev=pos-prev;

Next-prev=Prev;

Prev-next=Next;

free(pos);

//链表清空

voidList_Destory(ListNode*pos)

ListNode*head=pos,*Prev=pos-prev;

for(pos=pos-prev;head!=pos;pos=Prev)

Prev=pos-prev;

Any_delet(pos);

printf("\n清空完成\n");

}

测试

#define_CRT_SECURE_NO_WARNINGS1

#include"List.h"

voidListTest(ListNode**pphead)

ListInit(pphead);

Head_insert(*pphead,60);

Head_insert(*pphead,100);

Head_insert(*pphead,60);

Head_insert