# Data structure
## Single Link List

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	int data;
	struct node *next;
}NODE;//別名

NODE *createList(int*,int);
void printList(NODE*);
void freeList(NODE*);
NODE *searchNode(NODE*,int);
void insertNode(NODE*,int);

int main(void) {
	int array[]={4,5,20,8,9};
	NODE *first;
	NODE *node;
	first=createList(array,5);
	printList(first);

	
	node=searchNode(first,20);
	if(node!=NULL){
		insertNode(node,18);	
	}
	printList(first);
	freeList(first);
    system("PAUSE");
	return 0;
}
NODE *createList(int *array,int size){
	NODE *first,*current,*previous;
	int i;
	for(i=0;i<size;i++){
		current=(NODE*)malloc(sizeof(NODE));
		current->data=array[i];
		if(i==0){
			first=current;
		}else{
			previous->next=current;
		}
		current->next=NULL;
		previous=current;
	}
	return first;
};
void printList(NODE *first){
	NODE *print_node=first;
	if(first==NULL){
		printf("no value\n");
	}else{
		while(print_node!=NULL){
			printf("%3d",print_node->data);
			print_node=print_node->next;
		}
		printf("\n");
	}

};
void freeList(NODE *first){
	NODE *current,*temp;
	current=first;
	while(current!=NULL){
		temp=current;
		current=current->next;
		free(temp);
	}

};
NODE *searchNode(NODE *first,int target){
		NODE *current=first;
		while(current!=NULL){
			if(current->data==target){
				return current;
			}else{
				current=current->next;
			}
		}
		printf("not find\n");
		return NULL;
};
void insertNode(NODE *node,int insert){
	NODE *newnode;
	newnode=(NODE*)malloc(sizeof(NODE));
	newnode->data=insert;
	newnode->next=node->next;
	node->next=newnode;

};

## Double Link List

#include<stdio.h>
#include<stdlib.h>
//DLL
typedef struct node{
	int data;
	struct node *pre;
	struct node *next;
}NODE;
void append(NODE **head_ref,int new_data){
	//last node use to travel
	NODE *last=*head_ref;
	//allocate
	NODE *new_node=(NODE*)malloc(sizeof(NODE));
	//put data
	new_node->data=new_data;
	//point to NULL
	new_node->next=NULL;
	//if empty ，change head and pre point to NULL
	if(*head_ref==NULL){
		new_node->pre=NULL;
		*head_ref=new_node;
		return;//把head接上就可以結束了
	}
	//travel to last
	while(last->next!=NULL){
		last=last->next;
	}
	//new node add back last
	last->next=new_node;
	new_node->pre=last;
	return;
	
}
void push(NODE **head_ref,int new_data){
	//allocate
	NODE *new_node=(NODE*)malloc(sizeof(NODE));
	//put data
	new_node->data=new_data;
	//new node is first pre to NULL
	new_node->pre=NULL;
	new_node->next=*head_ref;
	//if have other node
	if(*head_ref!=NULL){
		(*head_ref)->pre=new_node;//一定要括弧
	}
	//head point to new node
	(*head_ref)=new_node;
}
void printList(NODE *node){
	if(node==NULL){
		printf(" empty\n");
		return;
	}
	//forward direction
	NODE *last=node;
	printf("forward direction:\n");
	while(last->next!=NULL){//最後一個值會沒讀到，會跳出迴圈
		printf("%d ",last->data);
		last=last->next;
	}
	printf("%d ",last->data);//印出最後一個值
	printf("\n");
	printf("backward direction:\n");
	while(last->pre!=NULL){
		printf("%d ",last->data);
		last=last->pre;
	}
	printf("%d ",last->data);
	printf("\n");
	
}

void deleteList(NODE **head_ref){
	NODE *current=*head_ref;
	NODE *next;
	
	//travel
	while(current!=NULL){
		next=current->next;
		free(current);
		current=next;
	}
	*head_ref=NULL;
};

int main()
{	
	NODE *head=NULL;
	
	append(&head,9);
	
	push(&head,3);
	push(&head,7);
	push(&head,10);
	push(&head,8);
	
	printList(head);
	
	deleteList(&head);
	printList(head);

return 0;
}

## Stack in SLL

#include<stdio.h> 
#include<stdlib.h> 

typedef struct node{
	int data;
	struct node *next;
}NODE;
NODE *newNode(int key){
	NODE *node=(NODE*)malloc(sizeof(NODE));
	node->next=NULL;
	node->data=key;
	return node;
}
void push(NODE **top_ref,int key){
	NODE *node=newNode(key);
	//node before head
	node->next=(*top_ref);
	//head is node
	(*top_ref)=node;
}
void Top(NODE *top){
	printf("%d\n",top->data);
}

void Pop(NODE **top_ref){
	if (*top_ref == NULL) 
      return; 
      
	NODE *current=(*top_ref);
	(*top_ref)=current->next;
	free(current);
	return;
}

void printStack(NODE *top){
	NODE *curr=top;
	while(curr!=NULL){
		printf("%d",curr->data);
		curr=curr->next;
	}
	printf("\n");
}
int empty(NODE *top){
	return (top==NULL);
}
int size(NODE *top){
	int cnt=0;
	while(top){
		cnt++;
		top=top->next;
	}
	return cnt;
}
int main() 
{
	NODE *top=NULL;
	
	push(&top,3);
	push(&top,2);
	push(&top,1);
	printStack(top);
	Top(top);
	
	Pop(&top);//don't forget &
	printStack(top);

	printf("size:%d\n",size(top));
	empty(top)?printf("Empty"):printf("Have value");
    return 0;
} 

## Queue in SLL

#include<stdio.h> 
#include<stdlib.h> 

typedef struct node{
	int data;
	struct node *next;
}NODE;
//use for point to front and rear
typedef struct queue{
	NODE *front,*rear;
}Queue;

Queue *newQueue(){
	//initilize Queue
	Queue *q=(Queue*)malloc(sizeof(Queue));
	q->front=NULL;
	q->rear=NULL;
	return q;
}
NODE *newNode(int key){
	NODE *node=(NODE*)malloc(sizeof(NODE));
	node->next=NULL;
	node->data=key;
	return node;
}
void enQueue(Queue *q,int key){
	NODE *node=newNode(key);
	//no node in queue
	if(q->rear==NULL){
		q->front=node;
		q->rear=node;
	}
	//the last have node，point to the next	
	q->rear->next=node;
	//change rear
	q->rear=node;
	
}


void deQueue(Queue *q){
	//no node
	if (q->front == NULL) 
      return; 
    //create temp
    NODE *temp=q->front;
    //change front
	q->front=q->front->next;
	//free
	free(temp);
	
}

void front(Queue *q){
	if(q==NULL)
		return;
	printf("%d\n",q->front->data);
}
void rear(Queue *q){
	if(q==NULL)
		return;
	printf("%d\n",q->rear->data);
}

void printQueue(Queue *q){
	NODE *curr=q->front;
	while(curr!=NULL){
		printf("%d",curr->data);
		curr=curr->next;
	}
	printf("\n");
}
int main() 
{
	Queue *q=newQueue();
	
	enQueue(q,1);
	enQueue(q,2);
	enQueue(q,3);
	printQueue(q);
	front(q);
	rear(q);
	
	deQueue(q);
	printQueue(q);

    return 0;
}