数据结构——双向链表

首先我们要介绍一下链表的分类

链表的分类

链表说明： 

虽然有这么多种链表结构，但是我们实际中用的还是两种结构：单链表（单向不带头不循环）和 双向带头循环链表 。

单链表（单向不带头不循环）：

结构简单，一般不会单独用来存数据。实际中更多是作为其它数据结构的子式。

双向带头循环链表 ：

结构最复杂，一般用来单独存储数据。实际中使用的链表结构，都是带头双向循环链表。

双向链表 

概念与结构

我们这里说的双向链表指的是双向带头循环链表。

双向链表的实现

Q1:双向链表怎么创建结构体？

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

 Q2：双向链表怎么初始化？

初始时，链表为空，我们先要创造一个头结点

为了体现循环，head->prev和head->next都应该是指向头结点的位置。 

为了体现头结点的位置，我们创建一个pphead指针，为了通过函数改变pphead指向的位置，我们需要传值调用，使用二级指针。

LTNode* BuyNode(LTDataType x)
{
	LTNode* newnode =(LTNode*) malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}
LTNode* LTInit(LTNode** pphead)
{
	*pphead = BuyNode(0);
	(*pphead)->prev = *pphead;
	(*pphead)->next = *pphead;
	return *pphead;
}

双向链表的实现

尾插

void ListPushBack(LTNode* pHead, LTDataType x)
{
	assert(pHead);
	LTNode* newnode = BuyNode(x);
	newnode->prev = pHead->prev;
	newnode->prev->next = newnode;
	pHead->prev = newnode;
	newnode->next = pHead;
}

 头插

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

头删

void ListPopFront(LTNode* pHead)
{
	assert(pHead && pHead->next!=pHead);
	LTNode* del = pHead->next;
	pHead->next = del->next;
	del->next->prev = pHead;
	free(del);
	del = NULL;
}

尾删

void ListPopBack(LTNode* pHead)
{
	assert(pHead && pHead->prev!=pHead);
	LTNode* del = pHead->prev;
	del->prev->next = pHead;
	pHead->prev = del->prev;
	free(del);
	del = NULL;
}

 查找

LTNode* ListFind(LTNode* pHead, LTDataType x)
{
	assert(pHead && pHead->next);
	LTNode* pcur = pHead->next;
	while (pcur != pHead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

在pos之前插入

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

删除pos位置的结点

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

打印

void ListPrint(LTNode* pHead)
{
	LTNode* pcur = pHead->next;
	while (pcur != pHead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("pHead");
}

销毁

void ListDestory(LTNode** ppHead)
{
	assert(ppHead && *ppHead);
	LTNode* pcur = (*ppHead)->next;
	LTNode* next = pcur->next;
	while (pcur != *ppHead)
	{
		free(pcur);
		pcur = next;
		next = next->next;
	}
	free(*ppHead);
	*ppHead = NULL;
	pcur = NULL, next = NULL;
}