二重リンクリストに対するノードの追加・削除

二重リンクリストに対する操作

二重リンクリストに対して前方または後方からノードを追加したり、指定された数字を元でノードを削除したりするコードは下記となります。

doublylist.c

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

//node declaration
struct dnode{
  struct dnode *prev;
  int data;
  struct dnode *next;
};

//function declaration
void d_append(struct dnode **, int);
void d_display(struct dnode *);
int d_count(struct dnode *);
void d_addatbeg(struct dnode **, int);
void d_addafter(struct dnode *, int, int);
void d_delete(struct dnode **, int);
void r_display(struct dnode *);

void main(){
  //declare pointer to point to the front of doubly linked list
  struct dnode *p;
  
  //set pointer to point to empty doubly linked list
  p = NULL;
  
  //append node to doubly linked list
  d_append(&p,11);
  d_append(&p,21);
  
  //show nodes in doubly linked list
  d_display(p);
  printf("No. of elements in the DLL = %d\n",d_count(p));
  
  //add node at beginning of doubly linked list
  d_addatbeg(&p, 33);
  d_addatbeg(&p, 55);
  
  //show nodes in doubly linked list
  d_display(p);
  printf("No. of elements in the DLL = %d\n",d_count(p));
  
  //add node after the specified number of nodes
  d_addafter(p,1,4000);
  d_addafter(p,2,9000);
  
  //show nodes in doubly linked list
  d_display(p);
  printf("No. of elements in the DLL = %d\n",d_count(p));
  
  //delete node in doubly linked list
  d_delete(&p,51);
  d_delete(&p,21);
  
  //show nodes in doubly linked list
  d_display(p);
  printf("No. of elements in the DLL = %d\n",d_count(p));
}

//append node to doubly linked list
void d_append(struct dnode **q, int num){
  struct dnode *r, *temp;
    
  //create new node
  r = malloc(sizeof(struct dnode));
  //set value of new node
  r->data = num;
  //set next link of new node to null
  r->next = NULL;

  //if doubly linked list is empty
  if(*q == NULL){
    //set prev link of new node to null
    r->prev = NULL;
    //set p pointer to the new node
    *q = r;
  }else{ //if doubly linked list is not empty

    //set locator pointor to the front of doubly linked list
    temp = *q;
  
    //loop through doubly linked list to the last node
    while(temp->next!=NULL){
      temp = temp->next;
    }
    
    //set prev link of new node to last node of doubly linked list
    r->prev = temp;
    
    //set link of last node to point to new node
    temp->next = r;
  }
}

//add node to the beginning of doubly linked list
void d_addatbeg(struct dnode **q, int num){
  struct dnode *r;
  
  //create new node
  r = malloc(sizeof(struct dnode));
  //set data of new node
  r->data = num;
  //set previous link to NULL
  r->prev = NULL;
  //set next link to the front node
  r->next = *q;
  //if doubly linked list is not empty
  if(*q != NULL){
    //set prev link of current front node to new node
    (*q)->prev = r;
  }
  //set p pointer to point to the new node
  *q = r;
}

//add node after the specified number of nodes
void d_addafter(struct dnode *q, int loc, int num){
  int i;
  struct dnode *r, *temp;
  
  //set locator pointer to the front node of doubly linked list
  temp = q;
  
  //if provided location is not valid, print message and return to main
  if(loc > d_count(q) || loc <= 0){
    printf("Please give a number bigger than 0 or less than the size of linked list. If the list is empty, please add node before using this function.\n");
    return;
  }
  
  //move locator pointer to the insertion location.
  for(i=1;i<loc;i++){
    temp = temp->next;
  }
  
  //create new node
  r = malloc(sizeof(struct dnode));
  //set data of new node
  r->data = num;
  //set prev link of new node
  r->prev = temp;
  //set next link of new node
  r->next = temp->next;
  //if next node after new node is not null
  if(r->next != NULL){
    //set prev of node after new node to point to it
    (r->next)->prev = r;
  }
  //set next link of node pointed by locator to new node
  temp->next = r;
}

//delete node in doubly linked list
void d_delete(struct dnode **q, int num){
  struct dnode *temp;
  
  //set locator pointer to front of doubly linked list
  temp = *q;
  
  //loop through linked list to find target node
  while(temp!=NULL){
    if(temp->data == num){
      break;
    }
    //go to next node
    temp = temp->next;
  }
  
  //if target is not found, print message and return to main
  if(temp == NULL){
    printf("Target not found.\n");
    return;
  }
  
  //if first node is target for deletion
  if(temp == *q){
    //move p to point to the next node
    *q = temp->next;
    //if linked list is not empty after deletion
    if(*q != NULL){
      //set prev link of next node to null
      (*q)->prev = NULL;
    }
    //delete node
    free(temp);
  }else{
    //set node before target to point to the next node
    (temp->prev)->next = temp->next;
    //if node after target is not null
    if(temp->next != NULL){
      //set node after target to point to the node before target
      (temp->next)->prev = temp->prev;
    }
    //delete node
    free(temp);
  }
}

//display nodes in doubly linked list
void d_display(struct dnode *q){
  while(q!=NULL){
    printf("%d\n",q->data);
    q = q->next;
  }
}

//count number of nodes in doubly linked list
int d_count(struct dnode *q){
  int c = 0;
  
  //loop through doubly linked list
  while(q!=NULL){
    c++;
    q = q->next;
  }
  
  return c;
}

//display nodes in reverse order
void r_display(struct dnode *q){
  struct dnode *s;
  
  //if doubly linked list is empty
  if(q == NULL){
    return;
  }
  
  //loop through doubly linked list to the last node
  while(q->next != NULL){
    q = q->next;
  }
  
  //set locator pointer to point to the last node
  s = q;

  //loop through doubly linked list from last node to first node
  while(s!=NULL){
    printf("%d\n",s->data);
    s = s->prev;
  }
}