😊

C言語 データ構造 構造体を使ったリスト構造(Linked Lists)

2023/03/06に公開

学んだことのまとめのつもりなので間違えてるとこがありましたら、教えていただけると助かります!

構造体(Struct)を使ったリスト構造(Linked Lists)

リスト構造とは?

  • Structを使った配列のようなもの
  • ポインターで node どうしがつながっている
  • 配列よりも簡単にデータを追加したり削除したりすることができる
  • 配列だったら index を1つずつずらさないといけなかったりするが、リスト構造だと簡単にできる
insertionのイメージ

deletionのイメージ

簡単なコードの説明

  • void* create_newnode() で新しく追加したいデータのノードを作成
  • void insertion() データをリストに追加
  • void deletion() データをリストから取り出す
free()で確保していたメモリを解放(解放しないと、バグの原因になるかも)
  • print_LinkedLists() でリストの中のデータを確認

実行結果

head --> 4 --> NULL
head --> 2 --> 4 --> NULL
head --> 2 --> 4 --> 8 --> NULL
head --> 2 --> 4 --> 6 --> 8 --> NULL
head --> 4 --> 6 --> 8 --> NULL
head --> 4 --> 8 --> NULL

コード

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

typedef struct Node{
  int data;
  struct Node *next;
}node;

static node *head=NULL;

void* create_newnode(int num){
  node *newnode=malloc(sizeof(node));
  newnode->data=num;
  newnode->next=NULL;
  return newnode;
}

void insertion(int num){
  node *newnode=create_newnode(num);
  // if(head==NULL){
  //   head=newnode;
  // }else{
    node *current=head;
    node *previous=NULL;
    while(current!=NULL && current->data < newnode->data){
      //currentが削除したいnum、もしくはcurrentがNULLになった終了する
      previous=current;
      current=current->next;
    }
    if(previous==NULL){
      //previousがNULLっていうことはnewnode->dataが(head->data)よりも小さかったということ、もしくはheadがNULLだったということ
      newnode->next=head;
      head=newnode;
    }else{//
      previous->next=newnode;
      newnode->next=current;
      //listの一番最後だったとしても上のwhile()でcurrentはNULLの状態で終了しているので問題ないし、途中へのinsertだったとしても問題ない
    }
  //}
}

void deletion(int num){
  
  if(head->data==num){
    node *temp=head;
    head=head->next;
    free(temp);
    return;
  }else{
    node *current=head;
    node *previous=NULL;
    while(current!=NULL && current->data!=num){
      //currentが削除したいnum、もしくはcurrentがNULLになった終了する
      previous=current;
      current=current->next;
    }
    if(current==NULL){
      //currentがNULLになるまでwhile()が回ったということは削除したいnumが存在しなかったということ
      printf("!-- no exist %d in list --!\n",num);
    }else{
      //currentがNULLじゃないということは、削除したいnumを見つけたということ
      node *temp=current;
      previous->next=current->next;//currentがlistの一番最後だったとしても、current->nextはNULLなので問題ない
      free(temp);
    }
  }
}

void print_LinkedLists(){
  node *ptr=head;
  printf("head --> ");
  while(ptr!=NULL){
    printf("%d --> ",ptr->data);
    ptr=ptr->next;
  }
  printf("NULL\n");
}
int main(void) {
  insertion(4);
  print_LinkedLists();
  
  insertion(2);
  print_LinkedLists();
  
  insertion(8);
  print_LinkedLists();
  
  insertion(6);
  print_LinkedLists();
  
  deletion(2);
  print_LinkedLists();
  
  deletion(6);
  print_LinkedLists();
}

Discussion