[자료구조] 연결리스트(Linked List)

//연결리스트

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

typedef struct ListNode{
    int data;
    struct ListNode *link;
}ListNode;

//노드 생성 함수
ListNode* create_node(int data){
    ListNode* node;
    node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    node->link = NULL;
    
    return node;
}

//노드를 제일 앞에 삽입하는 함수
//삽입하는 노드가 head가 된다.
ListNode* insert_first(ListNode* head){
    int data;
    ListNode* new_node;
    
    printf("input data : ");
    scanf("%d", &data);
    
    new_node = create_node(data);
    
    if(head == NULL){
        head = new_node;
    }else{
        new_node->link = head;
        head = new_node;
    }
    
    return head;
}

//노드를 찾는 함수
ListNode* search_node(ListNode* head){
    int data;
    ListNode* pre_node = NULL;
    
    printf("which data do you search? ");
    scanf("%d", &data);
    
    //head가 NULL일 때
    if(head == NULL){
        return NULL;
    //찾는 data가 head일 때 head 리턴
    }else if(head->data == data){
        return head;
    }
    
    //data 찾기
    while(head->data != data && head->link != NULL){
        pre_node = head;
        head = head->link;
    }
    
    //찾는 데이터의 전 노드 리턴
    if(head->data == data){
        return pre_node;
    //찾는 데이터가 없을 때 NULL 리턴
    }else{
        return NULL;
    }
}

//노드 중간에 삽입하는 함수
ListNode* insert(ListNode* head){
    ListNode* pre_node;
    ListNode* new_node;
    ListNode* temp;
    int data;
    
    printf("input data : ");
    scanf("%d", &data);
    new_node = create_node(data);
    
    pre_node = search_node(head);
    
    //찾은 데이터가 head일 경우
    if(pre_node == head){
        new_node->link = head;
        return new_node;
    
    //찾는 데이터가 없을 경우 맨 뒤에 삽입
    }else if(pre_node == NULL){
        pre_node = head;
        while(pre_node != NULL){
            temp = pre_node;
            pre_node = pre_node->link;
        }
        temp->link = new_node;
        return head;
        
    //찾은 데이터가 있을 경우 찾은 데이터 뒤에 삽입
    }else{
        new_node->link = pre_node->link;
        pre_node->link = new_node;
        return head;
    }
}

//맨 앞 노드 삭제하는 함수
ListNode* delete_first(ListNode* head){
    ListNode* temp;
    
    if(head == NULL){
        return NULL;
    }
    
    temp = head;
    head = head->link;
    free(temp);
    
    return head;
}

//전체 노드를 출력하는 함수
void print_node(ListNode* head){
    while(head != NULL){
        printf("%d ", head->data);
        head = head->link;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    ListNode* head = NULL;
    ListNode* pre_node;
    int menu;
    
    do{
        printf("========================\n");
        printf("1.insert_first 2.insert\n3.delete_first 4.delete\n5.search 6.reverse\n7.print_node 8.end\n");
        printf("========================\n");
        printf("menu : ");
        scanf("%d", &menu);
        
        if(menu == 1){
            head = insert_first(head);
        }else if(menu == 2){
            head = insert(head);
        }else if(menu == 3){
            head = delete_first(head);
        }else if(menu == 4){
            //head = delete_node(head);
        }else if(menu == 5){
            pre_node = search_node(head);
            if(pre_node == NULL){
                printf("no data\n");
            }else{
                printf("data is %d\n", pre_node->data);
            }
        }else if(menu == 6){
            //reverse(head);
        }else if(menu == 7){
            print_node(head);
        }
    }while(menu != 8);
}