Doubly-linked List(LIST)

双方向リスト[Doubly Linked List]は、エレメントの次エレメントだけでなく前エレメントのポインタを持った構造で、前後に自由に移動することが出来ます。

双方向リストの構造

LIST 構造体の定義

LIST構造を使用するには、まずLIST形式のデータ構造を定義必要があります。

LIST_ENTRY(type)

LIST_ENTRYはLIST形式のデータ構造を定義します。各エレメントに数字が１つだけ入っているLIST構造、Listsを定義してみると、下記のようになります。

struct Lists {
    LIST_ENTRY(Lists) list_ptr;
                int32_t data;
};

これは、次のように展開されます。

struct Lists {
    struct {
        struct Lists *le_next;
        struct Lists **le_prev;
    } list_ptr;
                int32_t data;
};

これは定義だけで、まだ実体は無いことに注意してください。

LIST_HEAD(name, type)

LIST_HEADは、エレメントの先頭アドレスが入る構造体を定義します。

LIST_HEAD(ListsHead, Lists);

これは、次のように展開されます。

struct ListsHead { struct Lists *lh_first; };

これも定義だけで、まだ実体は無いことに注意してください。

LIST 構造体の初期化

LIST_HEAD_INITIALIZER(head)

LIST_HEAD_INITIALIZERは、LIST_HEADを初期化します。次のように使用します。

// LISTヘッダの実体を定義
struct ListsHead lists_head = LIST_HEAD_INITIALIZER(&lists_head);

LIST_INIT(head)

LIST_INITは、LISTを初期化します。次のように使用します。

if(!(LIST_EMPTY(&lists_head)))         // LISTが空であるかチェック
    LIST_INIT(&lists_head);            // LISTの初期化

LIST Access Methods

LIST_FIRST(head)

LIST_FIRSTは、LISTの先頭エレメントのポインタを返します。

arithmetic = LIST_FIRST(&lists_head);

LIST_END(head)

LIST_ENDは、NULLを返します。

LIST_EMPTY(head)

LIST_EMPTYは、LISTが空であるか調べます。

LIST_NEXT(elm, field)

LIST_NEXTは、エレメント(elm)に連結されている次エレメントのポインタを返します。

arithmetic_next = LIST_NEXT(arithmetic,list_ptr);

LIST Insert Methods

LIST_INSERT_HEAD(head, elm, field)

LIST_INSERT_HEADは、新しいエレメント(elm)をLIST(head)に追加します。

// データ作成
for(i=0;i<5;i++){
    number[i].data = i;
    number[i].list_ptr.le_next = NULL;
    number[i].list_ptr.le_prev = NULL;
}
for(i=1;i<=2;i++){
    // LISTにデータをセット
    LIST_INSERT_HEAD(&lists_head, &number[i], list_ptr);
}

この結果は、次のようになります。

LIST_INSERT_HEADの結果

LIST_INSERT_AFTER(listelm, elm, field)

LIST_INSERT_AFTERは、指定されたエレメント(listelm)の後に、新しいエレメント(elm)を追加します。

arithmetic      = LIST_FIRST(&lists_head);              // 最初のエレメント(data=2)
arithmetic_next = LIST_NEXT(arithmetic,list_ptr);       // 指定エレメントの次エレメント(data=1)
LIST_INSERT_AFTER(arithmetic_next,&number[0],list_ptr); // data=1)の後ろに(data=0)を挿入

この結果は、arithmetic_next(data=1)の後ろにエレメントnumber[0](data=0)が挿入されます。

LIST_INSERT_AFTERの結果

LIST_INSERT_BEFORE(listelm, elm, field)

LIST_INSERT_BEFOREは、指定されたエレメント(listelm)の前に、新しいエレメント(elm)を追加します。

LIST_INSERT_BEFORE(arithmetic,&number[4],list_ptr);     // (data=2)の前に(data=4)を挿入

この結果は、arithmetic(data=2)の前にエレメントnumber[4](data=4)が挿入されます。

LIST_INSERT_BEFOREの結果

LIST_REPLACE(elm, elm2, field)

LIST_REPLACEは、elmのエレメントをLISTから切り放し、切り放した所にelm2を挿入します。

LIST_REPLACE(&number[4],&number[3],list_ptr);           // (data=4)を(data=3)に置換える

結果は、data=4のエレメントが切り放され、data=3のエレメントが挿入されます。

LIST_REPLACEの結果

LIST Loop Methods

LIST_FOREACH(var, head, field)

LIST_FOREACHは、headに格納されたエレメントを最初から終りまでループして、varにポインタを返します。

// エレメントの最初から終わりまでループ 
LIST_FOREACH(arithmetic, &lists_head, list_ptr){
   printf("%d\n",arithmetic->data);
}

結果は、下記のようになります。

LIST Remove Methods

LIST_REMOVE(head, elm, type, field)

LIST_REMOVEは、指定されたエレメント(elm)をLIST(head)から削除します。

while((arithmetic = LIST_FIRST(&lists_head)))
    LIST_REMOVE(arithmetic,list_ptr);          // 指定したエレメントを削除

LISTデータの操作sample

LISTデータの操作sampleです。

Last modified: Thu Jan 24 18:10:35 2008 JST