C言語教室 第19回 - 単方向リスト

同じ型の変数をまとめて扱うことの出来る仕組みとして「配列」というものを使ってきましたが、今回は順序や要素の数を容易に変えられるリスト構造について説明します。

リスト構造にはいくつかの種類がありますが、最初に最もシンプルな単方向リストというものを説明します。各要素は値の他に次の要素を指すポインタを持っており、最後の要素であれば次の要素は無いので、ポインタ変数には NULL を入れて使います。

これをまとめて扱うために次のような構造体を定義して使います。

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

このリストを使う時には、最初の構造体へのポインタがあれば、そこから全ての要素を辿れるわけです。要素がひとつもない時には先頭へのポインタを NULL にします。

連結リスト

連結リスト - Wikipedia

さてリストを扱うには、リスト要素の追加または挿入、削除の機能が必要です。例えばリストの最初に要素を追加するには

void prepend(Node **head, int data) {
  Node new_node = (Node)malloc(sizeof(Node));
  new_node->data = data;
  new_node->next = *head;
  *head = new_node;
}

で要素を追加していけます。それぞれの要素を表示するには、先頭から順に next が NULL になるまで辿っていけば良いわけです。

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

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

void prepend(Node **head, int data) {
  Node *new_node = (Node*)malloc(sizeof(Node));
  new_node->data = data;
  new_node->next = *head;
  *head = new_node;
}

void print_list(Node *head) {
  while (head != NULL) {
    printf("%d ", head->data);
    head = head->next;
  }
}

void free_list(Node *head) {
  Node *current = head;
  while (current != NULL) {
    Node *next = current->next;
    free(current);
    current = next;
  }
}

void main() {
  Node *head = NULL;

  prepend(&head, 3);
  prepend(&head, 2);
  prepend(&head, 1);

  printf("List: ");
  print_list(head);

  free_list(head);
}

このコードを実行すると、最後に挿入した要素が最初になるので、以下の出力が得られます。

List: 1 2 3 

先頭ではなく末尾に追加するのであれば、next が NULL になる要素まで辿っていき、そこで要素を追加するコードを書きます。途中であれば、手前の next に新しい要素を入れ、新しい要素の next に、元の next をコピーすれば OK です。削除に関しても同じようにして要素を繋ぎ変えて行けば良いわけです。特定の要素の内容を探すのであれば、表示する関数を参考にして、先頭の要素から順に処理します。

このように単方向リストは、常に先頭から処理を行い、逆方向に辿ることは出来ないのですが、要素の挿入や削除、並び替えはポインタを操作するだけで済むので、配列と比べると非常に簡単に処理できます。特にリストに含まれる要素が整数といった単純な型ではなく、文字列や構造体であると値をコピーするのが大変になるので重宝します。

C++であるとか python などであればリストは最初から用意されているのですが、C言語では、このように自分で書いていかなければなりません。ポインタ操作が肝になるのですが、リストを平然と処理できるようになれば、もうC言語のポインタ操作も自信を持ってかまわないでしょう。

最後の要素に追加する頻度が高い場合などは、先頭へのポインタ以外に末尾へのポインタも常に更新して使うようなやり方も考えられます。自分で関数を書くからこそ、目的に合わせて効率的なコードを模索する自由もあります。

なお、リスト構造には次へのポインタだけではなく、前へのポインタも持つ双方向リストや、全体が輪のようになっている循環リストというものもあります。また応用としてポインタが複数ある木構造や網構造も作れます。

次回は双方向リストを説明します。

課題
・リストの要素の数を返す関数を書きなさい。
・リストの最後に要素を追加する関数を書きなさい。
・リストの先頭の要素を削除する関数を書きなさい。
・n番目の要素を返す関数を書きなさい。

演習
・リストを配列にコピーする関数を書きなさい。
・配列からリストを作る関数を書きなさい。

ヘッダ画像は、以下のものを使いました。
https://commons.wikimedia.org/wiki/File:Singly-linked-list.svg