A doubly-linked list is a collection of nodes, each of which has a
pointer to the node before it and the node after it (as opposed to a
singly linked list, where each node only has a pointer to its
successor).  We can use the following structure to represent a node in
a doubly-linked list of integers:

struct node {
  int val;
  struct node *next;
  struct node *prev;
};

The list itself can be represented by a structure that keeps track of
the first node and the last node in the list:

struct list {
  struct node *first;
  struct node *last;
}

Your assignment is to implement the following functions:

/* Create an empty list.
   Return a pointer to the empty list, or NULL on failure. */
struct list *create_list();

/* Free up memory used by list and nodes in it */
void delete_list(struct list *l);

/* Insert value in the beginning of a list.
   Return 0 on failure and 1 on success. */ 
int insert_start(struct list *l, int val);

/* Insert value in the end of a list.
   Return 0 on failure and 1 on success. */ 
int insert_end(struct list *l, int val);

/* Create a node with value val and put it in the list after node n.
   Return 0 on failure and 1 on success. */
int insert_after(struct list *l, struct node *n, int val);

/* Create a node with value val and put it in the list before node n.
   Return 0 on failure and 1 on success. */
int insert_before(struct list *l, struct node *n, int val);

/* Delete node n from the list. 
   The other nodes should remain in their old relative order. */
void delete_node(struct list *l, struct node *n);

/* Check if there is a node with value val.
   Return 1 if val is in the list, 0 otherwise. */
int check_val(struct list *l, int val);

All functions except for delete_list and check_val should run in
an amount of time independent of the length of the list.