[数据结构与算法]【数据结构】 双向循环链表链表的实现

目录

带头结点双向循环链表

下来挑选几个例子说明双向链循环表的实现过程，其他原理都是一样的

首先是想明白一个问题，两个链表相交求交点，链表是否带环？

分为3种情况：

1.两条链表都不带环

?2.其中一条链表带环，另一个链表不带环

?3.两个链表都带环

?

带头结点双向循环链表

操作如下

#pragma once


typedef int DataType;


typedef struct DListNode
{
	struct DListNode* next;  // 指向后一个节点
	struct DListNode* prev;  // 指向前一个节点
	DataType data;
}DListNode;



void DListInit(DListNode** head);//初始化
void DListPushBack(DListNode* head, DataType data);//尾插
void DListPopBack(DListNode* head);//尾删

void DListPushFront(DListNode* head, DataType data);//头插
void DListPopFront(DListNode* head);//头删

DListNode* DListFind(DListNode* head, DataType data);  //

void DListInsrt(DListNode* pos, DataType data);  //任意位置删除插入
void DListErase(DListNode* pos);  //任意位置删除

int DListSize(DListNode* head);  
int DListEmpty(DListNode* head);

// 清空链表中的所有有效节点
void DListClear(DListNode* head);

void DListDestroy(DListNode** head);

void DListInit(DListNode** head); 初始化

只需要将头节点创建好，然后通过形参带进去---》形参必须要用二级指针

下来挑选几个例子说明双向链循环表的实现过程，其他原理都是一样的

void DListInsrt(DListNode* pos, DataType data); ?//任意位置删除插入

1.创建一个新节点

2。将新节点插入到Pos之前（注意先将新节点链接进去，在断开原链表）

?

newNode->next = pos;

newNode->prev = pos-> prev;

newNode->prev->next = newNode;

pos->prev = newNode;

void DListPushBack(DListNode* head, DataType data);//尾插

?

newNode->next =head;

newNode->prev = head->prev;

newNode->prev->next = newNode;

head->prev = newNode;

尾插时的head就相当于任意位置插入时的pos?