// 07 Maintain linkled list tail and head pointers
// 2011-06-18

#include <stdio.h>

typedef struct elementT{
	int data;
	struct elementT *next;
}element;

element *head = NULL, *tail = NULL;

// delete the element from the list
int Delete(element *elem){
	if(!elem) return 0;
	
	if (elem == head){
		head = head->next;
		delete elem;
		if (!head) tail = NULL; // if the list has only one element
		return 1;
	}
	
	element *cursor = head;	
	
	// why need the loop? if elem is not in the list, no deletion happens
	while(cursor){ 
		if (cursor->next == elem){
			cursor->next = elem->next;	
			delete elem;
			if (cursor->next == NULL){
				tail = cursor;
			}
			return 1;		
		}
		cursor = cursor->next;
	}
	
	// not found
	return 0;
}

// insert after the given element
// if elem is NULL, insert to the head of the list
int InsertAfter(element *elem, int data){
	element *newE = new element;	
	if (!newE) return 0;
	newE->data = data;
	
	if (elem == NULL){
		// empty head, insert newE as the only element
		newE->next= head;
		head = newE;
		if (newE->next== NULL){
			tail = newE;
		}
		return 1 ;
	}
	
	// insert after elem
	element *cursor = head;
	// why need the loop? if elem is not in the list, no insertion happens
	while(cursor){ 
		if (cursor == elem){
			newE->next = elem->next;
			elem->next= newE;	
			if (newE->next == NULL){
				tail = newE;
			}
			return 1;		
		}
		cursor = cursor->next;
	}
	
	// not insertion happens, free memory
	delete newE;
	return 0; 
}

// print the whole linked list
void printList(element *head){
	element *cursor = head;
	while (cursor){
		printf("%d ", cursor->data);
		cursor = cursor->next;
	}
}

int main(){
	InsertAfter(NULL,1);
	element *pos = head;
	InsertAfter(head,2);
	InsertAfter(pos,3);
	printList(head);
	
	printf("\nDelete tail\n");
	Delete(tail);
	printList(head);

	printf("\nDelete head\n");
	Delete(head);
	printList(head);
	
	return 1;
}

1 3 2 
Delete tail
1 3 
Delete head
3