C语言双向链表

前言

假期时间因为为学校开学考试做准备所以一直没更新博客，今天开始博客会陆续更新。

双向链表

之前我们说过了顺序表和单链表，这次介绍双向链表，双向链表在使用上要比单链表简单，结构比单链表复杂一些，需要两个指针域，其结构如下图，其中头结点数据域不动（不要存放指针长度一类因为有时候我们不确定链表节点数据类型，如果是char类型而节点数大于128，那么就会出现bug），带有头结点可方便对其操作。

双向链表节点代码如下：

typedef int LTDataType;
typedef struct ListNode {
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}LTNode;
1
2
3
4
5
6

与单链表相同无非是双向链表的增删改查。

链表头结点的创建

ListNode* ListCreate()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	head->next = head;
	head->prev = head;
	return head;
}
1
2
3
4
5
6
7

这里别忘了是双向链表，要给两个指针都赋值，因为是头结点（PS：头结点数据域一般是垃圾值）所以就指向自己。

节点尾插与尾删

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	ListNode* tail = pHead->prev;
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11

这里就体现出双向链表的优势，我们不用遍历就可以直接找到链表的尾结点。

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	ListNode* tail = pHead->prev;
	ListNode* TailPrev = tail->prev;
	free(tail);
	TailPrev->next = pHead;
	pHead->prev = TailPrev;
}
1
2
3
4
5
6
7
8
9

尾插时不要忘了让节点指向头结点。

节点头插与头删

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = pHead->next;
	pHead->next->prev = newnode;
	pHead->next = newnode;
	newnode->prev = pHead;
}
1
2
3
4
5
6
7
8
9
10

这里注意哈，链表的头插与头删是在头结点之后位置进行，这里例出一幅头插图作为参考（艺术细胞为0后续可能解锁画图软件，这里先凑合看）。

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
	cur = pHead->next;
	pHead->next = cur->next;
	cur->next->prev = pHead;
	free(cur);
}
1
2
3
4
5
6
7
8
9

头插和头删要注意顺序，否则可能找不到头结点的下一个节点。

特定位置插入或删除节点

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这里还是注意一下代码顺序无其他重点。

链表节点查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return pHead;
}
1
2
3
4
5
6
7
8
9
10
11
12

若最后没有找到该数值则返回头结点。

双向链表的销毁

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	ListNode* newhead = pHead->next;
	ListNode* cur = newhead->next;
	while (cur->next!=pHead)
	{
		free(newhead);
		newhead = cur;
		cur = newhead->next;
	}
	free(pHead);
	pHead == NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里别忘了最后删除并置空头结点，置空头结点的原因是使用者在主函数还有头结点的地址，但此时头结点已被释放（野指针），若再次调用头结点则可能出现bug。

链表的打印

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	ListNode* newnode = pHead->next;
	while (newnode!=pHead)
	{
		printf("%d ", newnode->next->data);
		newnode = newnode->next;
	}
}
1
2
3
4
5
6
7
8
9
10

比较简单，不做赘述。
双向链表许多函数的while循环是判断其节点是否与头结点相等，而不是其节点是否为空，这里要注意与单链表区分，最后代码其实还应该加上断言（assert）函数判断是否为空，但博主这里没有加（是故意的还是不小心的）。

这里纯粹是懒得加了，这个习惯不是很好，大家不要学我，最好还是自己加一下。
最后期待你的三连，若有错误欢迎私信或评论区指出。