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

// Node of a list
typedef struct NodeT {
  int            data;
  struct NodeT * next;
} Node;

// List with a pointer to the first (head) and the last (foot)
// element of the list
typedef struct ListT {
  Node * head;
  Node * foot;
} List;


// create a new list and return the pointer to the list
List * makeNewList ();


// insert a new item at the head of the list
void insertAtHead (List *list, int newItem);

// free list: free every node and the list structure itself
void freeList (List *list); 

// pretty print list
void printList (List *list);
           
int lengthOfList (List *list);


int main (int argc, char ** argv) {
  // simple test of some of the list functions
  List *list = makeNewList();
  insertAtHead (list, 5); 
  insertAtHead (list, 4);
  insertAtHead (list, 3); 
  insertAtHead (list, 2);
  insertAtHead (list, 1);  
  printList (list);
  lengthOfList (list);
  freeList (list);
  return (0);

}


List * makeNewList () {
  // allocate space for the List struct
  List * l = (List*) malloc (sizeof(List));
  // check if assert was succesfull
  assert (l); 
  // list is empty, so head and foot don't point to a node yet
  l->head = NULL;
  l->foot = NULL;
  // return the list pointer
  return (l);
}


void insertAtHead (List *list, int newItem) {
  // allocate space for the new node struct
  Node * node = (Node *) malloc (sizeof(Node));
  // check if assert was succesfull
  assert (node);
  // initialise data field of the node
  node->data = newItem; 
  // make sure the list pointer is not NULL
  assert (list);
  // let node point to first node in list
  node->next = list->head; 
  // the new head of the list is the new node
  list->head = node;
  // if list was empty, foot is still NULL, and 
  // head and foot should point to the same node
  // since the list has only one element now
  if (list->foot == NULL) {
    list->foot = node; 
  }
}

void freeList (List *list) {
   int copyNode;
   Node *currentNode;
   assert(list);
   currentNode = list->head;
   while (currentNode) {
      copyNode = currentNode;
      currentNode = currentNode->next;
      free (currentNode);
      currentNode = copyNode;
   }

  // free the list struct and all the nodes in the list
  // implement as an exercise. Similar to printList, but
  // make sure you never free a node when you still need to
  // access information from the node. I.e.
  // free (node);
  // currentNode = node->next;
  // is *not* ok, you can't derefence 'node' after calling free,

}


void printList (List *list) {
  Node *currentNode;
  // make sure list is not NULL
  assert (list);
  // keep track of the current node we're printing
  currentNode = list->head;
  printf ("{");
  while (currentNode) {
    // print data of current node
    printf ("%d", currentNode->data);
    // move currentNode to the next node
    currentNode = currentNode->next;
    // printf ',' only if this was not the last node
    if (currentNode) {
      printf (", ");
    }
  }
  printf ("}\n");  

}

int lengthOfList (List *list) {
   Node *currentNode;
   assert(list);
   currentNode = list->head;
   int counter=0;
   while (currentNode) {
      counter++;
      currentNode = currentNode->next;
   }
   printf ("The list is of length: %d",counter);
return (0);
}