Data structure - c language to realize basic operations such as adding, deleting, searching and modifying the leading circular double linked list (super long and super detailed)

1, Basic cognition

What is a cycle

The last node of the linked list points to the head node, forming a ring. Therefore, any other node can be found from any node in the circular linked list.

What is a double linked list

Two pointers are stored in the structure of the linked list, one pointing to the predecessor node and the other pointing to the successor node.

Basic structure

As shown in the figure, data is the stored number, prev and next point to the predecessor node and the successor node respectively.

2, Realize

1. Initialization

Initialization is to create a head node and return the head node.
Since it is a double linked list, initialization is to create this head node. Even if there is only one head node, it must abide by the rules and point to itself. Here I spent a picture to make it easy for everyone to understand.

Only one head node
The following is the code directly!

LTNode* SLTInit()
 6	{
 7		LTNode* phead= (LTNode*)malloc(sizeof(LTNode));
 8		phead->next = phead;
 9		phead->prev = phead;
 10		return phead;
 11	}
 12	

2. Head insertion method

First, create a new node to store data. Here, call the "create node" function. I put the "create node" function on the last side. Students who don't know it will go on to look.

Here, insert one end to the front of the list.

void LTPushFront(LTNode* phead, LTDataType x)
 51	{
 52		assert(phead != NULL);
 53		LTNode* newnode = BuyLTNode(x);
 54		LTNode* next = phead->next;
 55	
 56	
 57	
 58		phead->next = newnode;
 59		newnode->next = next;
 60		newnode->prev = phead;
 61		next->prev = newnode;
 62	
 63	}
 64	

3. Tail insertion method

void LTPhshBack(LTNode* phead, LTDataType x)
 21	{
 22		assert(phead != NULL);
 23		LTNode* newnode=BuyLTNode(x);
 24		LTNode* tail = phead->prev;
 25		
 26	
 27		tail->next = newnode;
 28		newnode->prev = tail;
 29	
 30		newnode->next = phead;
 31		phead->prev = newnode;
 32	
 33	}
 34	

4. Head deletion method

void LTPopFront(LTNode* phead)
 81	{
 82		assert(phead != NULL);
 83		assert(phead->next != NULL);
 84	
 85		LTNode* next = phead->next;
 86		LTNode* nextNext= next->next;
 87		phead->next = nextNext;
 88		nextNext->prev = phead;
 89		free(next);
 90		next = NULL;
 91	
 92	}
 93	

4. Tail deletion method

void LTPopBack(LTNode* phead) 
 66	{
 67		assert(phead != NULL);
 68		//Cannot delete sentinel position
 69		assert(phead->next != phead);
 70		LTNode* tail = phead->prev;
 71		LTNode* cur = tail->prev;
 72		cur->next = phead;
 73		phead->prev = cur;
 74		
 75		tail = NULL;
 76		free(tail);
 77	}
 78	

5. Search function

LTNode* LTFind(LTNode* phead, LTDataType x)
 96	{
 97		assert(phead != NULL);
 98		LTNode* cur = phead->next;
 99		while (cur!=phead)
 100		{
 101			if (cur->data == x)
 102			{
 103				return cur;
 104			}
 105			cur = cur->next;
 106		}
 107		return NULL;
 108	}
 109	
 110	

6. Insert a number in a certain position

This function can be reused for head interpolation and tail interpolation.

void LTInsert(LTNode* pos, LTDataType x)
 113	{
 114		assert(pos != NULL);
 115		LTNode* newnode = BuyLTNode(x);
 116		LTNode* posPrev = pos->prev;
 117	
 118		posPrev->next = newnode;
 119		newnode->prev = posPrev;
 120	
 121		newnode->next = pos;
 122		pos->prev = newnode;
 123	
 124	}
 125	

7. Delete the number in a certain position

This function can be reused to the head deletion method and the tail deletion method.

void LTErease(LTNode* pos)
 127	{
 128		assert(pos != NULL);
 129		LTNode* posPrev = pos->prev;
 130		LTNode* posNext = pos->next;
 131	
 132		posPrev->next = posNext;
 133		posNext->prev = posPrev;
 134		free(pos);
 135		pos = NULL;
 136	
 137	

8. Create node

LTNode* BuyLTNode(LTDataType x)
 13	{
 14		LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
 15		newnode->data = x;
 16	}
 17	

 

summary

When inserting or deleting, you must remember to assert, otherwise there may be errors, but you can't find the error.
Double linked list is a storage structure that is updated on the basis of sequential list. Its advantages are that it is efficient to insert at any position, and it can apply for space on demand, without causing space waste.

Tags: C data structure linked list

Posted by kidestranged on Wed, 07 Sep 2022 21:55:27 +0300