双方向連結リスト
双方向のリンクです。
「双方向連結リスト」はCoddyKit上の無料C Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
双方向のリンク
双方向連結リストでは、各ノードが2つのポインターを持ちます。1つはnextノードを指し、もう1つはprev（前の）ノードを指します。
これによりリストを両方向にたどれるようになり、削除も簡単になります。
#include <stdio.h>
struct Node {
int value;
struct Node *prev;
struct Node *next;
};
int main(void) {
printf("Each node links forward and backward\n");
return 0;
}ノードを定義する
このstructでは、nextに加えてprevポインターを追加します。リストの両端では、どちらもNULLです。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
int main(void) {
struct Node *n = malloc(sizeof(struct Node));
n->value = 1; n->prev = NULL; n->next = NULL;
printf("%d\n", n->value);
free(n);
return 0;
}作成用ヘルパー
これまでと同様に、ヘルパー関数でメモリ確保を一元化します。prevとnextの両方をNULLに設定します。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v) {
struct Node *n = malloc(sizeof(struct Node));
n->value = v; n->prev = NULL; n->next = NULL;
return n;
}
int main(void) {
struct Node *n = make(42);
printf("%d\n", n->value);
free(n);
return 0;
}ノードを双方向につなぐ
2つのノードをつなぐときは、両方の方向を更新する必要があります。最初のノードのnextと、2番目のノードのprevを更新します。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2);
a->next = b;
b->prev = a;
printf("forward %d, back %d\n", a->next->value, b->prev->value);
free(a); free(b);
return 0;
}先頭に挿入する
先頭に追加する場合、新しいノードのnextを古いheadに設定し、古いheadのprevを新しいノードに設定してから、headを新しいノードに移します。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
void push(struct Node **head, int v) {
struct Node *n = make(v);
n->next = *head;
if (*head) (*head)->prev = n;
*head = n;
}
int main(void) {
struct Node *head = NULL;
push(&head, 2); push(&head, 1);
printf("%d %d\n", head->value, head->next->value);
return 0;
}前方向に走査する
前方向への走査は単方向連結リストと同じです。NULLになるまでnextをたどります。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2);
a->next = b; b->prev = a;
for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
printf("\n");
free(a); free(b);
return 0;
}後方向に走査する
大きな利点は、どのノードからでもprevポインターをたどり、headに到達するまで後方向に進めることです。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2), *c = make(3);
a->next = b; b->prev = a; b->next = c; c->prev = b;
for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
printf("\n");
free(a); free(b); free(c);
return 0;
}削除が簡単
各ノードが前のノードを把握しているため、前のノードを探さずに削除できます。
node->prevとnode->nextを両方向でつなぐだけです。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
void del(struct Node **head, struct Node *n) {
if (n->prev) n->prev->next = n->next; else *head = n->next;
if (n->next) n->next->prev = n->prev;
free(n);
}
int main(void) {
struct Node *a = make(1), *b = make(2), *c = make(3);
a->next=b; b->prev=a; b->next=c; c->prev=b;
struct Node *head = a;
del(&head, b);
printf("%d %d\n", head->value, head->next->value);
return 0;
}両隣を更新する
ノードを削除するときは、前のノードのnextと、次のノードのprevを両方必ず修正してください。
存在しない隣接ノードを間接参照しないよう、両端ではそれぞれNULLかどうかを確認します。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2);
a->next = b; b->prev = a;
a->next = NULL;
free(b);
printf("now only %d remains\n", a->value);
free(a);
return 0;
}tailポインターを保持する
多くの双方向連結リストでは、最後のノードを指すtailポインターも保持します。これにより、末尾への追加と末尾からの後方向走査をO(1)で行えます。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *head = make(1), *tail = head;
struct Node *n = make(2);
tail->next = n; n->prev = tail; tail = n;
printf("tail = %d\n", tail->value);
free(head); free(n);
return 0;
}トレードオフ
双方向連結リストは、ノードごとにポインターが1つ増えるため、より多くのメモリを必要とします。また、変更のたびに2つのリンクを更新する必要があります。
その代わり、双方向の走査と、既知のノードのO(1)削除が可能になります。必要に応じて選択してください。
#include <stdio.h>
int main(void) {
printf("Singly: less memory, one-way\n");
printf("Doubly: more memory, two-way + easy delete\n");
return 0;
}クイックチェック
双方向連結リストについての理解度を確認しましょう。
まとめ
双方向連結リストについて学びました。
- 各ノードは
prevとnextの両方のポインターを持ちます。 - リンクをつなぐには、両方の方向を更新する必要があります。
- 前方向と後方向に走査でき、既知のノードをO(1)で削除できます。
- メモリの使用量とポインター更新の回数が増えることが代償です。tailポインターがあれば、末尾への追加をO(1)で行えます。
よくある質問
「双方向連結リスト」レッスンは無料ですか？
はい。「双方向連結リスト」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「双方向連結リスト」で何を学びますか？
双方向のリンクです。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「双方向連結リスト」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。