[one · data 𞓜 simple implementation of the leading two-way circular linked list]

zero 、 All in all

  C The language simply implements each process of the leading two-way circular linked list , The code is explained in the comments .

  
  

One 、 The whole model ：

List.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>// Boolean 


// two-way 、 Take the lead 、 Circular linked list ：
typedef int LTDataType;
typedef struct ListNode
{
    
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

struct List
{
    
	LTNode* phead;
	int size;
};


// Initialization of linked list 
void ListInitform(LTNode** pphead);
// Linked list initialization improved version 
LTNode* ListInit(void);

// Linked list printing 
void ListPrint(LTNode* plist);

// The end of the linked list is inserted 
void ListPushBack(LTNode* phead, LTDataType x);
// The head of the list is inserted 
void ListPushFront(LTNode* phead, LTDataType x);
// Delete the linked list header 
void ListPopBack(LTNode* phead);
// Delete the end of the linked list 
void ListPopFront(LTNode* phead);
// stay pos Insert before position 
void ListInsert(LTNode* pos, LTDataType x);
// Delete pos A node at a location 
void ListErase(LTNode* pos);

// Calculate the length of the list 
int ListSize(LTNode* phead);

// List destruction 
void ListDestory(LTNode* phead);

  
  

Text.c

#include"List.h"

void TestList1()
{
    
	// Test linked list initialization 
	//LTNode* plist = NULL;
	//ListInit(&plist);// Note that arguments are passed 

	// Test the improved version of linked list initialization 
	LTNode* plist = ListInit();
	// Test the tail plug 
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);

	// Test header delete 
	ListPopFront(plist);
	ListPrint(plist);//1
	ListPopFront(plist);
	ListPrint(plist);//2
	ListPopFront(plist);
	ListPrint(plist);//3
	ListPopFront(plist);
	ListPrint(plist);//4
	ListPopFront(plist);
	ListPrint(plist);//5
	ListPopFront(plist);
	ListPrint(plist);// Sentry post 

}

void TestList2()
{
    
	LTNode* plist = ListInit();
	// The slave list is empty ( Only sentinel positions ) Start the test head insertion 
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);
	ListPrint(plist);

	// Test tail deletion 
	ListPopBack(plist);
	ListPrint(plist);//1
	ListPopBack(plist);
	ListPrint(plist);//2
	ListPopBack(plist);
	ListPrint(plist);//3
	ListPopBack(plist);
	ListPrint(plist);//4
	ListPopBack(plist);
	ListPrint(plist);//5
	ListPopBack(plist);
	ListPrint(plist);// Test sentry position 


}

void TestList3()
{
    
	LTNode* plist = ListInit();
	// test pos Acting on the head insert 、 Tail insertion 
	ListPushFront(plist, 1);
	ListPrint(plist);//1
	ListPushFront(plist, 2);
	ListPrint(plist);//2 1
	ListPushFront(plist, 3);
	ListPrint(plist);//3 2 1

	ListPushBack(plist, 1);
	ListPrint(plist);//3 2 1 1
	ListPushBack(plist, 2);
	ListPrint(plist);//3 2 1 1 2
	ListPushBack(plist, 3);
	ListPrint(plist);//3 2 1 1 2 3

	// test pos Act on header deletion 、 Deletion at the end 
	ListPopFront(plist);
	ListPrint(plist);//2 1 1 2 3
	ListPopFront(plist);
	ListPrint(plist);//1 1 2 3

	ListPopBack(plist);
	ListPrint(plist);//1 1 2
	ListPopBack(plist);
	ListPrint(plist);//1 1
}

int main(void)
{
    
	//TestList1();
	//TestList2();
	TestList3();
	return 0;
}

  
  

List.c

#include"List.h"


