数据结构——双向链表

双向链表

1.双向链表的定义

        我们之前学过单链表，也就是无头单向非循环链表。那么我们今天学的是带头双向循环链表。虽然它的结构相较于单链表复杂一些，但在实际应用中具有很好的应用意义。

        带头的意思就是带有一个哨兵位的头结点，此结点用来存放头结点，不存放有效数据。之前单向链表只可以指向下一个链表，双向就可以指向上一个。循环则是指可以从最后一个链表循环到第一个。

定义代码如下：

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

2.双向链表的基本操作

（1）双向链表建立结点

LTNode* BuyLTNode(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;

	return node;
}

（2）双向链表的初始化

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

（3）打印双向链表

        这里有个很有意思的地方，注意看循环判断条件是：cur！=phead，也就是说当cur==phead的时候跳出循环。这是因为这是一个循环链表，当cur==phead的时候说明已经又到了头结点，说明已经遍历结束了。大家可以再体会一下这个思想。

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

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

（4）双向链表的尾插

        要实现尾插，我们只需要找到尾，按照双向循环链表的特点，head的prev指向尾结点，所以我们定义一个tail指针，从而实现尾插。

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	newnode->prev = tail;
	tail->next = newnode;

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


	/*LTInsert(phead, x);*/
}

（5）双向链表的头插

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

	/*LTNode* newnode = BuyLTNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

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

	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;

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

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

（6）双向链表的尾删

        尾删只需要找到尾结点，再将尾结点的前驱节点记录下来，然后释放尾结点，再将前驱和头结点之间连接起来就可以实现。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

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

	tailPrev->next = phead;
	phead->prev = tailPrev;

	/*LTErase(phead->prev);*/
}

（7）双向链表的头删

        大家思考一下，怎么进行头删？是不是和尾删是一样的思路，只不过这次找到的是第一个结点和第二个结点，释放第一个结点，然后改变头结点和第二个结点的指向关系。

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

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

	//free(first);

	//phead->next = second;
	//second->prev = phead;

	LTErase(phead->next);
}

（8）获取双向链表的数据个数

int LTSize(LTNode* phead)
{
	assert(phead);

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

	return size;
}

（9）pos位置之前进行插入

// pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

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

（10）在pos位置进行删除

// 删除pos位置
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	free(pos);

	posPrev->next = posNext;
	posNext->prev = posPrev;
}

（11）双向链表的销毁

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

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

3.双向链表妙用——pos位置前插入

        我们先再来看一下pos位置前进行插入：

那如果我现在要头插，根据LTInsert函数，我的参数应该如何定义？头插就是在一个位置处，所以是我们要插入的位置就是phead->next。

LTInsert(phead->next, x)

那么尾插呢？大家仔细思考一下，是在tail后面吗？实际上呢，尾插的位置就是phead。在pos位置之前插入，那么在phead之前插入，不就是在tail之后插入。

LTInsert(phead, x)