The establishment and basic operation of bidirectional linked list of C language data structure

The establishment and basic operation of bidirectional linked list of C language data structure

Bidirectional linked lists have more flexibility than single linked lists, and most of their operations are the same as linear lists. The following is a summary of the differences between bidirectional and single linked lists and the problems I encountered in the implementation process.

1. Establishment of two-way linked list

When a bidirectional list is initialized, the first and last two nodes are allocated memory space. After successful allocation, point the prior pointer of the first node and next pointer of the tail node to NULL, which is a critical step of 10, as this is the condition used later to determine the empty table. At the same time, when the list is empty, the next of the first node should point to the tail node, and the prior of the tail node should point to the first node.

2. The insertion of two-way linked list

Since there is one more prior pointer in the pointer field when defining a bidirectional linked list, the insertion operation becomes complicated, but the basic operation is not difficult to understand. Just remember that when dealing with the relationship between the precursor and successor Pointers and the inserted node, you should always grasp the "order principle", that is, if the inserted node and two existing nodes form a triangle, you should first deal with the "up" pointer, and then deal with the "down" pointer. The following code describes the process:

pinsert->prior=p;
pinsert->next=p->next;
p->next->prior=pinsert;
p->next=pinsert;  

3. Delete the two-way linked list

Once you understand the insertion of a bidirectional list, the deletion is 10 points easier to understand. The following code describes the process:

 p->prior->next=p->next;
  p->next->prior=p->prior;
  free(p);

Other operations of a bidirectional linked list are similar to those of a single linked list, so I won't go into details here. The complete code is as follows:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int elemtype;
typedef struct node{
  elemtype data;
  struct node * next;
  struct node * prior;
}node;
typedef struct node* dlinklist;

status visit(elemtype c){
  printf("%d ",c);
}

/* Bidirectional list initialization */
status initdlinklist(dlinklist * head,dlinklist * tail){
  (*head)=(dlinklist)malloc(sizeof(node));
  (*tail)=(dlinklist)malloc(sizeof(node));
  if(!(*head)||!(*tail))
    return ERROR;
  /* this 1 Step is crucial */ 
  (*head)->prior=NULL;
  (*tail)->next=NULL;
  /* When the list is empty, point the head to the tail */
  (*head)->next=(*tail);
  (*tail)->prior=(*head);
}

/* Determines whether it is empty */
status emptylinklist(dlinklist head,dlinklist tail){
  if(head->next==tail)
    return TRUE;
  else
    return FALSE;
} 

/* The tail method creates a linked list */ 
status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=tail,pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  if(!pinsert)
     return ERROR;
  pinsert->data=data;
  pinsert->next=NULL;
  pinsert->prior=NULL;
  tail->prior->next=pinsert;
  pinsert->prior=tail->prior;
  pinsert->next=tail;
  tail->prior=pinsert;
} 

/* Header insertion creates a linked list */ 
status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=head,qmove=tail,pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  if(!pinsert)
    return ERROR;
  else{
    pinsert->data=data;
    pinsert->prior=pmove;
    pinsert->next=pmove->next;
    pmove->next->prior=pinsert;
    pmove->next=pinsert;
  }
}

/* Print a linked list in positive order */ 
status traverselist(dlinklist head,dlinklist tail){
  /*dlinklist pmove=head->next;
  while(pmove!=tail){
    printf("%d ",pmove->data);
    pmove=pmove->next;
  }
  printf("\n");
  return OK;*/
  dlinklist pmove=head->next;
  while(pmove!=tail){
    visit(pmove->data);
    pmove=pmove->next;
  }
  printf("\n");
}

/* Returns the first 1 A value of data The order of the elements of */
status locateelem(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=head->next;
  int pos=1;
  while(pmove&&pmove->data!=data){
    pmove=pmove->next;
    pos++;
  }
  return pos;
}

/* Return table long */
status listlength(dlinklist head,dlinklist tail){
  dlinklist pmove=head->next;
  int length=0;
  while(pmove!=tail){
    pmove=pmove->next;
    length++;
  }
  return length;
}

/* Print the list in reverse order */
status inverse(dlinklist head,dlinklist tail){
  dlinklist pmove=tail->prior;
  while(pmove!=head){
    visit(pmove->data);
    pmove=pmove->prior;
  }
  printf("\n");
}

/* Delete the first in the list pos The position of the element and the data return */
status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){
  int i=1;
  dlinklist pmove=head->next;
  while(pmove&&i<pos){
    pmove=pmove->next;
    i++;
  }
  if(!pmove||i>pos){
    printf(" Illegal data entry \n");
    return ERROR;
  }
  else{
    *data=pmove->data;
    pmove->next->prior=pmove->prior;
    pmove->prior->next=pmove->next;
    free(pmove);
  }
}

/* Insert an element at the end of the list */
status inserttail(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  pinsert->data=data;
  pinsert->next=NULL;
  pinsert->prior=NULL;
  tail->prior->next=pinsert;
  pinsert->prior=tail->prior;
  pinsert->next=tail;
  tail->prior=pinsert;
  return OK;
} 
int main(void){
  dlinklist head,tail;
  int i=0;
  elemtype data=0;
  initdlinklist(&head,&tail);
  if(emptylinklist(head,tail))
    printf(" The list is empty \n");
  else
    printf(" The list is not empty \n");
  printf(" Header insertion creates a linked list \n"); 
  for(i=0;i<10;i++){
    createdlinklisthead(head,tail,i);
  }
  traverselist(head,tail);

  for(i=0;i<10;i++){
    printf(" Value is in the table %d The position of the element is ",i); 
    printf("%d position \n",locateelem(head,tail,i));
  }
  printf(" Table for long %d\n",listlength(head,tail));
  printf(" Print the list in reverse order ");
  inverse(head,tail);
  for(i=0;i<10;i++){
    deleteelem(head,tail,1,&data);
    printf(" The deleted element is %d\n",data);
  }
  traverselist(head,tail);
  if(emptylinklist(head,tail))
    printf(" The list is empty \n");
  else
    printf(" The list is not empty \n");
    printf(" The tail method creates a linked list \n");
  for(i=0;i<10;i++){
    //inserttail(head,tail,i);
    createdlinklisttail(head,tail,i);
  }
  traverselist(head,tail);
  printf(" Print the list in reverse order ");
  inverse(head,tail);
}

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