Basic operation of bidirectional linked list

This paper mainly summarizes the basic operation of bidirectional linked list , Including the creation of two-way linked list , Insert , Delete... By location , Delete by data field , Traverse , Reverse order and other operations , See code and notes for details .

#include <stdio.h>
#include <stdlib.h> 

typedef struct Node {
	int data;
	struct Node * prior;
	struct Node * next;
}NODE, *PNODE;

// Insert the node at the specified location 
/*
 Be careful :
 The insertion is not in the end. Change the precursor pointer of the next node inserted as a node  
*/ 
bool insertNode(PNODE L, int i, int x) {
	PNODE p = L;
	while(p && --i) // Give Way p Point to i-1 Nodes  
		p = p->next;
	if(!p) return false;	// The linked list is not long enough , Insert the failure  
	PNODE s = (NODE*)malloc(sizeof(NODE));
	s->data = x;
	s->next = p->next;
	if(p->next) // Be sure to remember to determine whether the insertion is not the last before modifying the predecessor pointer of the subsequent node  
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

// Delete the element with the specified value 
/*
 Be careful ：
1. The deletion position is uncertain , Traversal with double pointers  
2. Judge whether the length of the linked list is enough , Just judge p Node to ( Nodes to be deleted ) Is it empty ;
3. Remember to judge whether the next node after deleting a node exists , If exist , Change its precursor . 
*/
bool deletNode1(PNODE L, int x) {
	PNODE p = L->next, q = L;
	while(p && p->data != x) {
		q = p;
		p = p->next;
	}
	if(!p) return false; // The linked list is not long enough , Delete failed  
	q->next = p->next;	// Delete the value from the bidirectional linked list as x The node of  
	if(q->next)	// It can also be p->next 
		q->next->prior = q;
	free(p);
	return true;
}

// Delete the element at the specified position and save the value of the deleted element  
/*
 Be careful ：
1. Judge whether the length of the linked list is enough , Include ：p Whether the pointer is empty ( Delete the previous node of the node )  and  p Point to the next node ( Nodes to be deleted ) Is it empty ;
2. Remember to reserve the address of the deletion node, that is p->next; 
2. Remember to judge whether the next node after deleting a node exists , If exist , Change its precursor . 
*/ 
bool deletNode2(PNODE L, int i, int &e) {
	PNODE p = L, q;
	while(p && --i) // Give Way p Point to i-1 Nodes  
		p = p->next;
	if(!p || !p->next) return false; // The linked list is not long enough , Delete failed  
	q = p->next;
	e = q->data;
	p->next = q->next; // Delete the... From the two-way linked list i Nodes  
	if(p->next) // Notice the p->next And the one reserved in front q The meaning has changed , Write q->next It's OK  
		p->next->prior = p;
	free(q); 
	return true;
}

// Create linked list by head insertion 
/*
 Be careful ：
1.s node ( New insert node ) The right pointer field of begins to fill the right pointer field of the header node ; 
2. Be sure to judge whether the next node after the newly inserted node exists , If exist , Change its precursor  . 
*/ 
void creatList(PNODE &L, int *a, int n) {
	L = (NODE*)malloc(sizeof(NODE));
	L->next = L->prior = NULL;
	for(int i=0;i<n;i++) {
		PNODE s = (NODE*)malloc(sizeof(NODE));
		s->data = a[i];
		s->next = L->next;
		if(s->next) // When the special judgment is not an empty table, the processing method of the precursor pointer of the element after the insertion position , Write here L->next It's OK  
			s->next->prior = s;
		s->prior = L;
		L->next = s;
	}
} 

// Tail interpolation method to create linked list 
// The operation is basically the same as that of a one-way linked list , Remember to add the precursor pointer  
void creatList2(PNODE &L, int *a, int n) {
	L = (NODE*)malloc(sizeof(NODE));
	L->next = L->prior = NULL;
	PNODE p = L;	 
	for(int i=0;i<n;i++) {
		PNODE s = (NODE*)malloc(sizeof(NODE));
		s->data = a[i]; 
		s->next = p->next;
		s->prior = p;
		p->next = s;
		p = p->next;
	}
}

// Output list  
void displayNode1(PNODE L) {
	if(L == NULL || L->next == NULL)
		return;
	PNODE p = L->next;
	while(p) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

// Use the precursor pointer to output the linked list in reverse order  
void displayNode2(PNODE L) {
	if(L == NULL || L->next == NULL)
		return;
	PNODE p = L->next;
	while(p->next) 
		p = p->next;
	printf("%d ",p->data);
	p = p->prior;
	while(p != L ) {
		printf("%d ",p->data);
		p = p->prior;
	} 
	printf("\n");	
}

// The reverse order of the two-way linked list  
void reverse(PNODE L) {
	PNODE p = L->next, q = NULL, r; // Note that there q How to handle pointers  
	while(p) {
		r = p->next; // reserve p Pointer field to node 
		p->prior = p->next;
		p->next = q; // change p The pointer field pointing to the node points to the previous node 
		q = p; //p,q Pointer backward  
		p = r;
	}
	L->next = q;// Head node homing  
    q->prior = L; // Don't forget that the precursor pointer of the last node points to the head node  
} 

int main() {
	int n = 5, m = 7;
	int a[n] = {9,3,0,6,1};
	int b[m] = {5,1,3,6,8,7,4};
	PNODE L;
	creatList2(L,a,n);
	displayNode1(L);
	int e;
	if(deletNode2(L,5,e)) {
		printf(" The deleted element is :%d\n",e);
	} else {
		printf(" The element does not exist \n");
	}
	displayNode1(L);
	return 0;
}

The most important thing about the bidirectional linked list is the processing of the precursor pointer , Because there is a precursor pointer   So insert , Delete and so on , Be sure to remember to judge whether subsequent nodes exist , If so, modify the predecessor pointer of the subsequent node .