(c言語)ポインタを用いたリスト

C言語 プログラミング

ココでは主に挿入と削除について話します。(最後に作成したものをチェックするprintも紹介します。)

  • 単方向リスト
  • 双方向リスト

単方向リスト

単方向リストとは

単方向リストは下の図のようなもので、1つのリストが次の行先のみを知っているようなものです。

上の図を以下の図のように変換することで挿入(insert)及び削除(delete)を作る際にイメージしやすくなります。

実際に書いてみましょう

挿入(insert)及び削除(delete)以外の部分は以下のようになります。

struct node{
  struct node *next; //nextのアドレスを入れる部分
  int elem; //値を入れる部分
};
struct node* head(void){
  struct node* n;//箱の生成
  n=(struct node*)malloc(sizeof(struct node));//箱の拡張
  n->next = NULL;//箱の行き先をnullにする
  return n;
}
void main(){
struct node* list;
list=head;
}

ここからがinsert及びdeleteです

void insert(struct node* p, char elem) {
  struct node* n;  //新しく値を代入する箱を作る
  n = (struct node*)malloc(sizeof(struct node));  //箱の大きさを拡張する
  n->elem = elem;                                 //値を代入
  n->next = p->next;  // nの行先をpの行き先にする
  p->next = n;        //作った箱の行先をpにする=次にpが来る
}

void delete(struct node* p){
  if(p->next != NULL){
    p->next=p->next->next;    //pの行き先を次の次にする=一つ飛ばす
  }
}

注意点

insertでは受け取った引数のpの次に値を挿入し、deleteでは受け取った引数pの次の値を削除する形となります。

作成時のポイント

  • 追加する箱を考えて、追加する箱のnext部分を先に指定する。
  • その後で追加した箱の一つ後ろ(引数で渡したもの)のnextを変える。

双方向リスト

双方向リストとは

双方向リストは下の図のようなもので、1つのリストが次の行先を知っていて、また、１つのリストが前の行き先も知っているようなものです。

上の図を以下の図のように変換することで挿入(insert)及び削除(delete)を作る際にイメージしやすくなります。

実際に書いてみましょう

挿入(insert)及び削除(delete)以外の部分は以下のようになります。

struct node{
  struct node *next;  //nextのアドレスを入れる場所
  struct node *prev;  //prevのアドレスを入れる場所
  int elem; //値を入れる場所
};
struct node* head(void){
  struct node *n;//箱の生成
  n=(struct node*)malloc(sizeof(struct node));//箱の拡張
  n->next = NULL;//箱の行き先を指定
  n->prev = NULL;//箱の戻り値を指定(使うことはない)
  return n;
}
void main(){
struct node* list;
list=head;
}

ここからがinsert及びdeleteです

void insert(struct node* p, int elem) {
  struct node* n;  //新しく値を代入する箱を作る
  n = (struct node*)malloc(sizeof(struct node));  //箱の大きさを拡張する
  n->elem = elem;                                 //値を代入

  if (p->next == NULL) {  //一個目の代入のみ
    n->next = p->next;    // nの行き先をpの行き先の次の物にする
    n->prev = p;          // nの戻り先をpにする
    p->next = n;          // pの行き先をnにする
  } else {
    n->next = p->next;  // nの行き先をpの行き先の次の物にする
    n->prev = p;        // nの戻り先をpの戻り先pにする
    p->next->prev = n;  // pの行き先の一つ前をnにする
    p->next = n;        // pの行き先をnにする
  }
}

void delete(struct node* p){
  if(p != NULL){
    p->prev->next=p->next;//pの一つ前(prev)を一つ後(next)を繋げる
    p->next->prev=p->prev;//pの一つ後(next)と一つ前(prev)を繋げる
  }
}

注意点

insertでは受け取った引数のpの次に値を挿入し、deleteでは受け取った引数pを削除する形となります。

作成時のポイント

  • 新しく挿入する値のprevとnextの行き先を先に決める
  • headのみの場合とhead以外がある場合で注意をする
  • 図に書きながら、prevとnextの行き先を線で結び、コードを書いたら消すようにする。

おまけ(作ったリストの全表示)

リストの中身のみ表示(単方向、双方向対応)

void printlist(struct node* p) {  //listを渡す
  p = p->next;    //listの先に行く
  for (; p != NULL; p = p->next) {
    printf("%c ", p->elem); //表示
  }
  printf("\n");
}

リストの詳細を表示(単方向リスト用)

void detailprintf_1(struct node* p) { //listを渡す
  int i = 0;
  p = p->next;    //listの一つ先へ進む
  for (; p != NULL; p = p->next) {
    printf("[%d]elem:%c\n", i, p->elem);  //値の表示
    if (p->next != NULL) {
      printf("[%d]nextelem:%c\n", i, p->next->elem);  //nextの表示
    } else {
      printf("[%d]nextelem:NULL(end)\n", i);  //nextがNULLだったNULL(end)と表示
    }
    i++;      //先頭からの番号を数える
  }
}

リストの詳細を表示(双方向リスト用)

void detailprintf_2(struct node* p) {   //listを渡す
  int i = 0;
  p = p->next;        //listの一つ先に進む
  for (; p != NULL; p = p->next) {
    printf("[%d]elem:%c\n", i, p->elem);  //値の表示
    if (p->next != NULL) {
      printf("[%d]nextelem:%c\n", i, p->next->elem);  //nextの表示
    } else {
      printf("[%d]nextelem:NULL(end)\n", i);  //nextがNULLだったNULL(end)と表示
    }
    if (i != 0) {
      printf("[%d]prevelem:%c\n", i, p->prev->elem);  //prevの表示
    } else {
      printf("[%d]prevelem:HEAD\n", i);   //prevがheadだったらHEADと表示
    }
    i++;      //先頭からの番号を数える
  }
}

結果(双方向リスト)

int main(void) {
  struct node* list;

  list = head();

  insert(list, 'a');
  insert(list, 'b');
  insert(list->next, 'c');
  insert(list, 'd');
  insert(list, 'e');
  delete (list->next);
  printlist(list);
  detailprintf(list);

  return 0;
}

d b c a
[0]elem:d             //先頭(0番目)の値
[0]nextelem:b         //次の値(1番目)
[0]prevelem:HEAD      //前の値(-1番目)
[1]elem:b             //1番目の値
[1]nextelem:c         //次の値(2番目)
[1]prevelem:d         //前の値(0番目)
[2]elem:c             //2番目の値
[2]nextelem:a         //次の値(3番目)
[2]prevelem:b         //前の値(1番目)
[3]elem:a             //3番目の値
[3]nextelem:NULL(end) //次の値(4番目)
[3]prevelem:c         //前の値(2番目)

　まとめ

今回、ポインタを用いたリストの単方向リスト、双方向リストについて書きました。

図を書きながらやるとイメージしやすいです。