[C言語]双方向リストとその基本操作(追加、削除、挿入)関数の実装[コード付]

どうも〜　シュモクザメです。
今回は双方向リストです！
以前、普通の双方向リストについて扱ったので、ぜひそちらもご覧ください！！⬇︎

双方向リストとは？
コードの実装
全体のコードと動かしてみた結果
まとめ

双方向リストとは？

まず双方向リストについて。
普通の線形リストについては知っている前提で話していきますね。

普通の線形リストはこのようなイメージ⬇

︎まあ普通ですよね。
一方双方向リストはこのようなイメージ⬇︎

ぱっと見で違う点がわかりますね。
双方向リストでは先頭から末尾にかけてのポインタのみではなく、
反対方向のポインタも各ノードが持っています。

つまり、ひとつのノードにつき２つポインタを持っていて、前後のノードから指されているってこと。

逆に言えばそれ以外は普通の線形リストと変わらないとも捉えられるね

メリットは普通のリストでは不可能な、反対方向からも探索等が行えることですね。
デメリットはポインタが増える分、つなぎ変えが少し面倒ってことですね。

コードの実装

早速コードの実装です。

前提

前提として以下のように双方向リストを作成していきます

headは先頭を指すポインタで、tailは末尾を指すポインタです。

構造体の定義

まずは構造体を定義しましょう。

typedef struct list{
    int date;
    struct list *next;
    struct list *prev;
}list;

以前の記事などではなかった、list *prevがあります。
これは反対方向を指すポインタです。

ノードを作成する関数

list *cre(void){
    list *A;
    A = (list*)malloc(sizeof(list));
    
    return A;
}

リストの要素、ノードを生成する関数です。
mallocでメモリを確保して、その確保したメモリを指すポインタを返す関数ですね。

リストの末尾にノードを追加する関数

ノードの末尾に追加する関数です

void list_add(list **tail,int value){
    list *new;
    new = cre();
    new->date = value;
    
    list *p = *tail;
    p->next = new;
    new->prev = p;
    new->next = NULL;
    
    *tail = new;
}

仮引数は末尾を示すlist型のポインタのポインタと、追加するノードの値valueです。

末尾を指すポインタのポインタ、、、

ポインタのポインタ、、ややこしいですよね、、
感覚はmain関数内でリストの末尾を指すポインタtailを定義するんですが、
この操作関数の中でtailの指す先を変更したい！！！
だからポインタのポインタで考える！！
って感じですね。

てことで本文の解説に入りましょう。
一旦listのポインタ型のpを定義して、それが末尾を指すように

list *p = *tail;

とします。(tailはポインタのポインタ型なので、✳︎を一つつければポインタ型になりますね)

ここからは前回の線形リストの時と同様につなぎ変えを行なっています。

list *p = *tail;
p->next = new;
new->prev = p;
new->next = NULL;

prevが増えただけで特に変わったところはないのですね。
不安な場合は是非前回の記事をチェックしてください！！

そして最後にtailの指す場所を変更します。

*tail = new;

新しいノードが末尾にくるのでtailはnewを指せば良いですね

リストにノードを挿入する関数

次はノードをリストの末尾以外に追加する、つまり挿入する時の関数です。

void list_insert(list **tail, list **head, int value){
    int n;
    printf("何番目に要素を追加しますか？(先頭は0番目):");
    scanf("%d",&n);
    
    list *new;
    new = cre();
    new->date = value;
    list *p = *head;
    if(n==0){
        p->prev = new;
        *head = new;
        new->next = p;
        new->prev = NULL;
    }else{
        for(int i=0; i<n; i++){
            p = p->next;
        }
        p->prev->next = new;
        new->next = p;
        new->prev = p->prev;
        p->prev = new;
    }
}

仮引数は先ほどと同じように末尾を示すlist型のポインタのポインタと追加するノードの値value、そして先頭を示すlist型のポインタのポインタを受け取ります。

何番目に挿入するかを入力した後は先ほどと同様にノードを生成して今度は✳︎p = ✳︎headとします。
そしてif文。ここではn==0か調べて先頭に挿入するかどうかを判定してます。

先頭に挿入する場合

pが現在の先頭を指していることからprevを用いてnewをその前に割り込むようにしてます

p->prev = new;
*head = new;
new->next = p;
new->prev = NULL;

その際headが新しい要素(新しい先頭)を指すように、
そして新しい要素のprevはNULLにすることに注意です。

先頭以外に挿入する場合

　　　　　for(int i=0; i<n; i++){
            p = p->next;
        }
        p->prev->next = new;
        new->next = p;
        new->prev = p->prev;
        p->prev = new;

まずfor文を用いて挿入する位置までpを進めます。
ここら辺は上にも貼った線形リストの走査の記事で解説してるので是非どうぞ！！

そのあとはまたつなぎ変えを行います。

p->prev->next = new、、？？

やっぱここはややこしいですよね。
言葉では伝えづらいのでイメージ図をどうぞ

ポイントはp->prev = newを入れる位置ですね。
これを入れた時点でpの一つ前の要素がnewになっちゃいます。
となると、newを入れる前のpの一つ前の要素にアクセスできなくなるので、そこら辺のつなぎ変えができなくなりますね。
なので上のようなコードの順番でつなぎ変えを行なっています。

ノードを削除する関数

双方向リストからノードを削除する関数です。

