初阶数据结构-双向链表

双向链表的概念

  链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

哨兵位

为什么要有哨兵位呢？
1.对于一个已经创建和初始化的链表来讲，可以没有数据，即头节点，尾节点等，但是不能没有哨兵位，因为哨兵位并不是帮我们存储数据的，只是来定位链表的。即使是一个空链表，它也会有哨兵位，所以我们可以用哨兵位是否为空来检测程序运行情况。
2.对于链表来讲，一个很重要的地方就是头的位置，而哨兵位则可以起到定位头的作用，它的下一个节点就是头节点。
3.在双向循环链表中，如果我们要遍历，那么很难去说明结束条件，而我们可以用哨兵位来作为结束条件，当当前节点为哨兵位时，遍历结束。

链表的分类

  1. 单向或者双向2. 带头或者不带头3. 循环或者非循环

双向链表的基本功能

//初始化
LTNode* LTInit( );
//打印
void LTPrint(LTNode* phead);
//判断是否为空
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的值
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);

双向链表的创建

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

双向链表节点的创建

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

双向链表的初始化

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

双向链表的打印

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

双向链表判断是否为空

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

双向链表的尾插

将tail的next指针指向newnode，将newnode的prev指针指向tail，将newnode的next指针指向phead，最后将phead的prev指针指向newnode

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail -> next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;*/

	LTInsert(phead, x);
}

双向链表的头插

将newnode的next指针指向phead的next，将phead的next指针指向newnode，将phead的next指针指向newnode，将newnode的prev指针指向phead

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

	newnode->next = phead->next;
	phead->next = newnode;

	phead->next = newnode;
	newnode->prev = phead;
}

//void LTPushFront(LTNode* phead, LTDataType x)
//{
	//assert(phead);
	/*LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;*/

	//LTInsert(phead->next, x);
}

双向链表的头删

将phead的next指针指向next的next，将phead的next的prev指针指向phead，释放next指针

//void LTPopFront(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//
//	LTNode* next = phead->next;
//
//	/*phead->next = next->next;
//	phead->next->prev = phead;*/
//
//	phead->next = next->next;
//	next->next->prev = phead;
//	free(next);
//}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	/*LTNode* first = phead->next;
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);*/

	LTErase(phead->next);
}

双向链表的尾删

释放掉tail，将tailprev的next指针指向phead，将phead的prev指针指向tailprev

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	/*LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;*/

	LTErase(phead->prev);
}

双向链表的查找

遍历双向链表查找值为x的位置

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

双向链表的pos位置插入

将prev的next指针指向newnode，将newnode的prev指针指向prev，将newnode的next指针指向pos，将pos的prev指针指向newnode

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

	//prev newnode pos
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

双向链表的pos位置删除

将posPrev的next指针指向posNext，将posNext的prev指针指向posPrev

void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

双向链表的销毁

从第一个指针向后进行释放，再将cur的指针指向下一个节点

void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

双向链表的测试主函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"


void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);

	LTPopBack(plist);

	LTPrint(plist);
}


void TestList2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);

	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);
}

int main()
{
	TestList1();
	return 0;
}