数据结构之链表（双链表）

目录

一、双向带头循环链表

概念

 二、哨兵位的头节点

优点：

头节点的初始化

三、带头双向链表的实现

1.双链表的销毁

2.双链表的打印

3.双链表的尾插和头插

尾插：

头插：

4.双链表的尾删和头删

尾删：

头删：

5.双链表的查找

四、测试代码

一、双向带头循环链表

概念

        名如其实，这个链表结构有哨兵位头节点，双向并且循环，结构最复杂。一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了这里我们用一张图片就能很好的看清楚双向带头循环链表的结构了。

 二、哨兵位的头节点

        从上一篇文章我们就在说带头/不带头，那么这个头是什么呢？其实它就是哨兵位的头节点。这个节点一般在一个链表的最前方的位置，不用来储存数据。

优点：

1.    简化边界条件处理：
•    在没有哨兵节点的情况下，链表的头插、头删等操作需要特别处理头节点为空的情况。
•    使用哨兵节点后，头节点始终存在，简化了插入和删除操作的逻辑，不需要单独处理头节点为空的情况。

2.    统一操作逻辑：
•    无论是头插、尾插、头删还是尾删，操作逻辑都可以统一处理，不需要区分是否是第一个节点。
•    例如，插入操作总是插入到哨兵节点之后，删除操作总是删除哨兵节点之后的节点。

3.    提高代码可读性和维护性：
•    由于边界条件处理简化，代码逻辑更加清晰，减少了出错的可能性。
•    代码维护起来也更加方便，因为不需要在多个地方处理特殊情况。
4.    便于实现某些算法：
•    在某些算法中，使用哨兵节点可以避免多次检查链表是否为空的情况，提高算法的效率。

头节点的初始化

// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	newnode->data = 0;
	newnode->next = newnode;
	newnode->prev = newnode;
	return newnode;
}

三、带头双向链表的实现

1.双链表的销毁

        与单链表的销毁类似，需要定义一个指针来遍历整个链表，但是注意，如果是从头节点开始遍历，我们会因为无法很好的控制停止条件而导致无限循环，所以我们从头节点的下一个开始遍历，当这个cur指针指向头节点时就停止，这里后面还会反复用到，请务必想清楚。

// 双向链表销毁
void ListDestory(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(plist);
	plist = NULL;
}

2.双链表的打印

// 双向链表打印
void ListPrint(ListNode* plist)
{
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		printf("%d<=>",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.双链表的尾插和头插

尾插：

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
	// 双向链表的找尾很简单，只需要指向plist的前一个节点就行
	ListNode* newnode = buyNewnode(x);
	ListNode* tail = plist->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = plist;
	plist->prev = newnode;
}

头插：

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* newnode = buyNewnode(x);
	ListNode* head = plist->next;
	plist->next = newnode;
	newnode->prev = plist;
	newnode->next = head;
	head->prev = newnode;
}

4.双链表的尾删和头删

尾删：

// 双向链表尾删
void ListPopBack(ListNode* plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return;
	}
	ListNode* tail = plist->prev;
	ListNode* prev = tail->prev;
	free(tail);
	tail = NULL;
	prev->next = plist;
	plist->prev = prev;
}

头删：

// 双向链表头删
void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (plist->next = plist)
	{
		return;
	}
	ListNode* head = plist->next;
	ListNode* newHead = head->next;
	free(head);
	head = NULL;
	plist->next = newHead;
	newHead->prev = plist;
}

5.双链表的查找

// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

四、测试代码

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next; 
	struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* buyNewnode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
ListNode* ListCreate()
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	newnode->data = 0;
	newnode->next = newnode;
	newnode->prev = newnode;
	return newnode;
}
// 双向链表销毁
void ListDestory(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(plist);
	plist = NULL;
}
// 双向链表打印
void ListPrint(ListNode* plist)
{
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		printf("%d<=>",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
	// 双向链表的找尾很简单，只需要指向plist的前一个节点就行
	ListNode* newnode = buyNewnode(x);
	ListNode* tail = plist->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = plist;
	plist->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return;
	}
	ListNode* tail = plist->prev;
	ListNode* prev = tail->prev;
	free(tail);
	tail = NULL;
	prev->next = plist;
	plist->prev = prev;
}
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* newnode = buyNewnode(x);
	ListNode* head = plist->next;
	plist->next = newnode;
	newnode->prev = plist;
	newnode->next = head;
	head->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (plist->next = plist)
	{
		return;
	}
	ListNode* head = plist->next;
	ListNode* newHead = head->next;
	free(head);
	head = NULL;
	plist->next = newHead;
	newHead->prev = plist;
}
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
int main()
{
	ListNode* plist = ListCreate();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPrint(plist);

	ListPopBack(plist);
	ListPrint(plist);

	ListPushFront(plist, 0);
	ListPrint(plist);

	ListPopFront(plist);
	ListPrint(plist);

	return 0;
}