void list_delete(list **tail,list **head){
    int n;
    printf("何番目の要素を削除しますか？(先頭は0番目):");
    scanf("%d",&n);
    
    list *p = *head;
    if(n==0){
        *head = p->next;
        p->next->prev = NULL;
        p->next = NULL;
    }else{
        for(int i=0; i<n; i++){
            p = p->next;
        }
        if(p->next == NULL){
            *tail = p->prev;
            p->prev->next = NULL;
            p->prev = NULL;
        }else{
            p->prev->next = p->next;
            p->next->prev = p->prev;
            p->next = NULL;
            p->prev = NULL;
        }
    }
}

仮引数はこれまでと同様list型の末尾を示すポインタのポインタとlist型の先頭を示すポインタのポインタをうけとります。

何番目の要素を削除するかを入力した後は✳︎p = ✳︎headとします。
そしてif文。ここではまたn==0か調べて先頭を削除するかどうかを判定してます。

先頭のノードを削除する場合

ここまでくればわかると思います。
先頭を削除するってことはheadを付け替える必要がありますね。
てことでこんな感じです。

*head = p->next;
p->next->prev = NULL;
p->next = NULL;

p->next->prev=NULLで削除する要素に指さない様にしてます。

先頭以外のノードを削除する場合

とりあえず先ほどと同様削除する場所までpを進めます。

for(int i=0; i<n; i++){
            p = p->next;
        }

ここからはさらに場合分けです。

末尾のノードを削除する場合

はい。もうわかりますよね。
末尾を削除ってことはtailを繋ぎ変えようってことですね。

if(p->next == NULL){
            *tail = p->prev;
            p->prev->next = NULL;
            p->prev = NULL;

末尾かどうかはp->nextがNULLかで判断します。
そこからは繋ぎ変えてるだけですね。

末尾でも先頭でもないノードを削除する関数

else{
            p->prev->next = p->next;
            p->next->prev = p->prev;
            p->next = NULL;
            p->prev = NULL;
        }

ここはtailもheadも何も関係ないところですね。
若干ややこしいですが落ち着けば大丈夫だと思います。

リストの中身を出力する関数

void list_show_head(list *head){
    printf("show_head\n");
    for(list *p=head; p!=NULL; p=p->next){
        printf("%d\n",p->date);
    }
    printf("---------\n");
}

void list_show_tail(list *tail){
    printf("show_tail\n");
    for(list *p=tail; p!=NULL; p=p->prev){
        printf("%d\n",p->date);
    }
    printf("---------\n");
}

最後は出力の関数です。
せっかくの双方向リストなので先頭からも末尾からもリストを辿りましょう。
ってことで二つ出力関数を作成しました。内容は簡単ですね。
NULLにあたるまで回すだけです。

全体のコードと動かしてみた結果

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

typedef struct list{
    int date;
    struct list *next;
    struct list *prev;
}list;

void list_show_head(list *head){
    printf("show_head\n");
    for(list *p=head; p!=NULL; p=p->next){
        printf("%d\n",p->date);
    }
    printf("---------\n");
}

void list_show_tail(list *tail){
    printf("show_tail\n");
    for(list *p=tail; p!=NULL; p=p->prev){
        printf("%d\n",p->date);
    }
    printf("---------\n");
}


list *cre(void){
    list *A;
    A = (list*)malloc(sizeof(list));
    
    return A;
}

void list_add(list **tail, int value){
    list *new;
    new = cre();
    new->date = value;
    
    list *p = *tail;
    p->next = new;
    new->prev = p;
    new->next = NULL;
    
    *tail = new;
}

void list_insert(list **tail, list **head, int value){
    int n;
    printf("何番目に要素を追加しますか？(先頭は0番目):");
    scanf("%d",&n);
    
    list *new;
    new = cre();
    new->date = value;
    list *p = *head;
    if(n==0){
        p->prev = new;
        *head = new;
        new->next = p;
        new->prev = NULL;
    }else{
        for(int i=0; i<n; i++){
            p = p->next;
        }
        p->prev->next = new;
        new->next = p;
        new->prev = p->prev;
        p->prev = new;
    }
}

void list_delete(list **tail,list **head){
    int n;
    printf("何番目の要素を削除しますか？(先頭は0番目):");
    scanf("%d",&n);
    
    list *p = *head;
    if(n==0){
        *head = p->next;
        p->next->prev = NULL;
        p->next = NULL;
    }else{
        for(int i=0; i<n; i++){
            p = p->next;
        }
        if(p->next == NULL){
            *tail = p->prev;
            p->prev->next = NULL;
            p->prev = NULL;
        }else{
            p->prev->next = p->next;
            p->next->prev = p->prev;
            p->next = NULL;
            p->prev = NULL;
        }
    }
}

int main(int argc, const char * argv[]) {
    list A;
    A.date = 0;
    A.next = NULL;
    A.prev = NULL;
    
    list *head = &A;
    list *tail = &A;
    
    list_add(&tail, 1);
    list_add(&tail, 2);
    list_add(&tail, 3);

    list_show_head(head);
    
    list_delete(&tail, &head);
    list_show_head(head);
    
    list_add(&tail, 7);
    list_show_head(head);
    
    list_insert(&tail, &head, 8);
    list_show_head(head);
    list_show_tail(tail);
    return 0;
}

実行結果が以下です