#define LINKED_LIST

struct listElement {
  void * data;
  struct listElement *next;
  struct listElement *previous;
};

typedef struct listElement LISTEL;

LISTEL * insertBefore(void *theData, LISTEL *place)
{
  LISTEL * element = malloc(sizeof(LISTEL));
  element->data = theData;
  if(place->previous == NULL)
    {
      element->next = place;
      place->previous = element;
    }
  else
    {
      LISTEL * previous = place->previous;
      previous->next = element;
      element->previous = previous;
      place->previous = place;
      element->next = place;
    }
  
  return element;
}

LISTEL * insertAfter(void *theData, LISTEL *place)
{
  LISTEL * element = malloc(sizeof(LISTEL));
  element->data = theData;
  if(place->next == NULL)
    {
      element->previous = place;
      place->next = element;
    }
  else
    {
      LISTEL * next = place->next;
      next->previous = element;
      element->next = next;
      place->next = element;
      element->previous = place;
    }
  return element;
}

LISTEL * circularizeList(LISTEL *start)
{
  LISTEL *tail = start;
  while (tail->next != NULL)
    tail = tail->next;
  start->previous = tail;
  tail->next = start;
  return start;
}

void * removeElement(LISTEL *remove)
{
  LISTEL *before = remove->previous;
  LISTEL *after = remove->next;
  void * value = remove->data;
  before->next = after;
  after->previous = before;
  free(remove);
  return value;
}