//05 Delete an element from a linked list
//only read "delete" function. The other functions are from example 04
// http://codepad.org/mSBjdVNy
//2011-06-18

#include <stdio.h>

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

int insert(element **head, int data){
	element *newHead = (element *) malloc(sizeof(element));
	if (!newHead) return 0; // memory allocation fails
	
	newHead->data = data;
	newHead->next = *head;
	*head = newHead;
	
	return 1; // success	
}

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

// return 1 if an element is deleted, otherwise return 0
// why use double pointer for head? because we need to change it, and we also 
// need to return a failure code.
int delete(element **head, element *deleteMe)
{
	// *head is the pointer to the head of the list
	if(!deleteMe) return 0;
	
	if (*head == deleteMe){
		// delete the head
		*head = deleteMe->next;
		free(deleteMe);
		return 1;
	}
	else{
		element *cursor = *head;
		while(cursor){
			if(cursor->next == deleteMe){
				cursor->next = deleteMe->next;
				free(deleteMe);
				return 1;				
			}
			cursor = cursor->next;					
		}
		return 0;
	}
	
}

//test
main()
{
	printf("Insert 1 to the head of the list\n");
	
	element *head = (element *) malloc(sizeof(element));
	if (!head) return 0; // memory allocation fails
	
	element *e1 = head; 
	head->data = 1;
	head->next = NULL;

	printf("Print the list: ");
	printList(head);
		
	printf("\nInsert 2,3 to the head of the list");
	insert(&head, 2);
	insert(&head, 3);
	
	printf("\nPrint the list: ");
	printList(head);

	printf("\nRemove 1 from the list");
	delete(&head, e1);
	
	printf("\nPrint the list: ");
	printList(head);

	printf("\nRemove head from the list");
	delete(&head, head);
	
	printf("\nPrint the list: ");
	printList(head);
	printf("\n");
	return 1;
}

Insert 1 to the head of the list
Print the list: 1 
Insert 2,3 to the head of the list
Print the list: 3 2 1 
Remove 1 from the list
Print the list: 3 2 
Remove head from the list
Print the list: 2