// Auxiliary function ： Dynamically open up a memory space , New node , Can be used to create a sentinel for the head 、 Tail insertion 、 Head insertion .
LTNode* BuyListNode(LTDataType x)
{
    
	// Dynamic development : Be careful malloc Details of the use of 
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)// Failed to open up 
	{
    
		perror("malloc:fail");
		exit(-1);
	}
	// When it's successful ：
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

// Initialization of linked list ： Double linked list 、 Lead and cycle 
// Refer to the previous single linked list , If it does not take the lead, it will not circulate , Initially, the linked list is empty , Point to NULL that will do ,
// But for this two-way linked list , Its lead 、 loop , So when there is no data in the linked list , At the beginning, there should be a head of sentry position , And its precursor pointer and subsequent pointer point to itself .
// details ： according to TestList1 know , To change the argument itself （ That is, the linked list pointer ）, Then the initial functionalization of the linked list here , The formal parameter needs to use the secondary pointer of the corresponding type .
void ListInitform(LTNode** pphead)
{
    
	*pphead = BuyListNode(-1);// At the beginning , Only the head node of sentry position in the linked list 
	(*pphead)->next = *pphead;// Handle subsequent pointer points to , Point it at yourself 
	(*pphead)->prev = *pphead;// The processing precursor pointer points to , Point it at yourself 
}

// Linked list initialization improved version 
// Because the above linked list initialization needs to use the secondary pointer , The improved version here uses only one level pointer ： Corresponding TestList The receiving method needs to be changed 
LTNode* ListInit(void)
{
    
	LTNode *phead = BuyListNode(-1);// Create a new pointer in the initialization function 
	phead->next = phead;
	phead->prev = phead;
	return phead;// Return the pointer address 
}




