Implementation of double linked list in C language

C Language implementation of double linked list

explain

The picture was drawn by myself , It's a little ugly , You don't mind? .
This article is from the column ： data structure
It will continue in the future coding. If necessary, you can pay attention to and like the wave .

Implemented function

• Insert node
• Delete node
• Go through all the elements from beginning to end
• Get the precursor of a node and its successor nodes

The main purpose of obtaining the precursor and successor is to test whether the double linked list is written correctly , Because the double linked list can access the precursor , This is different from the single linked list .

Structure definition

typedef struct BiLinkNode
{
    
	ElemType data;
	struct BiLinkNode *rlink,*llink;// Represents the left pointer and the right pointer respectively , Point to the forerunner and the successor respectively , Generally also writing prior and next
}BiLink;

initialization

// Initialize double linked list ( Leading node ) 
bool InitBiLinkList(BiLink *B)
{
    
	// First apply for a header node 
	BiLink *head = (BiLink *)malloc(sizeof(BiLink));
	// The left and right pointers are initially null , And the meter length is 0 
	head->llink = B;
	B->rlink = head;
	head->rlink = NULL;// After the header node, there is no element at first 
	return true;
} 

Insert node

​ As shown in the figure below ：

​ The green solid line is the structure before insertion , The dotted line is what we are going to do .S Represents the newly inserted node .

​ The sequence of operations here is ①②③④, Of course, you can also change the order , such as ③ and ④ The order of can be changed . The corresponding code implementation of these operations is ：

​ ①s->rlink = p->rlink;

​ ②p->rlink->llink = s;

​ ③p->rlink = s;

​ ④s->llink = p;

​ Here I use the head interpolation method to realize , Welcome to use the tail interpolation method to try .

// Insert 
bool InsertBiLinkList(BiLink *B,ElemType e)
{
    
	// The first interpolation 
	BiLink *p = B;//
	
	// Apply for a new node 
	BiLink *s = (BiLink *)malloc(sizeof(BiLink));
	
	s->data = e;// assignment  
	
	// Modify pointer   The node s Insert to node p after  
	s->rlink = p->rlink;//s Pointer to 
	p->rlink->llink = s;
	
	p->rlink = s;
	s->llink = p;
	
	length++;// Number of elements plus one 
	return true;
} 

Delete node

Pictured ：

Deleting is much simpler than inserting , We just need to modify it q->llink The right pointer of and q->rlink The left pointer of , Point them at q->rlink and q-<llink that will do .

bool DeleteBinList(BiLink *B,ElemType *e)// Delete a node according to the value 
{
    
	BiLink *q;
	q = B->rlink;

	while(q->rlink!=NULL)// First traversal  
	{
    
		if(q->data == e)// First find this node 
		{
    
			q->llink->rlink = q->rlink;// modify q The following pointer in front of the node 
			q->rlink->llink = q->llink;// modify q The precursor pointer behind the node  
		} 
		q = q->rlink;
	}
	length--;
	return true;
} 

Output all elements

Just traverse from beginning to end or from end to end . Here I implement the traversal from beginning to end .

void PrintAll(BiLink *B)
{
    
	BiLink *q;
	q = B->rlink;

	// Print out all elements  
	while(q->rlink!=NULL)
	{
    
		printf("%d ",q->data);
		q = q->rlink;// As long as it's not at the end , The pointer ++
	}
}

All the code

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> // according to C99 standard ,C Language use bool Type needs to add this header file 

typedef int ElemType;

typedef struct BiLinkNode
{
    
	ElemType data;
	struct BiLinkNode *rlink,*llink;
}BiLink;

//------------  Function declaration  ----------//
void MainMenu();
bool GetLen(BiLink *B);// Get table length , And print directly on the screen  
bool InitBiLinkList(BiLink *B);// initialization  
bool InsertBiLinkList(BiLink *B,ElemType e);// Insert 
void PrintAll(BiLink *B);// Output all elements 
bool GetPriorNode(BiLink *B,ElemType e,ElemType *ldata);// The search element is e The value of the precursor node of  
bool GetNextNode(BiLink *B,ElemType e,ElemType *rdata);// The search element is e The value of the successor node of 
bool DeleteBinList(BiLink *B,ElemType *e);// Delete a node according to the value  
//------------  Function declaration  ----------//

int length; // Actual length in the table  

