双向带头循环链表之重拳出击

目录

一、 链表的8种结构

二、 双向带头循环链表的实现

结构的创建和初始化 

 申请结点

初始化

尾插

打印

头插

尾删 

头删

判空

 链表长度

 在pos位置之前插入结点

删除pos位置的结点

三、完整代码

 总结

---

一、 链表的8种结构

1、不带头单向循环结构
2、不带头单向⾮循环结构
3、不带头双向循环结构
4、不带头双向⾮循环结构
5、带头单向循环结构
6、带头单向⾮循环结构
7、带头双向循环结构
8、带头双向⾮循环结构

但是其中我们最常用的就两种，一种是我之前说过的单链表 ，另一种就是我今天要说的双向带头循环链表。双向带头循环链表是非常实用的链表，它结构复杂但是操作简单，等你学完你也就瞧不上其他链表了。

 双向带头循环链表的结构是这样的：

好让我们上手写一下。

二、 双向带头循环链表的实现

结构的创建和初始化 

 首先我们写一下我们所需要的头文件

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

其次我们在创建它的结构时要有一个前驱指针，还要有一个后继指针 

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

结构创建好了，那就实现功能了。

需要实现一下几个基本功能

//初始化
LTNode* ListInit();
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
 
//打印
void ListPrint(LTNode* phead);
 
//头插
void ListPushFront(LTNode* phead, LTDataType x);
 
//尾删
void ListPopBack(LTNode* phead);
 
//头删
void ListPopFront(LTNode* phead);
 
//判空
bool ListEmpty(LTNode* phead);
 
//在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x);
 
//删除pos位置的节点
void ListErase(LTNode* pos);
 
//链表长度
int ListSize(LTNode* phead);
 
//销毁链表
void ListDestory(LTNode* phead);

 申请结点

LTNode* BuyListNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
}

初始化

初始化的话有两种方法可以用

方法一：二级指针

void ListInit(LTNode** pphead)
{
	*pphead = BuyListNode(-1);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}

 方法二：用结构体指针作为返回值 申请结点

LTNode* BuyListNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
}

尾插

 如果学习了单链表的话，这个对于你来说不就是小菜一碟嘛

 当然跟单链表不同的是双向链表就不用像单链表那样遍历找尾了，因为它头结点的prev就指向了尾结点所以变得更简单了。

链接过程 ：

 代码实现：

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	newnode->prev = tail;
	tail->next = newnode;
	newnode->next = phead;
	phead->prev = newnode;
}

当链表为空时，这个代码（也包括我下面的代码）也同样可以运行，不信你就顺着这个代码的思路理一遍

打印

代码实现： 

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

 注意：可不是从头开始打印，而是头结点的下一个位置，别忘了我们可是设了哨兵位的。 

头插

头插其实也很简单 

 代码实现： 

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode= BuyListNode(x);
	LTNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

当然你也可以不用像我这样定义一个next，但是你逻辑（链接的先后顺序）要捋顺，否则可是会出错的。

尾删 

代码实现：

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(! ListEmpty(phead));
    assert(phead->next!=phead);
    LTNode* tail = phead->prev;
    LTNode* tailprev = tail->prev;
    free(tail);
    phead->prev = tailprev;
    tailprev->next = phead;
}

双向链表的尾删其实也不难，我们可以先用phead->prev找到尾结点，free点尾结点，之后再将新的尾结点和phead进行链接。

头删

代码实现：

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	LTNode* head = phead->next;
	LTNode* headnext = head->next;
	free(head);
	phead->next = headnext;
	headnext->prev = phead;
}

思路和尾删的一样，phead->next找到头，free掉头结点，再将新的头和phead进行链接就完事了。

判空

 上面的头删和尾删都离开不了判空。所以说判空其实挺重要的。

代码实现：

bool ListEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

两行代码就搞定了，是不是感觉有点不太相信。其实它真就值这两行代码。

 链表长度

代码实现：

int  ListSize(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	int size = 0;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

得到链表的长度和打印链表的思路一致，我们要从头结点的下一个结点进行遍历，一直到cur==phead就结束，最后返回长度（size）就OK了。 

 

销毁链表

代码实现：

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	int size = 0;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		ListPopFront(cur);
		cur = next;
	}
	free(phead);
}

销毁的话和单链表是类似的，但是这里还要多一步，因为我们是带了哨兵位的头结点，我们要把这个哨兵位也删掉。

最精彩的部分当然要最后讲啦

曾经有个面试官面试的时候，叫人十分钟写出一个双链表，可别觉得面试官为难你，看了我下面讲的，你熟悉的话十分钟都不要就可以搞定。

 在pos位置之前插入结点

代码实现：

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	//prev newnode pos
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

 我们要先判断pos位置为不为空，然后找到pos位置的前一个，申请新节点，最后再将（pos、prev、newnode）进行链接就行了

删除pos位置的结点

代码实现：

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	posprev->next = posnext;
	posnext->prev = posprev;
	free(pos);
}

同样的我们先判断pos位置为不为空，然后我们在链接posprev和posnext,别忘了最后还要free掉pos结点。

前面的头插、尾插、头删、尾删直接调用这两个函数就行了。 

所以说十分钟写好一个双链表真的不是夸张。 

---

三、完整代码

 头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
 
 
 
//初始化
//void ListInit(LTNode** pphead);
LTNode* ListInit();
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
 
//打印
void ListPrint(LTNode* phead);
 
//头插
void ListPushFront(LTNode* phead, LTDataType x);
 
//尾删
void ListPopBack(LTNode* phead);
 
//头删
void ListPopFront(LTNode* phead);
 
//判空
bool ListEmpty(LTNode* phead);
 
//在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x);
 
//删除pos位置的节点
void ListErase(LTNode* pos);
 
//链表长度
int ListSize(LTNode* phead);
 
//销毁链表
void ListDestory(LTNode* phead);

源文件：

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "Dlist.h"
 
LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
}
 
//void ListInit(LTNode** pphead)
//{
//	*pphead = BuyListNode(-1);
//	(*pphead)->next = *pphead;
//	(*pphead)->prev = *pphead;
//}
LTNode* ListInit()
{
	LTNode* phead= BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	newnode->prev = tail;
	tail->next = newnode;
	newnode->next = phead;
	phead->prev = newnode;*/
	ListInsert(phead, x);
}
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
 
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	//LTNode* newnode= BuyListNode(x);
	1
	//LTNode* next = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;
	//newnode->next = next;
	//next->prev = newnode;
	2
	//phead->next->prev = newnode;
	//newnode->next = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;
	ListInsert(phead->next, x);
}
 
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(! ListEmpty(phead));
	/*assert(phead->next!=phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	phead->prev = tailprev;
	tailprev->next = phead;*/
	ListErase(phead->prev);
}
 
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	/*LTNode* head = phead->next;
	LTNode* headnext = head->next;
	free(head);
	phead->next = headnext;
	headnext->prev = phead;*/
	ListErase(phead->next);
}
 
bool ListEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
 
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	//prev newnode pos
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
 
 
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	posprev->next = posnext;
	posnext->prev = posprev;
	free(pos);
}
 
int  ListSize(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	int size = 0;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
 
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	int size = 0;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		ListErase(cur);
		cur = next;
	}
	free(phead);
}

 总结：

双链表的功能十分强大，虽然说结构可能复杂了一点但是插入删除的效率是非常的高，十分的好用。

觉得内容有用的话，就给博主三连吧