一、介绍

特点

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个链表虽然结构复杂，但是使用代码实现以后会发现能带来很多优势.

结构

二、实现

在List.h需要声明的头文件

#include <stdio.h>
//malloc函数用到
#include <stdlib.h>
//assert函数用到
#include <assert.h>

链表结构

在List.h中声明

typedef int ListNodeDate;

typedef struct ListNode
{
	ListNodeDate date;

	struct ListNode* next;//指向下一个
	struct ListNode* prev;//指向上一个
}ListNode;

动态申请内存节点函数

申请成功后将值赋给新节点的，后返回ListNode*类型的节点
如果申请内存失败将退出

ListNode* buyListNode(ListNodeDate x)
{
	ListNode* newListNode = (ListNode*)malloc(sizeof(ListNode));
	if (newListNode==NULL)
	{
		printf("申请内存失败！");
		exit(-1);//退出
	}
	newListNode->date = x;
	newListNode->next = NULL;
	newListNode->prev = NULL;

	return newListNode;
}

初始化函数

初始化一个头尾指向自己的head“哨兵位”头结点（不存储有效值）

ListNode* ListInit()
{

	ListNode* head = buyListNode(0);
	head->next = head;
	head->prev = head;

	return head;
}

实现尾插函

传入链表的head地址跟要尾插的值

void List_pushback(ListNode* head, ListNodeDate x)
{
//如果这个不指向什么还不为空，则结束程序
	assert(head);

	ListNode* tail = head->prev;
	ListNode* NewNode = buyListNode(x);

	tail->next = NewNode;
	NewNode->prev = tail;

	NewNode->next = head;
	head->prev = NewNode;
}

实现尾删函数

void List_popback(ListNode* head)
{
	assert(head);

	ListNode* tail = head->prev;
	ListNode* tail_prev = tail->prev;

	tail_prev->next = head;
	head->prev = tail_prev;
	free(tail);//清除malloc开辟的动态内存空间
	tail = NULL;//并置为空
}

实现打印函数

void List_printf(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
}

实现头插函数

void List_pushfront(ListNode* head, ListNodeDate x)
{
	assert(head);

	ListNode* tail = head->next;
	ListNode* NewNode = buyListNode(x);

	head->next = NewNode;
	NewNode->prev = head;

	NewNode->next = tail;
	tail->prev = NewNode;
}

实现头删函数

void List_popfront(ListNode* head)
{
	assert(head);

	ListNode* tail = head->next;
	ListNode* tail_next = tail->next;

	head->next = tail_next;
	tail_next->prev = head;

	free(tail);
	tail = NULL;
}

还有一些函数例如
中间插如删除等
查找替换等

三、代码

list.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int ListNodeDate;

typedef struct ListNode
{
	ListNodeDate date;

	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

//动态申请内存
ListNode* buyListNode(ListNodeDate x);
//初始化
ListNode* ListInit();
//打印
void List_printf(ListNode* head);
//尾插尾删
void List_pushback(ListNode* head, ListNodeDate x);
void List_popback(ListNode* head);
//头插头删
void List_pushfront(ListNode* head, ListNodeDate x);
void List_popfront(ListNode* head);

list.cpp文件

#include"List.h"

ListNode* buyListNode(ListNodeDate x)
{
	ListNode* newListNode = (ListNode*)malloc(sizeof(ListNode));
	if (newListNode==NULL)
	{
		printf("申请内存失败！");
		exit(-1);
	}
	newListNode->date = x;
	newListNode->next = NULL;
	newListNode->prev = NULL;

	return newListNode;
}

void List_pushback(ListNode* head, ListNodeDate x)
{
	assert(head);

	ListNode* tail = head->prev;
	ListNode* NewNode = buyListNode(x);

	tail->next = NewNode;
	NewNode->prev = tail;

	NewNode->next = head;
	head->prev = NewNode;
}

ListNode* ListInit()
{

	ListNode* head = buyListNode(0);
	head->next = head;
	head->prev = head;

	return head;
}

void List_printf(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
}

void List_popback(ListNode* head)
{
	assert(head);

	ListNode* tail = head->prev;
	ListNode* tail_prev = tail->prev;

	tail_prev->next = head;
	head->prev = tail_prev;
	free(tail);
	tail = NULL;
}

void List_pushfront(ListNode* head, ListNodeDate x)
{
	assert(head);

	ListNode* tail = head->next;
	ListNode* NewNode = buyListNode(x);

	head->next = NewNode;
	NewNode->prev = head;

	NewNode->next = tail;
	tail->prev = NewNode;
}

void List_popfront(ListNode* head)
{
	assert(head);

	ListNode* tail = head->next;
	ListNode* tail_next = tail->next;

	head->next = tail_next;
	tail_next->prev = head;

	free(tail);
	tail = NULL;
}

main.cpp文件

#include"List.h"

void test()
{
	ListNode* head = NULL;
	head = ListInit();
	List_pushback(head, 1);
	List_pushback(head, 2);
	List_pushback(head, 3);
	List_pushback(head, 4);
	List_popback(head);
	List_pushfront(head, 0);
	List_pushfront(head, -1);
	List_popfront(head);
	List_printf(head);
}

int main()
{
	test();

	return 0;
}

双向循环链表