// A doubly-linked list API.

struct DList;  // the type of doubly-linked list headers
struct DLink;  // the type of link nodes in the doubly-linked list

// returns a new, empty doubly-linked list (constant time; post: res
// != NULL, first_link(res) == last_link(res) == NULL)
DList* new_dlist();

// return the first link of the doubly-linked list, or NULL if the
// list is empty (constant time; pre: dlist != NULL)
DLink* first_dlink(DList* dlist);
// return the last link of the doubly-linked list, or NULL if the
// list is empty (constant time; pre: dlist != NULL)
DLink* last_dlink(DList* dlist);

// return the data stored with the argument link (constant time; pre:
// dlink != NULL)
int get_data(DLink* dlink);

// return the next link of the doubly-linked list after the argument
// link, or NULL if this is the last link (constant time; pre: dlink
// != NULL)
DLink* next_dlink(DLink* dlink);
// return the previous link of the doubly-linked list before the
// argument link, or NULL if this is the first link (constant time;
// pre: dlink != NULL)
DLink* prev_dlink(DLink* dlink);

// add a new link holding data at the front of the doubly linked list,
// before any existing links in the list (constant time; pre: dlist !=
// NULL)
void add_before_first(DList* dlist, int data);
// add a new link holding data at the end of the doubly linked list,
// after any existing links in the list (constant time; pre: dlist !=
// NULL)
void add_after_last(DList* dlist, int data);

// create a new link holding data, insert it before the argument link
// in the doubly-linked list, and return the new link (constant time;
// pre: dlist != NULL && dlink != NULL && dlink is a link in dlist)
DLink* insert_before(DList* dlist, DLink* dlink, int data);
// create a new link holding data, insert it after the argument link
// in the doubly-linked list, and return the new link (constant time;
// pre: dlist != NULL && dlink != NULL && dlink is a link in dlist)
DLink* insert_after(DList* dlist, DLink* dlink, int data);

// remove the argument link from the given doubly-linked list and
// deallocate the link (constant time; pre: dlist != NULL && dlink !=
// NULL && dlink is a link in dlist)
void delete_dlink(DList* dlist, DLink* dlink);

// deallocate the list and all its links (pre: dlist != NULL)
void delete_dlist(DList* dlist);

// EXTRA CREDIT:
// return the first link in the list for which the argument predicate
// function returns true when called on the link's data, or NULL if no
// such link is found (pre: dlink != NULL && pred != NULL)
DLink* find(DList* dlist, bool (*pred)(int data));