#include <stdio.h>
#include <stdlib.h>
/* self-referential structure */
struct Node
{
  int *items;
  int lindx, rindx;
  struct Node *next;
};

struct List
{
  int ncap;
  struct Node *head;
  struct Node *tail;
};

struct List SLL_new(int cap)
{
  /* construct an empty list */
  struct List list;
  list.ncap = cap;
  list.head = NULL;
  list.tail = NULL;
  return list;
}

struct Node *Node_new(int cap, int lft, int rgt)
{
  struct Node *node = malloc(sizeof(struct Node));
  node->items = malloc(sizeof(int) * cap);
  node->rindx = rgt;
  node->lindx = lft;
  node->next = NULL;
  return node;
}

int SLL_length(struct List *list)
{
  /* return the number of items in the list */
  struct Node *p;
  int n = 0;
  for (p = list->head; p != NULL; p = p->next)
  {
    n += p->rindx - p->rindx;
  }
  return n;
}

int SLL_empty(struct List *list)
{
  /* return true if the list contains no items */
  return list->head == NULL;
}

int SLL_contains(struct List *list, int item)
{
  int i;
  /* return true if the list contains the item */
  struct Node *p;
  for (p = list->head; p != NULL; p = p->next)
    for (i = p->lindx; i < p->rindx; i++)
      if (p->items[i] == item)
        break;
  return p != NULL;
}

int SLL_pop(struct List *list)
{
  int item = 0;
  /* remove and return the first item of the list */
  struct Node *node = list->head;
  item = node->items[node->lindx];
  node->lindx++;

  if (node->lindx > node->rindx)
  {
    list->head = node->next;
    free(node);
  }

  if (SLL_empty(list))
  {
    list->tail = NULL;
  }

  return item;
}

void SLL_push(struct List *list, int item)
{
  struct Node *node = list->head;

  /* insert the item at the front of the list */
  if (SLL_empty(list) || node->lindx == 0)
  {
    node = Node_new(list->ncap, list->ncap, list->ncap - 1);
    node->next = list->head;
    if (SLL_empty(list))
    {
      list->tail = node;
    }
    list->head = node;
  }

  node->lindx--;
  node->items[node->lindx] = item;

  if (SLL_empty(list))
  {
    list->tail = node;
  }

  list->head = node;
}

void SLL_append(struct List *list, int item)
{
  struct Node *node = list->tail;

  /* append the item to the end of the list */
  if (SLL_empty(list))
  {
    SLL_push(list, item);
  }
  else
  {
    if (node->rindx == list->ncap - 1)
    {
      node = Node_new(list->ncap, 0, -1);
      list->tail->next = node;
      list->tail = node;
    }

    node->rindx++;
    node->items[node->rindx] = item;
  }
}

int main()
{
  int i;
  struct List list = SLL_new(3);
  for (i = 1; i < 12; ++i)
  {
    SLL_push(&list, i);
    SLL_append(&list, i);
  }
  while (!SLL_empty(&list))
  {
    printf("%d ", SLL_pop(&list));
  }
  printf("\n");
  return 0;
}