C言語アルゴリズム-連結リスト

リストデータ構造について

リストとは

リストとは、多数のデータ要素を一定の形式に従って並べて扱うデータ構造です。

リスト構造は複数のデータを一覧表のように関連付けてまとめて扱いたい場合に用います。

線形リストと連結リストの違い

線形リスト(linear list)とは、要素が順序付けされたリストデータ構造のことです。例えば、配列は代表的な線形リストと言えます。なお、C言語における線形リストは、同じ要素のデータをメモリアドレス順に並べたものを指すと考えることができます。

連結リスト(linked list)とは、要素を何らかの方法でつなぎ合わせた（連結した）データ構造です。連結リストでは、配列のように各要素を連続的なメモリアドレスに並べることをしません。各要素は、メモリアドレス上に飛び飛びの位置に置かれており、それぞれをポインタで「連結（リンク）」します。

なお、単にリストといった場合、通常は連結リストのことを指します。

リストの種類

単方向リスト (singly linked list)
- 単方向リストとは、要素がＡ→Ｂ→Ｃ→Ｄのように一方向に次々連結されていくデータ構造です。構造が単純であるが、シーケンシャルなアクセスしかできないという問題があります。
双方向リスト (doubly-linked list)
- 双方向リストとは、要素がＡ⇔Ｂ⇔Ｃ⇔Ｄのように前後に対して連結されているデータ構造です。メモリの容量を多く用いることとなりますが、ある要素から逆順にアクセスするような操作が可能となります。
循環リスト (circular list)
- 循環リストとは、Ａ→Ｂ→Ｃ→Ｄ→Ａのように最後の要素が最初の要素にリンクするように連結されたデータ構造です。任意の要素から開始してリスト全体をたどることができます。
多重リスト構造 (multi list structure)
- セルの繋ぎを前後だけでなく上下左右として、３次元的にデータを構造化します。要素同士が複雑に関係し合うデータを扱うことができます。

セル (cell)とは

セルとは、リスト構造においてデータを格納する入れ物のことです。ノードと呼ばれることもあります。

C言語でリストを作成する場合、たいてい構造体を利用します。構造体メンバのnextは次のセルへのポインタです。


struct cell {
    struct cell *prev;
    struct cell *next;
    int key;
    data_t data;
};

C言語による連結リスト構造のサンプルプログラム

最も単純化した単方向連結リストです。新規セルを最後尾に追加する構造としています。


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

/* セルの定義 */
struct cell{
    struct cell *next;
    int data;
};
typedef struct cell cell_t;

/*!
 * @brief       新規セルを生成する。
 * @param[in]   data  データ
 * @return      新規セルのアドレスを返す。失敗の場合はNULLを返す。
 */
cell_t *
list_alloc(int data)
{
    cell_t *new = NULL;

    new = (cell_t *)malloc(sizeof(cell_t));
    if(new == NULL){
        fprintf(stderr, "ERROR: list_alloc(): %s\n", strerror(errno));
        return(NULL);
    }

    new->next = NULL;
    new->data = data;

    return(new);
}

/*!
 * @brief      リスト末尾に新規セルを追加する
 * @param[in]  header  リストの先頭要素
 * @param[in]  data  データ
 */
int
list_add(cell_t *header, int data)
{
    cell_t *next = NULL;
    cell_t *prev = header;

    /* セルを生成する */
    next = list_alloc(data);
    if(next == NULL) return(-1);

    /* 末尾にセルを追加する */
    while(prev->next != NULL){
        prev = prev->next;
    }
    prev->next = next;

    return(0);
}

/*!
 * @brief      リストの要素を全て解放する
 * @param[in]  header  リストの先頭要素
 */
void
list_free(cell_t *header)
{
    cell_t *temp = header;
    cell_t *swap = NULL;

    while(temp != NULL){
        swap = temp->next;
        free(temp);
        temp = swap;
    }
}

/*!
 * @brief      リストの要素を一覧表示する
 * @param[in]  header  リストの先頭要素
 */
static void
list_print(cell_t *header)
{
    cell_t *p = header;

    printf("list{ ");
    while(p != NULL){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("}\n");
}

int
main(void)
{
    int cnt = 0;

    /* 先頭セルを用意する */
    cell_t *header = list_alloc(0);
    if(header == NULL) return(-1);

    /* 要素を追加する */
    for(cnt = 1; cnt < 10; cnt++){
        list_add(header, cnt);
    }
    list_print(header);

    /* リストを解放する */
    list_free(header);

    return(0);
}