/*
 * LinkedList
 * linc
 * 2013.2.26
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define OK 1  
#define ERROR -1  
#define TURE 1  
#define FALSE 0 

struct Node
{
	int data;
	struct Node *next;
};
typedef struct Node *Head;
typedef struct Node *LinkedList;

//create the linked list,head insert
void createList(LinkedList *list,int size,Head *head)
{
	/*
	*head = (Head)malloc(sizeof(struct Node));
	printf("head test0");
	(*head)->data = size;
	printf("head test1");
	//(*head)->next = (*list);
	printf("head test2");
	*/
	LinkedList tmpList;
	srand(time(0));
	*list = (LinkedList)malloc(sizeof(struct Node));
	(*list)->next = NULL;
	for(int i = 0; i < size; i++)
	{
		tmpList = (LinkedList)malloc(sizeof(struct Node));
		tmpList->data = rand()%100 + 1;
		tmpList->next = (*list)->next;
		(*list)->next = tmpList;
		printf("list->data %d is %d\n",i,tmpList->data);
	}
	//head node
	tmpList = (LinkedList)malloc(sizeof(struct Node));
	tmpList->data = size;
	tmpList->next = (*list)->next;
	(*list)->next =tmpList;

	/*
	while((*list) != NULL)
	{
		printf("data is %d\n",(*list)->data);
		(*list)->next;
	}
	*/

}
//get element of list
int getElement(LinkedList list,int index,int *element)
{
	printf("getElement\n");
	LinkedList tmpList = list->next;
	printf("getElement---test\n");
	int size = tmpList->data;//the list size
	printf("the size is %d\n",size);
	if(index > size)
	{
		return ERROR;
	}
	
	int count = 0;
	while(tmpList && count < index+1)//+1 for head node
	{
		printf("data is %d\n",tmpList->data);
		tmpList = tmpList->next;
		++count;
	}
	if(!tmpList)
		return ERROR;
	*element = tmpList->data;
	return OK;
}

//clear list
int clearList(LinkedList *list)
{
	//use 2 points free the list
	LinkedList tmpList1,tmpList2;
	tmpList1 = (*list)->next;
	while(tmpList1)
	{
		printf("free the data is %d\n",tmpList1->data);
		tmpList2 = tmpList1->next;
		free(tmpList1);
		tmpList1 = tmpList2;
	}
	(*list)->next = NULL;
	return OK;
}

//insert
//after index
int insert(LinkedList *list,int index,int element)
{
	printf("insert index is %d,element is %d\n",index,element);
	LinkedList tmpList = (*list)->next;
	int size = tmpList->data;
	if(index > size)
	{
		printf("ERROR:the index > size.\n");
		return ERROR;
	}
	int count = 0;
	while(tmpList && count < index+1)
	{
		tmpList = tmpList->next;
		++count;
	}
	if(!tmpList)
		return ERROR;
	LinkedList node = (LinkedList)malloc(sizeof(struct Node));
	node->data = element;
	node->next = tmpList->next;
	tmpList->next = node;
	return OK;
}
//delete
int delete(LinkedList *list,int index)
{
	printf("delete,index is %d\n",index);
	LinkedList tmpList = (*list)->next;
	int size = tmpList->data;
	if(index > size)
	{
		printf("ERROR:the index > size.\n");
		return ERROR;
	}
	int count = 0;
	while(tmpList && count < index+1)
	{
		tmpList = tmpList->next;
		++count;
	}
	if(!tmpList)
		return ERROR;
	LinkedList node = tmpList->next;
	tmpList->next = node->next;
	free(node);
	return OK;
}

int main()
{
	LinkedList *list;
	Head *head;
	createList(list,10,head);
	int i = 1;
	getElement(*list,5,&i);
	insert(list,5,20);
	printf("getElement is %d\n",i);
	getElement(*list,5,&i);
	printf("getElement is %d\n",i);
	delete(list,5);
	clearList(list);
	return 0;
}

链式存储结构的优点在于它在找到目标元素后，删除或者插入都十分方便，只需将指针挪动一次就好；缺点就是不能像顺序存储结构那样迅速的找到目标元素，只能笨笨的一个一个元素的遍历下去。