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

typedef enum { FAIL, SUCCESS } Status;
typedef int ElemType;
typedef struct node {
  ElemType value;
  struct node *prev, *next;
} Node, DoubleLinkedList;

/* initialize a double linked list */
Status double_linked_list_init(DoubleLinkedList* dlist) {
  // use head node's value to store list length
  dlist->value = 0;
  dlist->prev = dlist->next = dlist;
  return SUCCESS;
}

/* insert a node into the double linked list at the given index */
Status double_linked_list_insert(DoubleLinkedList* dlist, int index,
                                 ElemType value) {
  // index out of range
  if (index < 0 || index > dlist->value) return FAIL;
  Node *predecessor = dlist, *current = (Node*)malloc(sizeof(Node));
  // find the predecessor node
  while (index--) predecessor = predecessor->next;
  // insert the current node
  current->value = value;
  current->next = predecessor->next;
  predecessor->next->prev = current;
  current->prev = predecessor;
  predecessor->next = current;
  dlist->value++;
  return SUCCESS;
}

/* delete a node from the double linked list at the give index */
Status double_linked_list_delete(DoubleLinkedList* dlist, int index) {
  if (index < 0 || index >= dlist->value) return FAIL;
  Node *predecessor = dlist, *current = NULL;
  // find the predecessor node
  while (index--) predecessor = predecessor->next;
  // delete the current node
  current = predecessor->next;
  predecessor->next = current->next;
  current->next->prev = predecessor;
  free(current);
  dlist->value--;
  return SUCCESS;
}

int main() {
  DoubleLinkedList dlist;
  double_linked_list_init(&dlist);
  int i;
  // test list insert operation
  for (i = 0; i < 5; i++)
    double_linked_list_insert(&dlist, dlist.value, i);
  // test list delete operation
  double_linked_list_delete(&dlist, 2);
  Node *current = dlist.next;
  // test list forward iteration
  for (i = 0; i < dlist.value; i++, current = current->next)
    printf("%d ", current->value);
  current = current->prev;
  // test list backward iteration
  for (i = 0; i < dlist.value; i++, current = current->prev)
    printf("%d ", current->value);
  return 0;
}