hello 大家好呀,Today I will share with you the implementation of the double-linked list addition, deletion, search and modification interface,If there is anything wrong, I hope you guys can help me correct it.

This time, the blogger shared the bidirectional circular linked list：

---

目录

 

 

1 初始化链表

2 尾插和头插

 3 尾删和头删

4 Find and insert and delete）

5 释放

---

 

 

1 初始化链表

ListNode* ListNodeCreat(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode)
	{
		newnode->data = x;
		newnode->next = NULL;
		newnode->prev = NULL;
	}
	return newnode;
}


ListNode* InitList(void)
{
	ListNode* phead = ListNodeCreat(1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

The initialization of the linked list we willphead的prev与next都指向phead,The processing here has some magical uses in the back,这里就先不说了,The header node is implemented here by returning a value,当然,It is also possible to pass a secondary pointer,效果都差不多.The head node does not store data,Just act as a sentinel.

2 尾插和头插

The specific code of the tail insertion：

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newtail = ListNodeCreat(x);
	tail->next = newtail;
	newtail->prev = tail;
	newtail->next = phead;
	phead->prev = newtail;

	//ListInsert(phead, x);
}

The implementation of the tail plug is very simple,can understand.Here we can see willphead的prev与next都指向phead的好处了,就算pheadNone of the latter nodes can still be processed,This makes writing code very concise.

The specific code of the header：

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* next = phead->next;
	ListNode* newnode = ListNodeCreat(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;

	//ListInsert(phead->next, x);
}

The implementation of the header plug is also relatively simple,In fact, a good picture can solve the problem,Here, there is no node behind the head node and it can also be processed.

来看看效果：

 3 尾删和头删

Tail deletion and head deletion are also relatively simple for doubly linked lists,Write it together here：

void ListPopBack(ListNode* phead)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);

	//ListErase(phead->prev);
}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	ListNode* next = phead->next->next;
	free(phead->next);
	phead->next = next;
	next->prev = phead;

	//ListErase(phead->next);
	
}

按部就班的写,Be careful not to miss outok了.

效果：

4 Find and insert and delete）

Find the specific code：

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

与单链表一样,This can also change the data：

 Check out the specific code：

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

这里是在posData is inserted before the bit,实现起来也比较简单.

The specific code to check and delete：

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

It is not difficult to find out after checking and deleting and checking and inserting,Both head and tail plugs can be implemented with check and plug,Both head deletion and tail deletion can be implemented with search and deletion.

头插在 phead->next前插入,尾插在phead前插入,The header delete position is phead->next,The tail deletion position is phead->prev.

This is the method that is commented out when implementing the code above.

5 释放

void ListDestroy(ListNode* phead)
{
	ListNode* cur = phead;
	ListNode* next = phead->next;
	while (cur->next!=phead)
	{
		free(cur);
		cur = next;

		next = next->next;
	}
	
}

A free linked list is similar to a singly linked list,比较容易理解.

好了,今天的分享就到这里了,如果该文对你有帮助的话能不能3连支持一下博主呢？