【数据结构】线性表之双向带头循环链表


在这里插入图片描述

双向链表的概念

在前面学习链表的时候,不知道大家有没有过感受,链表是通过next链接起来的,这种链接是头去链接尾,但是在尾部就不是那么好往前找到头。
在这里插入图片描述
比如这么一个结构,如果说现在让输出1,2,3,4,5是不是很容易,直接顺序遍历,然后打印data域即可,但是如果需要反着打印的时候大家是不是就难受了,心想:如果5到4有链接,4到3有链接,3到2有链接,2到一有链接,如果是这样的结构,就打印十分方便了。
上面心中所想的结构其实就是双向链表了。
如下:在这里插入图片描述
至于双向带头循环的链表:就是将头尾相连的双向链表了,这种链表结构就非常强大了,我们可以从任一点出发找到别的点。
在这里插入图片描述

算了来张百度百科的图片
在这里插入图片描述
现在来创建一个双向链表的结构:
其实就是多了一个prev指针的链表结构。

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LDataType data;
}ListNode;

双向链表的相关函数

初始化创建

注意创建就是指需要有一个头节点,对于双向链表来说,起码得有一个节点的,不然的话那算?算空气。这个节点首先就是自己链接自己的。

ListNode* ListCreate()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

新建一个节点

ListNode* BuyListNode(LDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

头插

头插的两种方式,一种是复用后面的在pos位置插入(对于头插来说pos就是phead->next,注意这里不是phead,phead->next才是指头插),另一种直接实现

复用

void ListPushFront(ListNode* phead, LDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

不复用

void ListPushFront(ListNode* phead, LDataType x)
{
	assert(phead);
	assert(phead->next != phead);//只有一个头节点的时候不要删除了
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

尾插

尾插也是两种实现,依旧是使用pos插入,此时pos是phead,头是连着尾的

复用

void ListPushBack(ListNode* phead, LDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}

不复用

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

头删

头删的时候注意要讨论不要删除最后的一个节点

复用


void ListPopFront(ListNode* phead)
{
	ListErase(phead->next);//复用头删
}

不复用

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* first = phead->next;
	ListNode* firstNext = first->next;
	phead->next = firstNext;
	firstNext->prev = phead;
	free(first);
}

尾删

尾删同理,至少保留一个节点~~

void ListPopBack(ListNode* phead)
{
	ListErase(phead->prev);
}
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

打印节点

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

查找

ListNode* ListFind(ListNode* phead, LDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;//指向头节点的next才是真实的值域
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

pos处插入节点

前面使用的头插尾插就是复用这个地方,对于为什么头插是phead->next,尾插是phead
在这里插入图片描述

void  ListInsert(ListNode* pos, LDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newNode = BuyListNode(x);
	prev->next = newNode;
	newNode->prev = prev;
	pos->prev = newNode;
	newNode->next = pos;
}

pos处删除节点

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

判断是否为空

int ListEmpty(ListNode* phead)
{
	return phead->next == phead ? 1 : 0;
}

判断大小

int ListSize(ListNode* phead)
{
	assert(phead);
	int len = 0;
	ListNode* cur = phead->next;//指向头节点的next才是真实的值域
	while (cur != phead)
	{
		len++;
		cur = cur->next;
	}
	return len;
}

销毁操作

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>