リストを実装してみる

C言語を使ってリスト(Linked List)構造を作ってみる。 リストとは簡単に言うと同じタイプのデータがつながった状態をいう

配列との違いとしてリストは列の長さは可変でデータの挿入や削除は早いという点がある。ランダムアクセスに関しては探索が必要となり遅いというデメリットもある。

実装したサンプルが下記

/* リスト　サンプルコードまとめ */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* リストのセルに関するコード */
#define BUFSIZE 32

struct List {
  char data[BUFSIZE];
  struct List* next;
};

/* add関数部分　サンプルコード */
struct List* add(struct List* lst, char* str)
{
  struct List* new;
  
  if (lst == NULL) {
    new = (struct List*)malloc(sizeof(struct List));
    if (new == NULL) { /* エラー処理 */
      printf("mallocに失敗しました。\n");
      return NULL;
    }
    new->next = NULL;
    strncpy(new->data, str, BUFSIZE);
    return new;
  } else {
    lst->next = add(lst->next, str);
    return lst;
  }
}

/* del関数部分　サンプルコード */
struct List* del(struct List* lst, char* str)
{
  struct List* tmp;
  
  if (lst == NULL) { /* エラー処理 */
    printf("%sが見つかりませんでした。\n", str);
    return NULL;
  }
  
  if (strncmp(lst->data, str, BUFSIZE) == 0) { /* 要素が見つかった */
    tmp = lst->next; /* ポインタの退避 */
    free(lst); /* 解放 */
    printf("%sを削除しました。\n", str);
    return tmp;
  } else {
    lst->next = del(lst->next, str);
    return lst;
  }
}

/* show関数部分　サンプルコード */
void show(struct List* lst)
{
  if (lst == NULL) return;
  printf(lst->data);
  show(lst->next);
}

/* finalize関数部分　サンプルコード */
void finalize (struct List* lst)
{
  struct List* tmp;
  
  if (lst != NULL) {
    tmp = lst->next;
    free(lst);
    finalize(tmp);
  }
}

/* メイン関数 */
int main()
{
  /* 変数の宣言 */
  int cmd = 1;
  struct List* head = NULL;
  char str[32];
  
  while (cmd != 0) {
    printf("コマンドを入力してください\n");
    printf("表示:1 挿入:2 削除:3 終了:0 -> ");
    scanf("%d", &cmd);
    scanf("%*c");
    
    switch (cmd) {
    case 1:
      /* リストを先頭から表示する */
      show(head);
      break;
    case 2:
      /* リストに要素を挿入する */
      printf("挿入する文字列を入力してください :");
      fgets(str, BUFSIZE, stdin);
      head = add(head, str);
      printf("%sが追加されました。\n", str);
      break;
    case 3:
      /* リストの要素を削除する */
      printf("削除する文字列を入力してください :");
      fgets(str, BUFSIZE, stdin);
      head = del(head, str);
      break;
    case 0:
      /* 終了処理 */
      finalize(head);
      printf("終了します。\n");
    default:
      printf("未定義のコマンドです。\n");
    }
  }
  
  return 0;
}