int main()
{
    
	BiLink B;
	
	int ch; 
	ElemType element,num,ldata,rdata;
	
	if(InitBiLinkList(&B))
		printf(" Successful initialization ！\n");
	else
		printf(" initialization failed ！\n");
	
	while(1)
	{
    
		MainMenu(); 
		printf(" Please enter the action you want to perform :");
		scanf("%d",&ch);
		
		switch(ch)
		{
    
			case 0:		printf(" Thank you for using , Exited ！");	exit(0);	break;
			case 1:		printf(" Please enter the element you want to insert :\n");
						scanf("%d",&element); 
						if(InsertBiLinkList(&B,element))
							printf(" Insert the success ！\n");
						else
							printf(" Insert the failure ！\n");
						break;
			case 2:		PrintAll(&B);
						break;		
			case 3:		if(GetLen(&B))
							printf(" To be successful !");
						else
							printf(" Acquisition failure !");
						break; 
						
			case 4:		
						printf(" Please enter the value of the current node you want to get ：\n");
						scanf("%d",&num);
						if(GetPriorNode(&B,num,&ldata))
							printf(" To be successful ,%d The value of the previous node of is :%d\n",num,ldata);
						else
							printf(" Acquisition failure ！");
						break;
			case 5: 
						printf(" Please enter the value of the current node you want to get ：\n");
						scanf("%d",&num);
						if(GetNextNode(&B,num,&rdata))
							printf(" To be successful ,%d The value of the last node of is :%d\n",num,rdata);
						else
							printf(" Acquisition failure ！");
						break;
			case 6: 
						printf(" Please enter the value of the node you want to delete ：\n");
						scanf("%d",&num);
						if(DeleteBinList(&B,num))
							printf(" Delete successful !\n");
						else
							printf(" Delete failed ！");
						break;
			default:	printf(" The operation instruction you entered is incorrect ！ Please re-enter ！");
		}
	}
	
	return 0;
}

// The main menu , Show  
void MainMenu()
{
    
	printf("\n\n\n");
	printf("\t *************  The realization of double linked list  ************\n\n"); 
	printf("\t ------- 0. sign out  \n\n");
	printf("\t ------- 1. Insert elements \n\n");
	printf("\t ------- 2. Output all elements \n\n");
	printf("\t ------- 3. Get table length \n\n");
	printf("\t ------- 4. Get the value of the precursor node of a node \n\n");
	printf("\t ------- 5. Get the value of the successor node of a node \n\n");
	printf("\t ------- 6. Delete a node \n\n");
	printf("\t *************************************\n");
}


// Initialize double linked list ( Leading node ) 
bool InitBiLinkList(BiLink *B)
{
    
	// First apply for a header node 
	BiLink *head = (BiLink *)malloc(sizeof(BiLink));
	// The left and right pointers are initially null , And the meter length is 0 
	head->llink = B;
	B->rlink = head;
	head->rlink = NULL;// After the header node, there is no element at first 
	return true;
} 

// Insert 
bool InsertBiLinkList(BiLink *B,ElemType e)
{
    
	// The first interpolation 
	BiLink *p = B;//
	
	// Apply for a new node 
	BiLink *s = (BiLink *)malloc(sizeof(BiLink));
	
	s->data = e;// assignment  
	
	// Modify pointer   The node s Insert to node p after  
	s->rlink = p->rlink;//s Pointer to 
	p->rlink->llink = s;
	
	p->rlink = s;
	s->llink = p;
	
	length++;// Number of elements plus one 
	return true;
} 


bool GetLen(BiLink *B)
{
    
	printf(" The watch is :%d\n",length);
	return true;
}

void PrintAll(BiLink *B)
{
    
	BiLink *q;
	q = B->rlink;

	// Print out all elements  
	while(q->rlink!=NULL)
	{
    
		printf("%d ",q->data);
		q = q->rlink;
	}
}

bool GetPriorNode(BiLink *B,ElemType e,ElemType *ldata)// The search element is e The value of the precursor node of 
{
    
	BiLink *q;
	q = B->rlink;
 
	while(q->rlink!=NULL)
	{
    
		if(q->data == e)// First find this node  
			*ldata = q->llink->data;
		q = q->rlink;
	}
	return true;
}

bool GetNextNode(BiLink *B,ElemType e,ElemType *rdata)// The search element is e The value of the successor node of 
{
    
	BiLink *q;
	q = B->rlink;
 
	while(q->rlink!=NULL)
	{
    
		if(q->data == e)// First find this node 
			*rdata = q->rlink->data;
		q = q->rlink;
	}
	return true;
}

bool DeleteBinList(BiLink *B,ElemType *e)// Delete a node according to the value 
{
    
	BiLink *q;
	q = B->rlink;

	while(q->rlink!=NULL)
	{
    
		if(q->data == e)// First find this node 
		{
    
			q->llink->rlink = q->rlink;// modify q The following pointer in front of the node 
			q->rlink->llink = q->llink;// modify q The precursor pointer behind the node  
		} 
		q = q->rlink;
	}
	length--; 
	return true;
} 

test