// Linked list printing 
// reflection ： Printing of double linked list , Because of its cycle 、 The reason for having a sentry post , Need to determine when to stop , And ensure that the data of sentry positions are not printed .
void ListPrint(LTNode* phead)
{
    
	assert(phead);
	LTNode* cur = phead->next;// Point to the node next to the sentry position ： That is, the sentinel position data will not be printed 
	while (cur != phead)// The conditions of judgment ： Because the linked list circulates , Will eventually return to the sentry post 
	{
    
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}




// The end of the linked list is inserted 
// reflection ： In the previously written single linked list , Two linked list tail insertion requires two-level pointers , In this type of double linked list , Whether the second level pointer is required for the end insertion of the linked list ？
// Here in the double linked list , Already contains the head of the sentry position , The tail insertion only needs to change the internal members of the node , There is no need to change the address of the node .（ namely next、prev A pointer is a member of a structure , Therefore, when passing parameters to a function, you can use a first-order pointer ）
// details ： Note the change of the pointing relationship between nodes 
void ListPushBack(LTNode* phead, LTDataType x)
{
    
	assert(phead);

	//pos The pre position insert function acts on the trailing insert ：
	ListInsert(phead, x);// Notice here phead->prev Not tail insertion 

	// Don't use Insert How to write a function ：
	// New node 
	LTNode* newnode = BuyListNode(x);
	// Change the pointer pointing relationship in the node 
	LTNode* tail = phead->prev;// Find the tail node of the original linked list 
	// change tail：
	tail->next = newnode;
	// change newnod:
	newnode->prev = tail;
	newnode->next = phead;
	// change phead:
	phead->prev = newnode;
}


// The head of the list is inserted 
// reflection ： Head insert with sentry post , You need to understand the meaning of header insertion at this time , The sentry position always occupies the theoretical head node , The header insertion here refers to the header insertion before the second node of the linked list after the sentry position .
void ListPushFront(LTNode* phead, LTDataType x)
{
    
	assert(phead);

	//pos The insert before position function acts on the header insert ：
	ListInsert(phead->next, x);

	// Don't use Insert How to write a function ：
	// New node 
	LTNode* newnode = BuyListNode(x);
	// Change the pointer pointing relationship in the node 
	LTNode* second = phead->next;// Find the node after the sentry position in the original linked list 
	// change second:
	second->prev = newnode;
	// change newnode:
	newnode->next = second;
	newnode->prev = phead;
	// change phead:
	phead->next = newnode;

	// If not used second The pointer , There are sequence requirements when changing the node pointing relationship , The following is a demonstration ：
	LTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;// Here comes phead->next, So it needs to be placed in phead->next Before being modified 
	newnode->prev = phead;
	phead->next->prev = newnode;// Here to find second node , Therefore, the modification needs to be placed in phead->next Before being modified 
	phead->next = newnode;
}


// Auxiliary delete function 
bool ListEmpty(LTNode* phead)
{
    
	assert(phead);
	return phead->next == phead;
	// If the judgment is true , return ture, It means that only the sentinel position head is left in the linked list ;
	// If the sentence is false , return false, Indicates that there are still valid nodes in the linked list 
}


// Delete the end of the linked list 
// reflection ： This two-way lead cycle linked list , It reflects the benefits of tail deletion , There is no need to traverse when finding the tail . A tailprev, And the above head second equally , It can facilitate the modification of the subsequent node relationship .
// This method is still applicable when there is only one valid node , When the linked list is empty ( Only the head node of the sentry position ), Need extra treatment .
void ListPopBack(LTNode* phead)
{
    
	assert(phead);
	assert(!ListEmpty(phead));// Other writing methods ：assert(phead->next!=phead);

	// With the help of Ereas How to write a function ：( These two assertions still need )
	ListErase(phead->prev);


	// Don't use Erase How to write a function ：
	// Deletion at the end , Find the tail node , Find the new tail node after tail deletion 
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	// Change relationships 
	phead->prev = tail->prev;
	tailprev->next = phead;
	// Release the node to be deleted 
	free(tail);
}


// Delete the linked list header 
// reflection ： As with header insertion, it is necessary to find out the effective header nodes and the pointing relationship between the remaining nodes after deletion 
void ListPopFront(LTNode* phead)
{
    
	assert(phead);
	assert(!ListEmpty(phead));

	// With the help of Ereas How to write a function ：( These two assertions still need )
	ListErase(phead->next);

	// Don't use Erase How to write a function ：
	// Head deletion , Valid header nodes , New valid header node 
	LTNode* second = phead->next;
	LTNode* secondnext = second->next;
	// Change the direction 
	phead->next = secondnext;
	secondnext->prev = phead;
	// Release nodes 
	free(second);
}





//pos Insert... Before position 
// reflection ： Take the lead in two-way linked list , stay pos Insert... Before position ,prev The existence of the pointer , No need to traverse to find pos Location 
void ListInsert(LTNode* pos, LTDataType x)
{
    
	assert(pos);
	// Determine the pointer 
	LTNode* posprev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	// Modify the relationship 
	// Yes newnode：
	newnode->next = pos;
	newnode->prev = posprev;
	// Yes pos：
	pos->prev = newnode;
	// Yes posprev：
	posprev->next = newnode;
}



//pos Delete... At location 
void ListErase(LTNode* pos)
{
    
	assert(pos);
	// Determine the desired pointer ：
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	// Modify the relationship ：
	posprev->next = posnext;
	posnext->prev = posprev;
	// Delete node ：
	free(pos);
}



// Find the length of the list 
// Ideas ： Go through the count , Time complexity O(N)
int ListSize(LTNode* phead)
{
    
	assert(phead);
	LTNode* cur = phead;
	int size = 0;
	while (cur != phead)
	{
    
		size++;
		cur = cur->next;
	}
	return size;
}
// To keep the time complexity of this function consistent with other functions （ That is, do not traverse the linked list ）,
// One method is applicable to the data Used to count the length of the linked list , But this method has bug,
// In the structure data The type is LTDataType, if char type , Then the storage nodes are limited , It will overflow .（ This method can be used selectively to determine the length of the linked list ）
// To actually solve this problem , It is more convenient to use the structure association mode , Or you can use a static variable to do 




// List destruction 
void ListDestory(LTNode* phead)
{
    
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
    
		LTNode* next = cur->next;
		ListErase(cur);
		cur = next;
	}
	free(phead);
}

  
  

