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

struct node {
  int data;
  struct node *prev, *next;
};
struct node *head = NULL;
struct node *tail = NULL;

void display() {
  if (head == NULL) {
    printf("\nList is empty\n");
    return;
  }
  struct node *temp;
  temp = head;
  while (temp != NULL) {
    printf("Data = %d\n", temp->data);
    temp = temp->next;
  }
}

void deleteFirst() {
  struct node *temp;
  if (head == NULL)
    printf("\nList is empty\n");
  else {
    temp = head;
    head = head->next;
    if (head != NULL)
      head->prev = NULL;
    free(temp);
  }
}

void deleteEnd() {
  struct node *temp;
  if (head == NULL)
    printf("\nList is empty\n");
  temp = head;
  while (temp->next != NULL)
    temp = temp->next;
  if (head->next == NULL)
    head = NULL;
  else {
    temp->prev->next = NULL;
    free(temp);
  }
}

void deletePosition() {
  int pos, i = 1;
  struct node *temp, *position;
  temp = head;

  if (head == NULL)
    printf("\nList is empty\n");

  else {

    printf("\nEnter position : ");
    scanf("%d", &pos);

    if (pos == 1) {
      deleteFirst();
      if (head != NULL) {
        head->prev = NULL;
      }
      free(position);
      return;
    }

    while (i < pos - 1) {
      temp = temp->next;
      i++;
    }

    position = temp->next;
    if (position->next != NULL)
      position->next->prev = temp;
    temp->next = position->next;

    free(position);
  }
}

int main() {
  int n, i, nodeNum, choice;

  printf("Enter the number of nodes: ");
  scanf("%d", &n);

  for (i = 1; i <= n; i++) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    printf("Enter the data for node %d: ", i);
    scanf("%d", &new_node->data);

    new_node->next = NULL;
    new_node->prev = tail;
    if (tail == NULL) {
      head = new_node;
    } else {
      tail->next = new_node;
    }
    tail = new_node;
  }

  printf("The original linked list is:\n");
  struct node *currNode = head;
  while (currNode != NULL) {
    printf("%d <-> ", currNode->data);
    currNode = currNode->next;
  }
  printf("NULL\n");

  while (1) {

    printf("\n1.Delete at beginning\n2.Delete in middle\n3.Delete at "
           "end\n4.Exit\nEnter your choice: ");
    scanf("%d", &choice);

    switch (choice) {

    case 1:
      deleteFirst();
      display();
      break;
    case 2:
      deletePosition();
      display();
      break;
    case 3:
      deleteEnd();
      display();

      break;

    case 8:
      exit(1);
      break;
    default:
      printf("Invalid Choice \n");
    }
  }
  return 0;
}