C言語で学ぶリンクリスト（連結リスト）の基本概念と4つの種類

はじめに：配列とポインタの違いを理解しよう

リンクリスト（連結リスト）を理解する前に、まずC言語における「配列の欠点」と「ポインタの利点」について確認しておきましょう。この2つの違いを知ることが、リンクリストがなぜ有効なデータ構造なのかを理解する鍵となります。

配列の欠点

• 静的なメモリ割り当て：配列はコンパイル時にサイズが決定されるため、実行中にサイズを変更できません。

• メモリの無駄：実際に必要なデータ量より大きい配列を確保すると、未使用の領域が無駄になります。

• メモリ不足のリスク：逆に、確保したサイズを超えるデータは格納できず、メモリが不足する可能性があります。

ポインタの利点

• 動的なメモリ割り当て：malloc() などの関数を使えば、実行時に必要な分だけメモリを確保できます。

• 効率的なメモリ使用：必要なときに必要なだけメモリを利用するため、無駄がありません。

リンクリスト（連結リスト）とは

リンクリストは動的なメモリ割り当てを利用するデータ構造で、要素の追加や削除に応じてサイズが自動的に拡大・縮小します。リンクリストは「ノード（node）」と呼ばれる要素の集合として定義され、各ノードは「データ部」と「リンク部」という2つの部分で構成されます。

データ・リンク・リンクリストの関係は、下図のように表されます。

C言語では、ノードは次のように構造体で表現できます。

struct node {
    int data;              /* データ部 */
    struct node *next;     /* リンク部（次のノードへのポインタ） */
};

リンクリストの種類

リンクリストには、主に以下の4種類があります。

• 単方向リンクリスト（Singly Linked List）
• 双方向リンクリスト（Doubly Linked List）
• 循環単方向リンクリスト（Circular Singly Linked List）
• 循環双方向リンクリスト（Circular Doubly Linked List）

1. 単方向リンクリスト

下図のような構造で表されます。

ノードは次の2つの部分で構成されます。

• データ部（Data）：実際の値を格納する部分
• リンク部（Link）：次のノードを指すポインタ

リンクフィールドは、常にリスト内の次のノードを指します。また、リストの末尾ノードのリンクフィールドはNULLとなり、これがリストの終端を示します。

2. 双方向リンクリスト

下図のような構造で表されます。

ノードは次の3つの部分で構成されます。

• データ部（Data）：実際の値を格納する部分
• 左リンク（Left Link / prev）：前のノードを指すポインタ
• 右リンク（Right Link / next）：次のノードを指すポインタ

左リンクは常にリスト内の左側（前）のノードを指し、右リンクは常に右側（次）のノードを指します。先頭ノードの左リンクと末尾ノードの右リンクはNULLでなければなりません。前後どちらの方向にもたどれるため、単方向リンクリストよりも柔軟な操作が可能です。

3. 循環単方向リンクリスト

下図のような構造で表されます。

ノードは次の2つの部分で構成されます。

• データ部（Data）
• リンク部（Link）

リンクフィールドは常にリスト内の次のノードを指します。通常の単方向リンクリストと異なるのは、末尾ノードのリンク部がNULLではなく先頭ノードを指す点です。これによりリスト全体が環状につながり、どのノードからでも一周できる構造になります。

4. 循環双方向リンクリスト

下図のような構造で表されます。

ノードは次の3つの部分で構成されます。

• データ部（Data）
• 左リンク（Left Link）
• 右リンク（Right Link）

左リンクは常にリスト内の左側のノードを指し、右リンクは右側のノードを指します。循環構造であるため、先頭ノードの左リンクは末尾ノードを指し、末尾ノードの右リンクは先頭ノードを指します。前後双方向に循環してたどれる、最も柔軟なリンクリストです。

まとめ

リンクリストは、ポインタによる動的メモリ割り当てを活かすことで、配列の「サイズが固定」という制約を克服できるデータ構造です。用途に応じて単方向・双方向・循環の4種類から適切なものを選ぶことで、効率的なデータ管理を実現できます。