【零基础学数据结构】双向链表

1.双向链表的概念

1.1头节点 

 1.2带头双向循环链表

注意： 哨兵位创建后，首尾连接自己

1.3双链表的初始化

// 创建节点
ListNode* ListBuyNode(ListDatatype x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc err!");
		exit(1);
	}
 
	node->data = x;
	node->next = node->prev = node; //哨兵位创建后，首尾连接自己
 
	return node;
}
 
// 双向链表的初始化
void ListInit(ListNode** pphead)
{
	// 给双链表创建一个哨兵位
	*pphead = ListBuyNode(-1);
}

相当于给头节点也就是哨兵位附上一个无效值，我们在后续的操作中不可以访问哨兵位，它的作用只是一个向导。 

2.双向链表的打印 

// 双向链表的打印
void ListPrint(ListNode* phead)
{
	// 遍历链表
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		// 打印
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

每次打印需要检查所传的值避开头节点， 我们第一个打印的值要从头节点的下一个节点开始，知道遍历链表走到头节点结束。

 3.双向链表的尾插 

// 双向链表的尾插
void ListPushBack(ListNode* phead, ListDatatype x)
{
	// 创建一个存放数据的新节点
	ListNode* newnode = ListBuyNode(x);
 
	// 进行尾插
	// 新节点连接
	newnode->prev = phead->prev;
	newnode->next = phead;
 
	// 改变原来链表的连接
	phead->prev->next = newnode;
	phead->prev = newnode;
}

尾插我们需要注意的是先要创建一个新的节点储存我要插入的值，在链表连接的时候首先把新创建节点的首尾相连，这样可以避免因为改动了原链表的指向而导致的问题！

如：我们先用(phead->prev)节点的*next指向了新节点(newnode)， 那么原本d3(phead->prev)的指向就会被覆盖，后续难以找到。

4.双向链表的头插 

void ListPushFront(ListNode* phead, ListDatatype x)
{
	// 创建一个存放数据的新节点
	ListNode* newnode = ListBuyNode(x);
 
	// 进行头插
	// 新节点连接
	newnode->prev = phead;
	newnode->next = phead->next;
 
	// 改变原来链表的连接
	phead->next->prev = newnode;
	phead->next = newnode;
}

和尾插的操作差不多，要注意先新后原——先连接新链表，后更改原来的链表。 

5.双向链表的尾删 

void ListPopBack(ListNode* phead)
{
	assert(phead && phead->next != phead);
 
	// 进行尾删除
	ListNode* del = phead->prev;// 这边创建del方便理解，不然指向过多太乱
	del->prev->next = del->next; 
	del->next->prev = del->prev;
 
	// 释放空间
	free(del);
	del = NULL;
}

6.双向链表的头删 

void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);
 
	// 进行头删除
	ListNode* del = phead->next;// 这边创建del方便理解，不然指向过多太乱
	del->next->prev = phead;
	phead->next = del->next;
 
	// 释放空间
	free(del);
	del = NULL;
}

7.双向链表的查找  

ListNode* ListFind(ListNode* phead, ListDatatype x)
{
	// 遍历双向链表
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		// 打印
		if (pcur->data == x)
		{
			return pcur;//如果找到返回节点
		}
		pcur = pcur->next;
	}
 
	// 没有找到
	return NULL;
}

 8.双向链表在pos位置之后插入 

void ListInsret(ListNode* pos, ListDatatype x)
{
	assert(pos);
 
	// 创建一个存放数据的新节点
	ListNode* newnode = ListBuyNode(x);
 
	// 插入
	// 新节点连接
	newnode->prev = pos;
	newnode->next = pos->next;
 
	// 原链表连接
	pos->next->prev = newnode;
	pos->next = newnode;
}

9.双向链表删除pos节点 

void ListErase(ListNode* pos)
{
	//pos理论上来说不能为phead，但是没有参数phead，无法增加校验
	assert(pos);
 
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
 
	free(pos);
	pos = NULL;
}

 10.双向链表的销毁

void ListDesTroy(ListNode* phead)
{
	assert(phead);
 
	// 遍历删除
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead，而phead还没有被销毁
	free(phead);
	phead = NULL;
	printf("销毁成功！");
}

销毁链表需要从头一个一个往下删除释放空间，我们创建pcur指针指向头节点，而next指针指向下一个节点，next指针的作用是防止我们删除当前节点时找不到下一个节点了。循环遍历删除，直到最后删除头节点（哨兵位）。 

 测试文件：用于检验代码执行的有效性

#include "List.h"
 
void ListNodetext()
{
	ListNode* plist;
	ListInit(&plist);
 
	// 测试尾插
	ListPushBack(plist, 1);
	/*ListPrint(plist);*/
	ListPushBack(plist, 2);
	/*ListPrint(plist);*/
	ListPushBack(plist, 3);
	ListPrint(plist); // 1->2->3->
 
	// 测试头插
	//ListPushFront(plist, 6);
	//ListPrint(plist);
	//ListPushFront(plist, 7);
	//ListPrint(plist);
	//ListPushFront(plist, 8);
	//ListPrint(plist);
 
	// 测试尾删
	//ListPopBack(plist);
	//ListPrint(plist);
	//ListPopBack(plist);
	//ListPrint(plist);
	//ListPopBack(plist);
	//ListPrint(plist);
 
	// 测试头删
	//ListPopFront(plist);
	//ListPrint(plist);
	//ListPopFront(plist);
	//ListPrint(plist);
	//ListPopFront(plist);
	//ListPrint(plist);
 
	// 测试查找
	//ListNode* find = ListFind(plist, 30);
	//if (find == NULL)
	//{
	//	printf("没有找到！");
	//}
	//else
	//{
	//	printf("找到了！");
	//}
 
	// 测试pos位置之后插入
	//ListNode* find = ListFind(plist, 2);
	//ListInsret(find, 5);
	//ListPrint(plist);
 
	// 测试删除pos节点
	//ListNode* find = ListFind(plist, 3);
	//ListErase(find);
	//find = NULL;
	//ListPrint(plist);
 
	ListDesTroy(plist);
	plist = NULL;
}
 
int main()
{
	ListNodetext();
	return 0;
}