pointerで連結リストに対して追加・削除

連結リストに対する追加・削除

C言語の勉強で連結リストの追加・削除のコードのメモとなります。

追加

連結リストの最後の要素に要素を追加するコードは下記となります。

append.c

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

struct node{
  int data;
  struct node *link;
};

//function declaration
void display(struct node *);
void append(struct node **, int);

void main(){
  //set pointer to null
  struct node *p = NULL;

  append(&p,4);
  append(&p,10);
  append(&p,30);

  display(p);
}

void append(struct node **q, int num){
  struct node *r, *temp;
  temp = *q;

  //if the node is not created
  if(*q == NULL){
    //create node
    r = malloc(sizeof(struct node));
    r->data = num;
    r->link = NULL;
    //change pointer to point to new node;
    *q = r;
  }else{
    //create node
    r = malloc(sizeof(struct node));
    r->data = num;
    r->link = NULL;
    //move to the last node
    while(temp->link!=NULL){
      temp = temp->link;
    }
    //change link of last node to point to created node
    temp->link = r;
  }
}

void display(struct node *q){
  while(q!=NULL){
    printf("%d\n",q->data);
    q = q->link;
  }
}

削除

連結リストの要素を削除するコードは下記となります。

delete.c

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

struct node{
  int data;
  struct node *link;
};

//function declaration
void append(struct node **, int);
void delete(struct node **, int);
void display(struct node *);

void main(){
  struct node *p;
  p=NULL;

  append(&p,10);
  append(&p,15);
  append(&p,20);
  append(&p,30);

  printf("Before deletion: \n");
  display(p);

  delete(&p,20);
  delete(&p,30);
  delete(&p,10);

  printf("After deletion:\n");
  display(p);
}

void delete(struct node **q, int num){
  struct node *temp,*r;
  temp = r = *q;

  //find node that has the value to be deleted
  while(temp!=NULL){
    //if found jump out of loop
    if(temp->data == num){
      break;
    }
    //preserve current node info before going to the next node
    r = temp;
    //if not found go to next node
    temp = temp->link;
  }

  //if the delete target is the first node
  if(temp == *q){
    //point p to the next node
    *q = temp->link;
    //delete node
    free(temp);
  }else{
    //change previous node link to point to the next node after target
    r->link = temp->link;
    //delete node
    free(temp);
  }
}

void append(struct node **q, int num){
  struct node *r,*temp;
  temp = *q;

  //p is pointing to null
  if(*q == NULL){
    //create new node
    r = malloc(sizeof(struct node));
    r->data = num;
    r->link = NULL;
    //change p to point to new node
    *q = r;
  }else{
    //move to last node
    while(temp->link!=NULL){
      temp=temp->link;
    }
    //create new node
    r = malloc(sizeof(struct node));
    r->data = num;
    r->link = NULL;
    //change last node link to point to new node
    temp->link = r;
  }
}

void display(struct node *q){
  while(q!=NULL){
    printf("%d\n",q->data);
    q=q->link;
  }
}