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

typedef int DATA;

typedef struct node {
  struct node *next;
  DATA data;
} NODE;

NODE list_head;

void addNewNodeToHeadLocal(struct node *root, int data, int pos) {
  NODE *newNode;
  if (root->next == 0 || pos <= 0) {
    if ((newNode = malloc(sizeof(NODE))) != 0) {
      newNode->next = root->next;
      root->next = newNode;
      newNode->data = data;
    }
  } else {
    addNewNodeToHeadLocal(root->next, data, pos - 1);
  }
}

void addNewNodeToHead(DATA *data, int pos) {
  addNewNodeToHeadLocal(&list_head, (*data)++, pos - 1);
}

void deleteFirstNodeLocal(struct node *root, int pos, int key) {
  NODE *prevNode;
  if (pos <= 0) {
    if (root->next) {
      prevNode = root->next;
      root->next = prevNode->next;
      free(prevNode);
    } else {
      printf("%d番目の要素はありません。\n",key);
    }
  } else {
    if (root->next)
      deleteFirstNodeLocal(root->next, pos - 1, key);
    else
      deleteFirstNodeLocal(root, pos - 1, key);
  }
}

void deleteFirstNode(int pos,int key) {
  deleteFirstNodeLocal(&list_head, pos - 1,key);
}

void showList(void) {
  NODE *pos;
  pos = list_head.next;
  while ( pos != NULL ) {
    printf("%d ", pos->data);
    pos = pos->next;
  }
  printf("\n");
}

int main() {
  int key, pos; 
  DATA value;
  
  value = 1;
  list_head.next = NULL;
  while (key != 9) {
    showList();
    printf("１．n番目を追加、２．n番目を削除、９．終了：");
    scanf("%d",&key);
    switch (key) {
    case 1:
      printf("何番目を追加しますか:");
      scanf("%d",&pos);
      addNewNodeToHead(&value, pos);
      break;
    case 2:
      printf("何番目を削除しますか:");
      scanf("%d",&pos);
      deleteFirstNode(pos,pos);
      break;
    default:
      break;
    }
  }
  while (list_head.next)
    deleteFirstNode(0,0);
  return 0;
}

/* end */