単一リンクリストは、5 つのデータ構造の中で最も単純で、上の 5つの機能し かサポートしません。 単一リンクリストは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または LIFO キューの実装に理想的です。
単一リンクテールキューには以下の機能もあります。
しかし以下に注意してください。
単一リンクテールキューは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または FIFO キューの実装に理想的です。
二重リンクタイプのすべてのデータ構造 (リスト、テールキュー、循環キュー) には 以下の機能もあります。
しかし以下に注意してください。
リンクリストは、二重リンクデータ構造の中で最も単純で、単一リンクリストの 機能に加えて上の機能しかサポートしません。
テールキューには以下の機能もあります。
しかし以下に注意してください。
循環キューには以下の機能もあります。
しかし以下に注意してください。
マクロ定義では、 Fa TYPE はユーザが定義した構造体の名前です。この構造体には、 Fa NAME という名前が付いた、 SLIST_ENTRY STAILQ_ENTRY LIST_ENTRY TAILQ_ENTRY CIRCLEQ_ENTRY という型のフィールドを含める必要があります。 引数 Fa HEADNAME は マクロ SLIST_HEAD STAILQ_HEAD LIST_HEAD TAILQ_HEAD CIRCLEQ_HEAD で宣言する必要のある、ユーザが定義した構造体の名前です。 このマクロの使用法の詳細については、以下の使用例を参照してください。
SLIST_HEAD(HEADNAME, TYPE) head;
ここで Fa HEADNAME は定義する構造体の名前で、 Fa TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ SLIST_HEAD_INITIALIZER はリストの Fa head を初期化します。
マクロ SLIST_EMPTY はリストに要素がない場合に真になります。
マクロ SLIST_ENTRY はリストの要素を接続する構造体を宣言します。
マクロ SLIST_FIRST はリストの先頭の要素を、リストが空なら NULL を返します。
マクロ SLIST_FOREACH は Fa head で参照されるリストを、各要素を順に Fa var に割り当てて順方向に走査します。
マクロ SLIST_INIT は Fa head が参照するリストを初期化します。
マクロ SLIST_INSERT_HEAD は新しい要素 Fa elm をリストの先頭に挿入します。
マクロ SLIST_INSERT_AFTER は要素 Fa listelm の後ろに新しい要素 Fa elm を挿入します。
マクロ SLIST_NEXT はリストの次の要素を返します。
マクロ SLIST_REMOVE_HEAD はリストの先頭から要素 Fa elm を削除します。 最適な効率を得るために、リストの先頭から要素を削除する場合には 一般的な Fa SLIST_REMOVE マクロの代わりにこのマクロを明示的に使用すべきです。
マクロ SLIST_REMOVE はリストから要素 Fa elm を削除します。
SLIST_HEAD(slisthead, entry) head =
SLIST_HEAD_INITIALIZER(head);
struct slisthead *headp; /* 単一リンクリストヘッド */
struct entry {
...
SLIST_ENTRY(entry) entries; /* 単一リンクリスト */
...
} *n1, *n2, *n3, *np;
SLIST_INIT(&head); /* リストを初期化 */
n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */
SLIST_INSERT_HEAD(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */
SLIST_INSERT_AFTER(n1, n2, entries);
SLIST_REMOVE(&head, n2, entry, entries);/* 削除 */
free(n2);
n3 = SLIST_FIRST(&head);
SLIST_REMOVE_HEAD(&head, entries); /* 先頭から削除 */
free(n3);
/* 順走査 */
SLIST_FOREACH(np, &head, entries)
np-> ...
while (!SLIST_EMPTY(&head)) { /* リストの削除 */
n1 = SLIST_FIRST(&head);
SLIST_REMOVE_HEAD(&head, entries);
free(n1);
}
STAILQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ STAILQ_HEAD_INITIALIZER はテールキューの Fa head を初期化します。
マクロ STAILQ_EMPTY はテールキューに要素がない場合に真になります。
マクロ STAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。
マクロ STAILQ_FIRST はテールキューの先頭の要素を、テールキューが空なら NULL を返します。
マクロ STAILQ_FOREACH は Fa head で参照されるテールキューを、各要素を順に Fa var に割り当てて順方向に走査します。
マクロ STAILQ_INIT は Fa head が参照するテールキューを初期化します。
マクロ STAILQ_INSERT_HEAD は新しい要素 Fa elm をテールキューの先頭に挿入します。
マクロ STAILQ_INSERT_TAIL は新しい要素 Fa elm をテールキューの末尾に挿入します。
マクロ STAILQ_INSERT_AFTER は新しい要素 Fa elm を要素 Fa listelm の後ろに挿入します。
マクロ STAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空なら、戻り値は未定義です。
マクロ STAILQ_NEXT はテールキューの次の要素を、この要素が末尾なら NULL を返します。
マクロ STAILQ_REMOVE_HEAD はテールキューの先頭から要素 を削除します。 最適な効率を得るために、テールキューの先頭から要素を削除する場合には 一般的な Fa STAILQ_REMOVE マクロよりもこのマクロを明示的に使用すべきです。
マクロ STAILQ_REMOVE はテールキューから要素 Fa elm を削除します。
STAILQ_HEAD(stailhead, entry) head =
STAILQ_HEAD_INITIALIZER(head);
struct stailhead *headp; /* 単一リンクテールキューヘッド */
struct entry {
...
STAILQ_ENTRY(entry) entries; /* テールキュー */
...
} *n1, *n2, *n3, *np;
STAILQ_INIT(&head); /* キューを初期化 */
n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */
STAILQ_INSERT_HEAD(&head, n1, entries);
n1 = malloc(sizeof(struct entry)); /* 末尾に挿入 */
STAILQ_INSERT_TAIL(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */
STAILQ_INSERT_AFTER(&head, n1, n2, entries);
/* 削除 */
STAILQ_REMOVE(&head, n2, entry, entries);
free(n2);
/* 先頭から削除 */
n3 = STAILQ_FIRST(&head);
STAILQ_REMOVE_HEAD(&head, entries);
free(n3);
/* 順走査 */
STAILQ_FOREACH(np, &head, entries)
np-> ...
/* テールキューの削除 */
while (!STAILQ_EMPTY(&head)) {
n1 = STAILQ_FIRST(&head);
STAILQ_REMOVE_HEAD(&head, entries);
free(n1);
}
/* テールキューの高速な削除 */
n1 = STAILQ_FIRST(&head);
while (n1 != NULL) {
n2 = STAILQ_NEXT(n1, entries);
free(n1);
n1 = n2;
}
STAILQ_INIT(&head);
LIST_HEAD(HEADNAME, TYPE) head;
ここで Fa HEADNAME は定義する構造体の名前で、 Fa TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ LIST_HEAD_INITIALIZER はリストの Fa head を初期化します。
マクロ LIST_EMPTY はリストに要素がない場合に真になります。
マクロ LIST_ENTRY はリストの要素を接続する構造体を宣言します。
マクロ LIST_FIRST はリストの最初の要素を、リストが空なら NULL を返します。
マクロ LIST_FOREACH は Fa head で参照されるリストを、各要素を順に Fa var に割り当てて順方向に走査します。
マクロ LIST_INIT は Fa head が参照するリストを初期化します。
マクロ LIST_INSERT_HEAD は新しい要素 Fa elm をリストの先頭に挿入します。
マクロ LIST_INSERT_AFTER は新しい要素 Fa elm を要素 Fa listelm の後ろに挿入します。
マクロ LIST_INSERT_BEFORE は新しい要素 Fa elm を要素 Fa listelm の前に挿入します。
マクロ LIST_NEXT はリストの次の要素を、この要素が末尾なら NULL を返します。
マクロ LIST_REMOVE は要素 Fa elm をリストから削除します。
LIST_HEAD(listhead, entry) head =
LIST_HEAD_INITIALIZER(head);
struct listhead *headp; /* リストヘッド */
struct entry {
...
LIST_ENTRY(entry) entries; /* リスト */
...
} *n1, *n2, *n3, *np;
LIST_INIT(&head); /* リストを初期化 */
n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */
LIST_INSERT_HEAD(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */
LIST_INSERT_AFTER(n1, n2, entries);
n3 = malloc(sizeof(struct entry)); /* 前に挿入 */
LIST_INSERT_BEFORE(n2, n3, entries);
LIST_REMOVE(n2, entries); /* 削除 */
free(n2);
/* 順走査 */
LIST_FOREACH(np, &head, entries)
np-> ...
while (!LIST_EMPTY(&head)) { /* リストの削除 */
n1 = LIST_FIRST(&head);
LIST_REMOVE(n1, entries);
free(n1);
}
n1 = LIST_FIRST(&head); /* リストの高速な削除 */
while (n1 != NULL) {
n2 = LIST_NEXT(n1, entries);
free(n1);
n1 = n2;
}
LIST_INIT(&head);
TAILQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言されます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ TAILQ_HEAD_INITIALIZER はテールキューの Fa head を初期化します。
マクロ TAILQ_EMPTY はテールキューに要素がない場合に真になります。
マクロ TAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。
マクロ TAILQ_FIRST はテールキューの最初の要素を、テールキューが空なら NULL を返します。
マクロ TAILQ_FOREACH は Fa head で参照されるテールキューを、各要素を順に Fa var に割り当てて順方向に走査します。
マクロ TAILQ_FOREACH_REVERSE は Fa head で参照されるテールキューを、各要素を順に Fa var に割り当てて逆方向に走査します。
マクロ TAILQ_INIT は Fa head が参照するテールキューを初期化します。
マクロ TAILQ_INSERT_HEAD は新しい要素 Fa elm をテールキューの先頭に挿入します。
マクロ TAILQ_INSERT_TAIL は新しい要素 Fa elm をテールキューの末尾に挿入します。
マクロ TAILQ_INSERT_AFTER は新しい要素 Fa elm を要素 Fa listelm の後ろに挿入します。
マクロ TAILQ_INSERT_BEFORE は新しい要素 Fa elm を要素 Fa listelm の前に挿入します。
マクロ TAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空の場合、戻り値は未定義です。
マクロ TAILQ_NEXT はテールキューの次の要素を、その要素が末尾の場合は NULL を返します。
マクロ TAILQ_PREV はテールキューの前の要素を、その要素が先頭の場合は NULL を返します。
マクロ TAILQ_REMOVE は要素 Fa elm をテールキューから削除します。
TAILQ_HEAD(tailhead, entry) head =
TAILQ_HEAD_INITIALIZER(head);
struct tailhead *headp; /* テールキューヘッド */
struct entry {
...
TAILQ_ENTRY(entry) entries; /* テールキュー */
...
} *n1, *n2, *n3, *np;
TAILQ_INIT(&head); /* キューを初期化 */
n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */
TAILQ_INSERT_HEAD(&head, n1, entries);
n1 = malloc(sizeof(struct entry)); /* 末尾に挿入 */
TAILQ_INSERT_TAIL(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */
TAILQ_INSERT_AFTER(&head, n1, n2, entries);
n3 = malloc(sizeof(struct entry)); /* 前に挿入 */
TAILQ_INSERT_BEFORE(n2, n3, entries);
TAILQ_REMOVE(&head, n2, entries); /* 削除 */
free(n2);
/* 順走査 */
TAILQ_FOREACH(np, &head, entries)
np-> ...
/* 逆走査 */
TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
np-> ...
/* テールキューの削除 */
while (!TAILQ_EMPTY(&head)) {
n1 = TAILQ_FIRST(&head);
TAILQ_REMOVE(&head, n1, entries);
free(n1);
}
/* テールキューの高速な削除 */
n1 = TAILQ_FIRST(&head);
while (n1 != NULL) {
n2 = TAILQ_NEXT(n1, entries);
free(n1);
n1 = n2;
}
TAILQ_INIT(&head);
CIRCLEQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE は循環キューにリンクする要素の型です。 循環キューのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ CIRCLEQ_HEAD_INITIALIZER は循環キューの Fa head を初期化します。
マクロ CIRCLEQ_EMPTY は循環キューに要素がない場合に真になります。
マクロ CIRCLEQ_ENTRY は循環キューの要素を接続する構造体を宣言します。
マクロ CIRCLEQ_FIRST は循環キューの先頭の要素を返します。
マクロ CICRLEQ_FOREACH は Fa head で参照される循環キューを、各要素を順に Fa var に割り当てて順方向に走査します。
マクロ CICRLEQ_FOREACH_REVERSE は Fa head で参照される循環キューを、各要素を順に Fa var に割り当てて逆方向に走査します。
マクロ CIRCLEQ_INIT は Fa head が参照する循環キューを初期化します。
マクロ CIRCLEQ_INSERT_HEAD は新しい要素 Fa elm を循環キューの先頭に挿入します。
マクロ CIRCLEQ_INSERT_TAIL は新しい要素 Fa elm を循環キューの末尾に挿入します。
マクロ CIRCLEQ_INSERT_AFTER は新しい要素 Fa elm を要素 Fa listelm の後ろに挿入します。
マクロ CIRCLEQ_INSERT_BEFORE は新しい要素 Fa elm を要素 Fa listelm の前に挿入します。
マクロ CIRCLEQ_LAST は循環キューの末尾の要素を返します。
マクロ CIRCLEQ_NEXT は循環キューの次の要素を返します。
マクロ CIRCLEQ_PREV は循環キューの前の要素を返します。
マクロ CIRCLEQ_REMOVE は要素 Fa elm を循環キューから削除します。
CIRCLEQ_HEAD(circlehead, entry) head =
CIRCLEQ_HEAD_INITIALIZER(head);
struct circleq *headp; /* 循環キューヘッド */
struct entry {
...
CIRCLEQ_ENTRY(entry) entries; /* 循環キュー */
...
} *n1, *n2, *np;
CIRCLEQ_INIT(&head); /* 循環キューを初期化 */
n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */
CIRCLEQ_INSERT_HEAD(&head, n1, entries);
n1 = malloc(sizeof(struct entry)); /* 末尾に挿入 */
CIRCLEQ_INSERT_TAIL(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */
CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
n2 = malloc(sizeof(struct entry)); /* 前に挿入 */
CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
CIRCLEQ_REMOVE(&head, n1, entries); /* 削除 */
free(n1);
/* 順走査 */
CIRCLEQ_FOREACH(np, &head, entries)
np-> ...
/* 逆走査 */
CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
np-> ...
/* 循環キューの削除 */
while (CIRCLEQ_FIRST(&head) != (void *)&head) {
n1 = CIRCLEQ_HEAD(&head);
CIRCLEQ_REMOVE(&head, n1, entries);
free(n1);
}
/* 循環キューの高速な削除 */
n1 = CIRCLEQ_FIRST(&head);
while (n1 != (void *)&head) {
n2 = CIRCLEQ_NEXT(n1, entries);
free(n1);
n1 = n2;
}
CIRCLEQ_INIT(&head);