🦔

C言語でリンクリスト構造を実装する

2024/04/27に公開

リンクリスト(連結リスト)は、データを連結して管理するデータ構造で、ノードがポインタでつながっています。ノードの追加、削除、検索などの操作を行うことができます。
以下に、片方向リスト(singly linked list)の例を示します。

片方向リストの実装

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

// リストのノードを表す構造体
struct list_node {
  int content;
  struct list_node *next;
};

// リストの最後の要素を返す関数
struct list_node *list_node_last(struct list_node *list_node) {
  struct list_node *last;

  if (!list_node)
    return NULL;
  last = list_node;
  while (last->next)
    last = last->next;
  return last;
}

// リストに要素を追加する関数
void  list_node_add(struct list_node **list_node, struct list_node *new) {
  struct list_node *last;

  if (!(*list_node)) {
    *list_node= new;
    return ;
  }
  last = list_node_last(*list_node);
  last->next = new;
}

// リストの要素を表示する関数
void print_list_node(struct list_node *head) {
  struct list_node *current = head;

  while (current != NULL) {
    printf("%d -> ", current->content);
    current = current->next;
  }
  printf("NULL\n");
}

// リストのノードを作成する関数
struct list_node *create_list_node(int content) {
  struct list_node *new_list_node = (struct list_node*)malloc(sizeof(struct list_node));

  new_list_node->content= content;
  new_list_node->next = NULL;
  return new_list_node;
}

// メイン関数
int main() {
  struct list_node *head = NULL;

  // ノードを追加
  list_node_add(&head, create_list_node(10));
  list_node_add(&head, create_list_node(20));
  list_node_add(&head, create_list_node(30));

  // リストの要素を表示
  printf("Linked list_node: ");
  print_list_node(head);

  // メモリを解放
  while (head != NULL) {
    struct list_node *tmp = head;
    head = head->next;
    free(tmp);
  }
  return 0;
}

リンクリストの構造体

struct list_node は、リンクリストのノードを表す構造体です。それぞれのノードは整数値 content と次のノードへのポインタ next を持っています。

list_node_last 関数

list_node_last 関数は、リストの最後の要素を返す関数です。
引数としてリストの先頭ノードを受け取り、最後のノードを探索して返します。

list_node_add 関数

list_node_add 関数は、新しいノードをリストに追加する関数です。
リストが空の場合は、新しいノードをリストの先頭に追加します。そうでない場合は、最後のノードの次に新しいノードを追加します。

print_list_node 関数は、リストの要素を表示する関数です。
リストの先頭から順に要素を表示し、最後に “NULL” を出力します。

create_list_node 関数

create_list_node 関数は、新しいノードを作成する関数です。
引数として整数値を受け取り、その値を持つ新しいノードを作成して返します。

メイン関数

メイン関数では、リストを作成し、要素を追加して表示しています。
最後にメモリを解放しています。

詳細な説明や他のリンクリストの実装方法については、以下のブログ記事を参照してください。

【C言語】連結リストとは【片方向リスト,双方向リスト,双方向循環リスト】
C言語 データ構造 構造体を使ったリスト構造(Linked Lists)
C言語 リスト構造について分かりやすく解説【図解】

Discussion