The C language implements data structures and two way linked list operations

The realization of bidirectional linked list of data structure

Each node in the bidirectional linked list contains two pointer fields, one of which holds the storage address of its successor node, and the other of which holds the storage address of its precursor node.

Type description of bidirectional linked list nodes:

// Type description of bidirectional linked lists  
typedef int ElemType; 
typedef struct node{ 
 ElemType data; 
 struct node *prior,*next; 
}DuLNode,*DuLinkList; 

Where, the prior domain stores the storage address of its precursor node, and the next domain stores the storage address of its successor node.

Two-way lists have two features:

1 is that you can search a node from both directions, which makes some operations (such as insert and delete) of the linked list easier. 2 is whether the use of the front chain or the chain can traverse the entire two-way linked list.

The operation of bidirectional linked list is basically the same as that of single linked list.

1. Create a bidirectional linked list of the leading node with the method of head insertion Create_DLinkListF(int n)

// Header insertion creates a bidirectional linked list of header nodes  
DuLinkList Create_DLinkListF(int n){ 
 DuLinkList L,p; 
 int i = n - 1; 
 ElemType x; 
 // New header  
 L = (DuLinkList)malloc(sizeof(DuLNode)); 
 L->prior = NULL; 
 L->next = NULL; 
 
 // Add the first 1 A node  
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 L->next = p; 
 p->prior = L; 
 p->next = NULL; 
 
 // Let's add other nodes  
 while(i > 0){ 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 
 p->next = L->next; 
 L->next->prior = p; 
 p->prior = L; 
 L->next = p; 
 
 i--; 
 } 
 return L; 
} 

2. The tail insertion method creates a two-way linked list of the leading node Create_DLinkListR(int n)

// The tail insertion method creates a bidirectional linked list of leading nodes  
DuLinkList Create_DLinkListR(int n){ 
 DuLinkList L,p,lastNode; 
 int i = n - 1; 
 ElemType x; 
 // New header  
 L = (DuLinkList)malloc(sizeof(DuLNode)); 
 L->prior = NULL; 
 L->next = NULL; 
 
 // Add the first 1 A node  
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 L->next = p; 
 p->prior = L; 
 p->next = NULL; 
 
 lastNode = p; 
 // Let's add other nodes  
 while(i > 0){ 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 
 lastNode->next = p; 
 p->prior = lastNode; 
 p->next = NULL; 
 
 lastNode = p; 
 i--; 
 
 } 
 return L; 
 
} 

3. Insert new node Insert_DLinkListBefore(DuLinkList p,ElemType x) before specified node

// Insert a new node before the specified node  
void Insert_DLinkListBefore(DuLinkList p,ElemType x){ 
 DuLinkList newNode; 
 // Judge node p Validity of previous nodes:  
 if(p->prior == NULL) 
 printf(" The node is not valid and cannot be inserted before the node \n"); 
 else{ 
 newNode = (DuLinkList)malloc(sizeof(DuLNode)); 
 newNode->data = x; 
 
 newNode->next = p; 
 p->prior->next = newNode; 
 newNode->prior = p->prior; 
 p->prior = newNode; 
 } 
} 

4. Insert new node Insert_DLinkListAfter(DuLinkList p,ElemType x) after specified node

// Inserts a new node after the specified node  
void Insert_DLinkListAfter(DuLinkList p,ElemType x){ 
 
 DuLinkList newNode; 
 newNode = (DuLinkList)malloc(sizeof(DuLNode)); 
 newNode->data = x; 
 
 // When the insertion position is last 1 After 1 node  
 if(p->next == NULL){ 
 p->next = newNode; 
 newNode->prior = p; 
 newNode->next = NULL; 
 } 
 else{ 
 newNode->next = p->next; 
 p->next->prior = newNode; 
 p->next = newNode; 
 newNode->prior = p; 
 } 
} 

5. Delete the specified node Delete_DLinkList(DuLinkList p)

// Delete specified node  
void Delete_DLinkList(DuLinkList p){ 
 // If you delete the last one 1 An element  
 if(p->next == NULL) 
 p->prior->next = NULL; 
 
 else{ 
 p->prior->next = p->next; 
 p->next->prior = p->prior; 
 
 } 
 free(p); 
} 

6. Back chain output bidirectional linked list Print_DLinkListN(DuLinkList L)

// Back chain output bidirectional linked list  
void Print_DLinkListN(DuLinkList p){ 
 
 while(p != NULL){ 
 printf("%d\t",p->data); 
 p = p->next; 
 } 
 printf("\n"); 
 
} 

7. Front chain output bidirectional linked list Print_DLinkListP(DuLinkList p)

// Front output bidirectional linked list  
void Print_DLinkListP(DuLinkList p){ 
 
 while(p != NULL){ 
 printf("%d\t",p->data); 
 p = p-prior; 
 } 
 printf("\n"); 
} 
 

Other operations of a bidirectional list, such as positioning, are similar to those of a single list, and are not to be repeated.

Thank you for reading, I hope to help you, thank you for your support of this site!