// linkedlist.h: header file,  ref in
//   linkedlist.c, stack.c, queue.c
void addlast(int );
void addfirst(int );
int removefirst();
void printlist();
void printreverse();
int empty();
// linkedlist.c:
#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"

struct listnode {
   int data;
   struct listnode* next;
};

static void printreverse0(struct listnode* );
static struct listnode* newlistnode(int );

struct listnode* first = NULL; // front, top
struct listnode* last = NULL;  // rear

static struct listnode* newlistnode(int dataitem) {
   struct listnode* newnode = (struct listnode*)
         malloc(sizeof(struct listnode));
   newnode -> data = dataitem;
}

void addlast(int dataitem) {
   // or add to rear, i.e. enqueue
   if (last == NULL) { // empty linked list
      last = newlistnode(dataitem);
      last -> next = NULL;
      first = last;
   }
   else { // case of non-empty linked list
      last -> next = newlistnode(dataitem);
      last = last -> next;
      last -> next = NULL;
   }
}

void addfirst(int dataitem) {
   // or add to front, i.e. dequeue, or push
   struct listnode* newnode = newlistnode(dataitem);
   newnode -> next = first;
   first = newnode;
   if (last == NULL)  // adding to empty list
      last = newnode;
}

int removefirst() {
   // or pop
   int valuetoreturn = first -> data;
   first = first -> next;
   if (first == NULL) last = NULL;
   return valuetoreturn;
}

int empty() {
   return first == NULL;
}

void printlist() {
   // first to last, or front to rear
   struct listnode* temp = first;
   if (temp == NULL) printf("Empty");
   while (temp != NULL) {
      printf("%i ", temp -> data);
      temp = temp -> next;
   }
   printf("\n");
}

void printreverse() {
   printreverse0(first);
   printf("\n");
}

static void printreverse0(struct listnode* temp){
   // last to first, or rear to front
   if (temp != NULL) {
      printreverse0(temp -> next);
      printf("%i ", temp -> data);
   }
   }
}

int delete(int dataItem) {
   // delete from anywhere in list
   if (first == NULL) return -1; // empty
   if (first == last) { // 1 item in list
      if (first -> data == dataItem) {
         first = last = NULL;
         return 0;
      }
      else return -1;
   }
   // >= 2 items in list
   if (first -> data == dataItem) {
      first = first -> next;
      return 0;
   }
   // >= 2 items, first not the one
   struct listnode* old = first;
   struct listnode* curr = first -> next;
   while (curr != NULL && curr -> data != dataItem) {
      curr = curr -> next;
      old = old -> next;
   }
   if (curr == NULL) return -1;
   // now found at curr
   if (curr == last) {
      last = old;
      last -> next = NULL;
      return 0;
   }
   old -> next = curr -> next;
   return 0;
}

// stack.h: header file,
void push(int );
int pop();
// stack.c: based on linkedlist.c
#include "linkedlist.h"
#include "stack.h"
void push(int dataItem) {
   addfirst(dataItem);
}
int pop() {
   return removefirst();
}
// queue.h: header file
void enqueue(int );
int dequeue();
// queue.c: based on linkedlist.c
#include "linkedlist.h"
#include "queue.h"
void enqueue(int dataitem) {
   addlast(dataitem);
}
int dequeue() {
   return removefirst();
}
// linkedlist0.h: header file
void printlist();
void printreverse();
int empty();
// linktest.c: test program.  Note:
//  can't use both stack and queue
#include <stdio.h>
#include "queue.h"
#include "stack.h"
#include "linkedlist0.h"

void main() {
   int a[] = {2, 3, 5, 7, 11, 13};
   int i, t;
   for (i = 0; i < 6; i++)
      enqueue(a[i]);
   printf("Queue:");
   printlist();
   printreverse();
   t = dequeue(); printf("%i ", t);
   t = dequeue(); printf("%i\n", t);
   // must empty queue to use stack
   while (!empty()) t = dequeue();

   for (i = 0; i < 6; i++)
      push(a[i]);
   printf("Stack:");
   printlist();
   printreverse();
   t = pop(); printf("%i ", t);
   t = pop(); printf("%i\n", t);
   push(11);
   push(13);
   
   printf("Delete test:\n");
   printlist();
   for (i = 5; i >= 0; i--) {
      delete(a[i]);
      printlist();
   }
   printf("2nd Delete test:\n");
   for (i = 0; i < 6; i++)
      push(a[i]);
   printlist();
   printf("%i ", delete(1));
   printf("%i ", delete(8));
   printf("%i\n", delete(15));
   printf("3rd Delete test:\n");
   for (i = 0; i < 6; i++) {
      delete(a[i]);
      printlist();
   }
}

Queue:
2 3 5 7 11 13 
13 11 7 5 3 2 
2 3
Stack:
13 11 7 5 3 2 
2 3 5 7 11 13
13 11
Delete test:
13 11 7 5 3 2 
11 7 5 3 2 
7 5 3 2 
5 3 2 
3 2 
2 

Empty
2nd Delete test:
13 11 7 5 3 2 
-1 -1 -1
3rd Delete test:
13 11 7 5 3 
13 11 7 5 
13 11 7 
13 11 
13 
Empty