双方向リスト

http://www.geocities.jp/ky_webid/algorithm/012.html

逆方向にも参照できる双方向リストですね。

循環リストの拡張でやってみます。

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

struct LIST {
    int data;
    int last;
    struct LIST *next;
    struct LIST *prev;
};
typedef struct LIST LIST;

LIST *create_list(int data) {
    LIST *p;
    p = (LIST *)malloc(sizeof(LIST));
    if ( p == NULL ) {
        // メモリ不足エラー
        return NULL;
    }
    p->next = NULL;
    p->prev = NULL;
    p->data = data;
    p->last = 1;
    
    printf("create %p\n",p);
    return p;
}

LIST *add_list (LIST *p,int data) {
    LIST *add,*q;
    
    add = create_list(data);
    
    while( !p->last ){
        p = p->next;
    }
    
    if ( p->next == NULL ) {
        q = p;
    }
    else {
        q = p->next;
    }
    p->last = 0;
    p->next = add;
    q->prev = add;
    add->next = q;
    add->prev = p;
    
    return add;
}

void free_list (LIST *p) {
    LIST *s = p;
    LIST *q;
    do {
        q = p;
        p = p->next;
        printf("free   %p\n",q);
        free(q);
        q = NULL;
    } while ( s!=p );
}

void delete_list (LIST *p,int data) {
    LIST *s = p;
    LIST *q;
    do {
        q = p;
        p = p->next;
        if ( p->data == data ) {
            q->next = p->next;
            q->next->prev = q;
            printf("free   %p\n",p);
            free(p);
            p = NULL;
            // まだ同じ値の要素があるかもしれないので引き続き検索する
            p = q->next;
        }
    } while ( s!=p );
}

void show_list (LIST *p) {
    LIST *s = p;
    
    do{
        printf("%d\n",p->data);
        p = p->next;
    }while( s!=p );
}

void show_prev_list (LIST *p) {
    LIST *s = p;
    
    do{
        printf("%d\n",p->data);
        p = p->prev;
    }while( s!=p );
}

int main (void) {
    LIST *head;
    LIST *p;
    
    head = create_list(100);
    p = add_list(head,200);
    add_list(head,300);
    add_list(p,200);
    add_list(p,500);
    
    delete_list(head,200);
    
    puts("next:");
    show_list(head);
    
    puts("prev:");
    show_prev_list(head);
    
    free_list(head);
    
    return 0;
}

$ main
create 00383148
create 00383160
create 00383178
create 00383190
create 003831A8
free   00383160
free   00383190
next:
100
300
500
prev:
100
500
300
free   00383148
free   00383178
free   003831A8

うまくいってますね。

まだまだ実装が汚いので他の実装例を見ながら少しずつ習得していきます。