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

struct BD_List {
  struct BD_List* prev ;
  int  data ;
  struct BD_List* next ;
} ;

// 木を生成する補助関数
struct BD_List* bd_cons( struct BD_List* p ,
			 int    x ,
			 struct BD_List* n ) {
  struct BD_List* ans ;
  ans = (struct BD_List*)malloc( sizeof( struct BD_List* ) ) ;
  if ( ans != NULL ) {
    ans->prev = p ;
    ans->data = x ;
    ans->next = n ;
  }
  return ans ;
}

int main() {
  struct BD_List* top ;
  struct BD_List* p ;
  // 順方向のポインタでリストを生成
  top = bd_cons( NULL , 1 ,
		 bd_cons( NULL , 2 ,
			  bd_cons( NULL , 3 , NULL ) ) ) ;
  // top->[x|1|o]->[x|2|o]->[x|3|x]
  
  // 逆方向のポインタを埋める
  top->next->prev = top ;
  top->next->next->prev = top->next ;
  // top->[x|1|o]<=>[o|2|o]<=>[o|3|x]
  
  // リストを辿る処理
  for( p = top ; p->next != NULL ; p = p->next )
    printf( "%d\n" , p->data ) ;
  for(         ; p->prev != NULL ; p = p->prev )
    printf( "%d\n" , p->data ) ;

  return 0 ;
}