/*------------------------------------------------
	連結リストの実装例（リストヘッドによる方法）
 ------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>

//DATA型を定義（正体は int 型）
typedef int DATA;

//NODE型の構造体定義
typedef struct node {
	struct node	*next;	// 次のノードへのポインタ
	DATA		data;	// データ部
} NODE;

//リストの先頭ポインタを保持する変数の宣言
NODE	list_head;

//関数のプロトタイプ宣言
void addNewNodeToHead( DATA* );	// 先頭ノードを追加
void deleteFirstNode();			// 先頭ノードを削除
void showList();				//リストの表示

/*---------------------------------------
	メイン関数
---------------------------------------*/
int main()
{
	int		key; 
	DATA	value = 1;	//格納する値を生成するための変数
	
	// リストヘッドの初期化
	list_head.next = NULL;
	
	//終了の 9 が入力されるまで繰り返す
	while( key != 9 ) {
		
		//リストの表示
		showList();
		
		//メニューを表示
		printf("1.先頭に追加，2.先頭を削除，9.終了：");
		
		//メニュー番号の入力と分岐
		scanf("%d",&key);		
		switch( key ) {
			
			case 1: //リストの先頭にデータを追加

				//追加するDATA（いまは整数値）を引数に追加関数をよぶ
				addNewNodeToHead( &value );	//注意：ノードを追加後，ついでに value をインクリメントしている
				break;
				
			case 2: //先頭のデータを削除

				//先頭の要素を削除する関数をよぶ
				deleteFirstNode();
				break;
		}		
	}
	
	return 0;
}

//リストの先頭にノードを追加する
void addNewNodeToHead( DATA *d )
{
	int i,key;
	NODE *newNode, *pos;
	
	printf("何番目を追加しますか:");
	scanf("%d",&key);
	
	if(key == 0)
	{
	    printf("0番目には追加できません。\n");
	    return ;
	}
	pos = &list_head;
	
	for(i = 0; i < key-1; i++)
	{
	    if(pos->next == NULL)
	        break;
	    pos = pos->next;
	}
	
	if(i != key - 1)
	{
	    printf("%d番目には追加できません。\n",key);
	    return ;
	}
	newNode = (NODE *)malloc(sizeof(NODE));
	
	if(newNode == NULL)
	    exit(1);
	
	newNode->next = pos->next;
	newNode->data = (*d)++;
	pos->next = newNode;
}

// リストの先頭ノードを削除する
void deleteFirstNode()
{
    int i,key;
	NODE *pos, *prevNode;
	
	printf("何番目を削除しますか:");
	scanf("%d",&key);
	
	if(key == 0)
	    return ;
	
	pos = &list_head;
	
	for(i = 0; i < key-1; i++)
	{
	    if(pos->next == NULL)
	        break;
	    pos = pos->next;
	}
	
	if(i != key - 1)
	{
	    printf("%d:番目の要素はありません。\n",key);
	    return ;
	}
	if(pos->next == NULL)
	{
	    printf("%d:番目の要素はありません。\n",key);
	    return ;
	}
	
	prevNode = pos->next;
	pos->next = prevNode->next;
	
}

//連結リストの状態を表示する
void showList()
{
    int cnt = 0;
	NODE *pos;	//読み出し位置にあるノードへのポインタ変数
	
	//最初のノードのアドレスを取得（注意: リストが空の場合は NULL が入っている）
	pos = list_head.next;
    
    while(pos != NULL)
    {
        pos = pos->next;
        cnt++;
    }
    if(cnt != 0)
        printf("%d: ", cnt);
    
    //最初のノードのアドレスを取得（注意: リストが空の場合は NULL が入っている）
	pos = list_head.next;
    
	//末尾のノードまで繰り返す
	while ( pos != NULL ) {
		printf("%d ", pos->data);	//データ参照して表示
		pos = pos->next;			//次のノードに進む
	}
	
	printf("\n");
}