Two 、 Block mode ( The appended drawings )：

initialization

// Auxiliary function ： Dynamically open up a memory space , New node , Can be used to create a sentinel for the head 、 Tail insertion 、 Head insertion .
LTNode* BuyListNode(LTDataType x)
{
    
	// Dynamic development : Be careful malloc Details of the use of 
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)// Failed to open up 
	{
    
		perror("malloc:fail");
		exit(-1);
	}
	// When it's successful ：
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

// Initialization of linked list ： Double linked list 、 Lead and cycle 
// Refer to the previous single linked list , If it does not take the lead, it will not circulate , Initially, the linked list is empty , Point to NULL that will do ,
// But for this two-way linked list , Its lead 、 loop , So when there is no data in the linked list , At the beginning, there should be a head of sentry position , And its precursor pointer and subsequent pointer point to itself .
// details ： according to TestList1 know , To change the argument itself （ That is, the linked list pointer ）, Then the initial functionalization of the linked list here , The formal parameter needs to use the secondary pointer of the corresponding type .
void ListInitform(LTNode** pphead)
{
    
	*pphead = BuyListNode(-1);// At the beginning , Only the head node of sentry position in the linked list 
	(*pphead)->next = *pphead;// Handle subsequent pointer points to , Point it at yourself 
	(*pphead)->prev = *pphead;// The processing precursor pointer points to , Point it at yourself 
}

// Linked list initialization improved version 
// Because the above linked list initialization needs to use the secondary pointer , The improved version here uses only one level pointer ： Corresponding TestList The receiving method needs to be changed 
LTNode* ListInit(void)
{
    
	LTNode *phead = BuyListNode(-1);// Create a new pointer in the initialization function 
	phead->next = phead;
	phead->prev = phead;
	return phead;// Return the pointer address 
}

  
  

Tail insertion

// The end of the linked list is inserted 
// reflection ： In the previously written single linked list , Two linked list tail insertion requires two-level pointers , In this type of double linked list , Whether the second level pointer is required for the end insertion of the linked list ？
// Here in the double linked list , Already contains the head of the sentry position , The tail insertion only needs to change the internal members of the node , There is no need to change the address of the node .（ namely next、prev A pointer is a member of a structure , Therefore, when passing parameters to a function, you can use a first-order pointer ）
// details ： Note the change of the pointing relationship between nodes 
void ListPushBack(LTNode* phead, LTDataType x)
{
    
	assert(phead);

	//pos The pre position insert function acts on the trailing insert ：
	ListInsert(phead, x);// Notice here phead->prev Not tail insertion 

	// Don't use Insert How to write a function ：
	// New node 
	LTNode* newnode = BuyListNode(x);
	// Change the pointer pointing relationship in the node 
	LTNode* tail = phead->prev;// Find the tail node of the original linked list 
	// change tail：
	tail->next = newnode;
	// change newnod:
	newnode->prev = tail;
	newnode->next = phead;
	// change phead:
	phead->prev = newnode;
}

  
  

Head insertion

