連結リスト②（双方向・循環）　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【データ構造】　第４章

/*
    要素を逆順に出力する
*/
void print_list(void)
{
    struct LinkedList_tag* p = gHead.prev;

    if( p == NULL ){
        puts( "リストは空です。" );
        return;
    }

    while( p != &gHead ){
        printf( "%d\n", p->value );
        p = p->prev;
    }
}

/*
    指定の値を持った要素を探す

    引数：
        start:  探索を開始する位置。
        value:  探す値。
    戻り値：
        start から探索を開始し、最初に見つけた value を持つ要素のメモリアドレスを返す。
        見つからなければ NULL を返す。
    備考：
        探索は、引数start の位置から開始され、最初に見つけた要素を返す。
*/
struct LinkedList_tag* search_elem(struct LinkedList_tag* start, int value)
{
    struct LinkedList_tag* p = start;

    do {
        if( p->value == value ){
            return p;
        }
        p = p->next;
    } while( p != start );

    return NULL;
}

/*
    要素を挿入する

    引数：
        value：  挿入する値。
        pos:    挿入する位置にある値。この値を持った要素を探し、その要素の直後に挿入する。
    戻り値：
        成功したら 0以外、失敗したら 0 を返す。
*/
int insert_elem(int value, int pos)
{
    // 追加位置を探す
    struct LinkedList_tag* p = search_elem( pos );
    if( p == NULL ){
        return 0;
    }

    // 追加する要素を作る
    struct LinkedList_tag* elem = malloc( sizeof(struct LinkedList_tag) );
    if( elem == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( 1 );
    }
    elem->value = value;
    elem->next = p->next;  // p と p->next の隙間に挿入する
    elem->prev = p;        // p と p->next の隙間に挿入する

    p->next = elem;           // p の直後に挿入された
    elem->next->prev = elem;  // elem->next にとっての prev は、挿入された elem

    return 1;
}