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

/*
 * Linked List Tutorial v1.0 22/1009
 *
 * Nick Giles
 * http://www.4pmp.com/
 *
 * Please let me know of any comments or corrections
 */

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


/**
 * Remove the first item in the list
 *
 */
int shift(struct node **head, int *p)
{
    struct node *firstNode;
  
    firstNode = *head;

    /* See if there is a first node */
    if (firstNode == NULL)
    {
        /* There isn't, so return -1*/
        return -1;
    }
     
    /* Set the passed pointer, the pointer to the first node in the list, to the next node */
    *head = firstNode->next;
    
    /* Get the value from the first node before we free() it */
    *p = firstNode->val;
    
    /* Deallocate the first node */
    free(firstNode);
    
    /* Return 0, all ok */
    return 0;
}


/**
 * Remove the last item and return the value
 *
 */
int pop (struct node **item, int *p)
{
    struct node *current;
    
    current = *item;
    
    if (current)
    {
        /* See if the current item specifies a proceding item */
        if (current->next)
        {
            /* There is a next item, so see if it is the last one */
            if (current->next->next == NULL)
            {
                /* The next item is the last one, so get its value */
                *p = current->next->val;
                
                /* Free the memory reserved for the last item */
                free(current->next);
                
                /* Remove the pointer to the last item */
                current->next = NULL;
                
                return 0;
            }
            
            /* Move on to the next item */
            return pop(&current->next, p);
        }
        
        /* There aren't any more items, this is the last one and therefore also the first */
        *p = current->val;
        
        /* Release the memory reserved for it */
        free(*item);
        
        /* Set the head node to NULL */
        *item = NULL;
        
        return 0;
    }
    
    /* There are no items in the list */
    p = NULL;
    
    return -1;
}

/**
 * Add a node onto the beginning of the list
 *
 */
void unshift(struct node** head, int data)
{
    /* Declare and reserve memory for the new item */
    struct node* newNode = malloc(sizeof(struct node));
    
    /* Se the new node's value */
    newNode->val = data;
    
    /* Set the next item to be the item that was previously first */
    newNode->next = *head;
    
    /* Set the pointer to the first item to this new item */
    *head = newNode;
}

/**
 * Adds a node onto the end of the list
 *
 */
void push(struct node** item, int data)
{
    struct node *current;
    struct node *endItem;
    
    current = *item;
    
    /* See if the passed value is a node */
    if (current)
    {
        /* See if this is the last node in the list */
        if (current->next == NULL)
        {
            /* This is the last item, so create a new node to go on the end */
            
            /* Allocate memory for the new node */
            endItem = malloc(sizeof(struct node));
            
            /* Set the value */
            endItem->val = data;
            
            /* Set the pointer to the next item to be NULL (there isn't a next, this will be the last item) */
            endItem->next  = NULL;
            
            /* Set the next pointer in the last item to the new item, making the new item now the last one */
            current->next = endItem;
            
            return;
        }
        else
        {
            /* This is not the last item, recurse to the next one */
            return push(&current->next, data);
        }
    }
    
    /* There are no nodes in the list, so create a new node and it will be the first in the list */
    endItem = malloc(sizeof(struct node));
    
    /* Set the value */
    endItem->val = data;
    
    /* Set the pointer to the next item to be NULL (there isn't a next, this will be the last item) */
    endItem->next  = NULL;
    
    /* Set the passed pointer to point to the new node */
    *item = endItem;
}


int main()
{
    struct node *head;
    int i, j;

    head = NULL;
    
    while (1)
    {
    
        for (i=1;i<6;i++)
        {
            /* Add to the beginning */
            unshift(&head, i);
            printf("Unshift: %d\n", i);
        }
        
        for (i=6;i<11;i++)
        {
            /* Add to the end */
            push(&head, i);
            printf("Push: %d\n", i);
        }
        
        for (i=1;i<6;i++)
        {
            /* Remove from the end */
            if (pop(&head, &j) == 0)
            {
                printf("Pop: %d\n", j);
            }
        }
        
        for (i=1;i<6;i++)
        {
            /* Remove from the beginning */
            if (shift(&head, &j) == 0)
            {
                printf("Shift: %d\n", j);
            }
        }
        
        /* Functions in a different order */
        
        for (i=1;i<6;i++)
        {
            /* Add to the end */
            push(&head, i);
            printf("Push: %d\n", i);
        }

        for (i=6;i<11;i++)
        {
            /* Add to the beginning */
            unshift(&head, i);
            printf("Unshift: %d\n", i);
        }

        
        for (i=1;i<6;i++)
        {
            /* Remove from the beginning */
            if (shift(&head, &j) == 0)
            {
                printf("Shift: %d\n", j);
            }
        }

        for (i=1;i<6;i++)
        {
            /* Remove from the end */
            if (pop(&head, &j) == 0)
            {
                printf("Pop: %d\n", j);
            }
        }
    }
    
    return 0;    
}