// The head of the list is inserted 
// reflection ： Head insert with sentry post , You need to understand the meaning of header insertion at this time , The sentry position always occupies the theoretical head node , The header insertion here refers to the header insertion before the second node of the linked list after the sentry position .
void ListPushFront(LTNode* phead, LTDataType x)
{
    
	assert(phead);

	//pos The insert before position function acts on the header insert ：
	ListInsert(phead->next, x);

	// Don't use Insert How to write a function ：
	// New node 
	LTNode* newnode = BuyListNode(x);
	// Change the pointer pointing relationship in the node 
	LTNode* second = phead->next;// Find the node after the sentry position in the original linked list 
	// change second:
	second->prev = newnode;
	// change newnode:
	newnode->next = second;
	newnode->prev = phead;
	// change phead:
	phead->next = newnode;

	// If not used second The pointer , There are sequence requirements when changing the node pointing relationship , The following is a demonstration ：
	LTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;// Here comes phead->next, So it needs to be placed in phead->next Before being modified 
	newnode->prev = phead;
	phead->next->prev = newnode;// Here to find second node , Therefore, the modification needs to be placed in phead->next Before being modified 
	phead->next = newnode;
}

  
  

Head insertion 、 Tail insertion test results

  
  

Deletion at the end

// Auxiliary delete function 
bool ListEmpty(LTNode* phead)
{
    
	assert(phead);
	return phead->next == phead;
	// If the judgment is true , return ture, It means that only the sentinel position head is left in the linked list ;
	// If the sentence is false , return false, Indicates that there are still valid nodes in the linked list 
}


// Delete the end of the linked list 
// reflection ： This two-way lead cycle linked list , It reflects the benefits of tail deletion , There is no need to traverse when finding the tail . A tailprev, And the above head second equally , It can facilitate the modification of the subsequent node relationship .
// This method is still applicable when there is only one valid node , When the linked list is empty ( Only the head node of the sentry position ), Need extra treatment .
void ListPopBack(LTNode* phead)
{
    
	assert(phead);
	assert(!ListEmpty(phead));// Other writing methods ：assert(phead->next!=phead);

	// With the help of Ereas How to write a function ：( These two assertions still need )
	ListErase(phead->prev);


	// Don't use Erase How to write a function ：
	// Deletion at the end , Find the tail node , Find the new tail node after tail deletion 
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	// Change relationships 
	phead->prev = tail->prev;
	tailprev->next = phead;
	// Release the node to be deleted 
	free(tail);
}

  
  

Tail deletion test results

  
  

Head deletion

// Auxiliary delete function 
bool ListEmpty(LTNode* phead)
{
    
	assert(phead);
	return phead->next == phead;
	// If the judgment is true , return ture, It means that only the sentinel position head is left in the linked list ;
	// If the sentence is false , return false, Indicates that there are still valid nodes in the linked list 
}

// Delete the linked list header 
// reflection ： As with header insertion, it is necessary to find out the effective header nodes and the pointing relationship between the remaining nodes after deletion 
void ListPopFront(LTNode* phead)
{
    
	assert(phead);
	assert(!ListEmpty(phead));

	// With the help of Ereas How to write a function ：( These two assertions still need )
	ListErase(phead->next);

	// Don't use Erase How to write a function ：
	// Head deletion , Valid header nodes , New valid header node 
	LTNode* second = phead->next;
	LTNode* secondnext = second->next;
	// Change the direction 
	phead->next = secondnext;
	secondnext->prev = phead;
	// Release nodes 
	free(second);
}

  
  

Header deletion test results

  
  

pos Insert... Before position

//pos Insert... Before position 
// reflection ： Take the lead in two-way linked list , stay pos Insert... Before position ,prev The existence of the pointer , No need to traverse to find pos Location 
void ListInsert(LTNode* pos, LTDataType x)
{
    
	assert(pos);
	// Determine the pointer 
	LTNode* posprev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	// Modify the relationship 
	// Yes newnode：
	newnode->next = pos;
	newnode->prev = posprev;
	// Yes pos：
	pos->prev = newnode;
	// Yes posprev：
	posprev->next = newnode;
}

  
  

pos Delete... At location

//pos Delete... At location 
void ListErase(LTNode* pos)
{
    
	assert(pos);
	// Determine the desired pointer ：
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	// Modify the relationship ：
	posprev->next = posnext;
	posnext->prev = posprev;
	// Delete node ：
	free(pos);
}

  
  

pos Test results at any position