循环单链表:尾结点的next指针指向头结点
从一个结点出发,可以找到链表中任何一个结点(可以找到前驱结点)
typedef struct LNode{ //定义循环单链表结点类型 ElemType data; //每个结点存放一个数据元素 struct LNode *next; //指针指向下一个结点 }LNode,*LinkList; //初始化一个循环单链表 bool InitList(LinkList &L){ L = (LNode*)malloc(sizeof(Lnode)); if(L==NULL){ return false; //内存不足,分配失败 } L->next = L; //头结点next指向头结点 return true; }
判断单链表是否为空表
//判断循环单链表是否为空 bool Empty(LinkList L){ if(L->next == L){ return true; }else{ return false; } }
判断结点p是否为循环单链表的表尾结点
//判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L,LNode *p){ if(p->next == L){ return true; }else{ return false; } }
从头部找到尾部,时间复杂度为:O(n)
从尾部找到头部,时间复杂度为:O(1)
很多时候对链表的操作实在头部或者尾部,可以让L指向表尾元素(插入、删除时可能需要修改L)
表头结点的prior指向表尾结点
表尾结点的next指向表头结点
typedef struct LNode{ //定义循环单链表结点类型 ElemType data; //每个结点存放一个数据元素 struct LNode *next; //指针指向下一个结点 struct LNode *prior; //指针指向下一个结点 }LNode,*DLinkList; //初始化一个循环单链表 bool InitDLinkList(DLinkList &L){ L = (LNode*)malloc(sizeof(Lnode)); if(L==NULL){ return false; //内存不足,分配失败 } L->next = L; //头结点next指向头结点 L->prior = L; return true; }
判断双链表是否为空表
//判断循环双链表是否为空 bool Empty(DLinkList L){ if(L->next == L){ return true; }else{ return false; } }
判断结点p是否为循环单链表的表尾结点
//判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L,LNode *p){ if(p->next == L){ return true; }else{ return false; } }
//在p结点之后插入s结点 bool InsertNextDNode(LNode *p,LNode *s){ s->next = p->next; //将结点*s插入到结点*p之后 p->next->prior = s; s->prior = p; p->next = s; }
循环双链表的好处,不需要考虑插入区域是否为表尾结点
//删除p的后继结点q p->next = q->next; q->next->prior = p; free(q);