#define TRUE 0
#define FALSE 1
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct item{
  int val;
  struct item *right;
  struct item *left;
} Item;

Item *lastItem(Item *parent)
{
  Item *prev, *curr;
  prev = curr = parent;
  while( curr ) {
    prev = curr;
    curr = curr->right;
  }
  return prev;
}

Item *firstItem(Item *parent)
{
  Item *prev, *curr;
  prev = curr = parent;
  while( curr ) {
    prev = curr;
    curr = curr->left;
  }
  return prev;
}

Item *find(Item *list, int val)
{
  Item *ptr;
  ptr = firstItem(list);
  while( ptr ){
    if(ptr->val == val)
      return ptr;
    ptr = ptr->right;
  }
  printf("Not in list\n");
  return list;
}


Item *append(Item *parent, int val)
{
  Item *ptr, *last;

  if(parent == NULL){
    parent = (Item *) malloc(sizeof(Item));
    parent->val = val;
    parent->left = NULL;
    return(parent);
  }
  else{
    ptr = (Item *) malloc(sizeof(Item));
    last = lastItem(parent);
    last->right = ptr;
    ptr->left = last;
    ptr->val = val;
    return ptr;
  }
}
Item *insert(Item *parent, int val)
{
  Item *ptr;

  if(parent == NULL){
    parent = (Item *) malloc(sizeof(Item));
    parent->val = val;
    parent->left = NULL;
    return(parent);
  }
  else{
    ptr = (Item *) malloc(sizeof(Item));
    ptr->right = parent->right;
    ptr->left = parent;
    ptr->val = val;
    (parent->right)->left = ptr;
    parent->right = ptr;
    return ptr;
  }
}
Item *delete(Item *parent, int val)
{
  Item *ptr;

  if(parent == NULL){
    return(parent);
  }
  else{
    parent = find(parent, val);
    ptr = parent->right;
    (parent->left)->right = ptr;
    ptr->left = parent->left;
    free(parent);
    return ptr;
  }
}

void listPrint(Item *list)
{
  if( list != NULL) {
    listPrint(list->left);
    printf("%i -> ", list->val);
  }
  else
    printf("\n");
}

main()
{
  Item *list = NULL;
  
  list = append(list, 1);
  list = append(list, 2);
  list = append(list, 3);
  list = append(list, 4);

  list = find(list, 2);
  list = insert(list, 4);
  list = insert(list, 14);
  list = insert(list, 14);
  list = append(list, 40);
  list = delete(list, 3);

  listPrint(lastItem(list));

}