带头双向循环链表（一）

一、概念与结构

无头单向非循环链表结构简单，一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。而带头双向循环链表的结构较为复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表，虽然它的结构复杂但是因为结构优势用代码实现起来会变得简单。 </br>

二、基本操作的实现

定义结构体

typedef int ListDataType;//类型重命名
typedef struct ListNode {
	ListDataType val; //结点数据
	struct ListNode* prev;//指向上一个结点的指针
	struct ListNode* next;//指向下一个结点的指针
}LTNode;

1.创建结点

LTNode* BuyListNode(ListDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申请空间
    //判断是否为空
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}

2.初始化链表

void ListInit(LTNode** pphead)//初始化
{
    //创建一个头节点
	*pphead = (LTNode*)malloc(sizeof(LTNode));//初始化时将头结点置为-1;
    
	*pphead = BuyListNode(-1); //头节点
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
//	LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1;
//	phead->next = phead;
//	phead->prev = phead;
//	return phead;
//}

初始化链表有两种方式，一种是有返回类型（注释部分），另一种是在初始化函数中给结构体开辟空间（不过注意参数要为二级指针）。因为是带头结点的循环链表，所以prev和next指针都指向自己。