Double linked list: initialize insert delete traversal

Double linked list cannot be accessed randomly , Search by bit , Search by value can only be realized by traversal . Time complexity 0(n)

Initialization of double linked list

// Initialization of double linked list （ Leading node ）
typedef struct DNode{		// Define double linked list node type 
	ElemType data;	// Each node stores a data element 【data Called a data field 】
	struct DNode *prior,*next;// Precursor and successor pointers 
}LNode,*LinkList;
// Initialize double linked list 
bool InitDLinkList(DLinkList &L){
	L = (DNode *)malloc(sizeof(DNode));// Assign a head node 
	if (L==NULL)// Out of memory , Allocation failed 
		return false;
	L->prior = NULL;// The first node prior Never point to NULL
	L->next = NULL;// There is no node after the head node 
	return true;
}
void testDLinkLink(){
	// Initialize double linked list 
	DLinkLink L;
	InitDLinkList(L);
	// Subsequent code ...
}
// Judge whether the double linked list is empty 
bool Empty(DLinkList L){
	if (L->next == NULL)
		return true;
	else
		return false;
}

Insertion of double linked list

【 Insertion of double linked list 】	
// stay p Insert after the node s node 
bool InsertNextDNode(DNode *p,DNode *s){
	if (p==NULL || s==NULL)// Illegal parameters 
		return false;
	s->next = p->next;
	if (p->next != NULL)// If p A node has a successor node 
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return = s;
}

【 Deletion of double linked list 】

【 Deletion of double linked list 】
// Delete p The successor node of a node 
bool DeleteNextDNode(DNode *p){
	if (p==NULL)
		return false;
	DNode *q = p->next;// find p The successor node of q
	if (q==NULL)
		return false;//p No successor nodes 
	p->next = q->next;
	if (q->next != NULL)//q Node is not the last node 
		q->next->prior = p;
	free(q);// Release space 
	return true;
}
void DestoryList(DLinklist &L){
	// Circularly release each data node 
	while (L->next != NULL)
		DeleteNextDNode(L);
	free(L);// Release the head node   The header node can be released only when the table is destroyed 
	L =NULL;// The head pointer points to NULL
}

【 Traversal of double linked list 】

【 Traversal of double linked list 】
// Backward traversal 
while(p!=NULL){
	// To a node p Do the corresponding treatment   Such as ： Print 
	p = p->next;
}
// Forward traversal 
while(p!=NULL){
	// To a node p Do the corresponding treatment 
	p = p->prior;
}
// Forward traversal -- Skip over node 
while(p->prior!=NULL){
	// To a node p Do the corresponding treatment 
	p = p->prior;
}