[자료구조] 단일연결리스트 c

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

#pragma warning (disable : 4996)

typedef struct node
{
    //노드 : 값 저장 단위
    //노드 = 값(vaule) + 다음 노드 주소(next)
    int value;
    struct node* next; //8바이트 : 주소를 저장하는 변수
}node;

//struct node* head;
node* head = NULL; //8바이트 : 주소를 저장하는 변수 //전역변수 : 프로그램 실행 ~ 종료 // 어디서든 접근 가능한 변수

void insertFrontNode(int data);
void displayNode(void);
void removeFrontNode(void);
void removeAllNode(void);
int getNodeCount(void);
node* searchNode(int target);
void removeTailNode(void);
int removeTarget(int target);
int removekthNode(int k);
void insertTailNode(int data);
node* createNode(int data);
void insertKthNode(int data, int k);
void insertSortedNode(int data);

int main(void)
{
    while (1) // 무한 루프
    {
        system("clear"); // 화면 지우기 system("cls");

        printf("\n\n\t *** 단일 연결 리스트(Singly Linked List)\n\n");
        printf("=======================================================\n");
        printf("1. 맨 앞 삽입\n"); //LIFO last in first out | O(1)
        printf("2. 맨 뒤 삽입\n"); //FIFO first in first out | O(N)
        printf("3. 앞에서부터 N번째 삽입\n");
        printf("4. 오름차순 정렬 삽입\n");
        printf("=======================================================\n");
        printf("5. 맨 앞 삭제\n");
        printf("6. 맨 뒤 삭제\n");
        printf("7. 전체 노드 삭제\n");
        printf("8. 특정 값 삭제\n");
        printf("9. 앞에서부터 N번째 삭제\n");
        printf("=======================================================\n");
        printf("10. 단일 연결 리스트 출력(노드 순회)\n");
        printf("11. 노드의 개수 구하기\n");
        printf("12. 노드 검색\n");
        printf(" 0. 프로그램 종료\n");
        printf("=======================================================\n");
        printf("\n메뉴 선택: ");
        int choice;
        scanf("%d", &choice);

        int data, k;

        switch (choice)
        {
        case 1:
            printf("\n\n정수 입력: ");
            scanf("%d", &data);

            insertFrontNode(data);
            break;
        case 2:
            printf("\n\n삽입할 정수 입력: ");
            scanf("%d", &data);
   
            insertTailNode(data);

            break;
        case 3:
            printf("\n\n삽입할 정수 입력: ");
            scanf("%d", &data);
            printf("몇 번째 삽입하시겠습니까? ");
            scanf("%d", &k);
            insertKthNode(data, k);
            break;
        case 4:
            printf("\n\n삽입할 정수 입력: ");
            scanf("%d", &data);
            insertSortedNode(data);
            break;
        case 5:
            removeFrontNode();
            break;
        case 6:
            removeTailNode();
            break;
        case 7:
            removeAllNode();
            break;
        case 8:
            printf("\n\n삭제할 정수 입력: ");
            scanf("%d", &data);

            //removeTarget함수 : 삭제 성공1, 삭제 실패 0
            if(removeTarget(data))
            {
                printf("\n\n\t\t삭제를 성공했습니다.\n");
            }
            else
            {
                printf("\n\n\t\t삭제를 실패했습니다.\n");
            }
            break;
        case 9:
        	printf("\n\n몇 번째 노드를 삭제하시겠습니꺼? ");
            scanf("%d", &data);

            //removekthNode함수 : 삭제 성공 1, 삭제 실패 0
            if (removekthNode(data))
            {
                printf("\n\n\t\t삭제를 성공했습니다.\n");
            }
            else
            {
                printf("\n\n\t\t삭제를 실패했습니다.\n");
            }
            break;
        case 10:
            displayNode();
            break;
        case 11:
            //getNodeCount함수 : 생성된 노드의 개수를 구해 리턴하는 함수
            printf("\n\n\t\t생성된 노드의 개수는 %d개 입니다.\n", getNodeCount());
            break;
        case 12:
            printf("\n\n검색할 정수 입력: ");
            scanf("%d", &data);

            //searchNode: 검색한 정수가 있으면 노드의 주소를 리턴, 없으면 NULL을 리턴
            if (searchNode(data) == NULL)
            {
                printf("\n\n\t\t검색한 노드는 존재하지 않습니다.\n");
            }
            else
            {
                printf("\n\n\t\t검색한 노드는 존재합니다.");
            }

            break;
        case 0:
            removeAllNode();
            return 0; // 프로그램 종료
        }

        printf("\n\n\t\t");
        system("read"); // 일시 정지 //system("pause");

    }
    return 0;
}
//O(1) : 상수 시간의 복잡도 : 생성된 노드의 개수와 상관없이 항상 일정한 스탭으로 명령 수행
void insertFrontNode(int data)
{
    node* newNode = createNode(data);

    if (head == NULL)
    {
        head = newNode;
        printf("\n\n\t\t노드 삽입(첫 노드로 연결)\n");
        return;
    }


    /* node* newNode; //8바이트 : 새 노드의 주소를 저장하는 변수
    newNode = (node*)malloc(sizeof(node)); //구조체 변수(노드) 생성
    newNode->value = data;
    newNode->next = NULL;

    if(head == NULL) // 아직 연결리스트가 구성 되기 전
    {
        head = newNode;
        printf("\n\n\t\t노드 맨 앞 삽입(첫 노드로 연결)\n");
        return; //호출한 곳으로 돌아간다. //함수의 종료
    }
    */

    newNode->next = head;
    head = newNode;
    printf("\n\n\t\t노드 맨 앞 삽입(일반적인 경우)\n");

}

//O(N) : 선형시간 복잡도 : 노드의 개수만큼 반복하기 때문에 노드의 개수에 따라 스탭이 결정된다. 
void displayNode(void)
{
    node* curNode = head; //currentNode, 각 노드를 방문하는 포인터 변수

    if(head == NULL)
    {
        printf("\n\n\t\t 연결 리스트가 구성되지 않아 출력할 데이터가 없습니다.");
        return;
    }

    printf("\n\nSingly Linked List: ");
    while (curNode->next != NULL) //마지막 노드는 포함되지 않는다.
    {
        printf("%d -> ", curNode->value);
       curNode = curNode->next;
    }
    printf("%d\n", curNode->value);
    /*
     printf("%d -> ", curNode->value); //5
    curNode = curNode->next;

    printf("%d -> ", curNode->value); //4
    curNode = curNode->next;*/  //너무 많이 각각 써야함..반복문으로 해야 편함

}

//O(1)
void removeFrontNode(void)
{
    node* delNode = head;

    if (head == NULL)
    {
        printf("\n\n\t\t연결 리스트가 구성되지 않아 삭제할 데이터가 없습니다.");
        return;
    }

    head = head->next;
    free(delNode); //첫 노드 제거
    printf("\n\n\t\t첫 노드를 제거했습니다.\n");
}

void removeAllNode(void)
{
    node* delNode;

    if(head == NULL)
    {
        printf("\n\n\t\t연결 리스트가 구성 되지 않아 삭제할 데이터가 없습니다.");
        return; //return 안쓰면 else를 이용하여 코드를 더 길게 사용하게 된다..
    }
    while(head != NULL)
    {
        delNode = head;
        head = head->next;
        free(delNode);
    }

    printf("\n\n\t\t모든 노드를 제거했습니다.");
}

int getNodeCount(void)
{
    if(head == 0) //연결리스트가 구성 되지 않는 경우 노드의 개수는 0개
        return 0;

    int count = 0; //노드의 개수
    node* curNode = head; //방문 노드를 첫 노드로 설정

    //방법2: 방문한 노드가 있다면 반복 -> 마지막 노드까지 순회
    while (curNode != NULL)
    {
        ++count;
        curNode = curNode->next;
    }

    return count;

    /*
     *방법1: 다음 노드가 존재하는 경우 반복 -> 마지막 노드는 포함되자 않는다.
    while (curNode->next != NULL)
    {
        ++count;
        curNode = curNode->next;
    }

    return count + 1;
    */
}

//O(N)
node* searchNode(int target)
{
    if (head == NULL)
        return NULL;

    node* curNode = head; //첫 노드부터 순회

    while (curNode != NULL) //방문노드가 있다면?
    {
        if(target == curNode->value) //찾는 값이야?
        {
            return curNode; //찾는 값의 노드의 주소를 리턴
        }
        curNode = curNode->next;
    }

    return NULL; //찾는 값이 없는 경우
}


//O(N)
void removeTailNode(void)
{
    if (head == NULL)
    {
        printf("\n\n\t\tcase1.연결 리스트가 구성되지 않아 삭제할 데이터가 없습니다.");
        return;
    }

    // case2. 노드가 한 개인 경우 => head에 저장된 값이 변경되기 때문이다.
    if (head->next == NULL)
    {
        free(head);
        head = NULL;
        printf("\n\n\t\tcase2. 노드가 한 개인 경우 제거\n");
        return;
    }

    node* curNode = head;
    while (curNode->next->next != NULL)
    {
        curNode = curNode->next;
    }

    free(curNode->next);
    curNode->next = NULL;
    printf("\n\n\t\tcase3. 마지막 노드를 제거\n");
}


int removeTarget(int target)
{
    if (head == NULL)
    {
        return 0; //삭제 실패
    }

    node* delNode;
    node* prevNode;

    //삭제할 노드가 첫 노드인 경우? => head 값이 변경되기 떄문이다.
    if(head->value == target)
    {
        delNode = head;
        head = head->next; //다음 노드로 head변경
        free(delNode);
        printf("\n\n\t\tcase1. 삭제할 노드가 첫 노드인 경우 제거\n");
        return 1; //삭제 성공
    }

    ////순회하면서 삭제할 데이터 찾아라!
    prevNode = delNode = head;

    while(delNode->next != NULL)// 삭제할 노드의 다음이 있다면?
    {
        delNode = delNode->next;

        if(delNode->value == target) //삭제할 값이야?
        {
            prevNode->next = delNode->next;
            free(delNode);
            printf("\n\n\t\tcase2. 일반적인 경우 특정 값 제거\n");
            return 1; //삭제 성공
        }

        prevNode = prevNode->next;
    }

    return 0; // 삭제할 값이 없는 경우 삭제 실패
}

int removekthNode(int k)
{
    if (head == NULL)
    {
        printf("\n\n\t\t생성된 노드가 없어서 삭제할수 없습니다.\n");
        return 0; // 삭제 실패
    }

    int nodeCount = getNodeCount(); //노드의 개수 구하기(노드의 개수를 구해왔다.)


   /* if (nodeCount == 0)
    {
        printf("\n\n\t\t생성된 노드가 없어서 삭제할 수 없습니다.\n");
        return 0; //삭제 실패
    }
    */
    if( k <= 0 || k > nodeCount)
    {
        printf("\n\n\t\t입력 값이 범위를 벗어났습니다.\n");
        printf("\t\t1~%d 사이의 정수를 입력해주세요.\n", nodeCount);

        return 0; //삭제 실패
    }

    node* delNode;
    node* prevNode;
    if (k == 1) //첫 번째 노드를 제거하는 경우?
    {
        delNode = head;
        head = head->next;
        free(delNode);
        printf("\n\n\t\tcase1. 첫 노드를 제거\n");
        return 1; // 삭제 성공
    }

    prevNode = head;
    int i;
    for (i = 0; i < k - 2; i ++) //삭제할 이전 위치로 이동
    {
        prevNode = prevNode->next;
    }

    delNode = prevNode->next; //삭제할 노드 지정
    prevNode->next = delNode->next;
    free(delNode);
    printf("\n\n\t\tcase2. 일반적인 경우 k번째 노드 제거\n");
    return 1;
}

//O(N); 노드의 개수만큼 반복
void insertTailNode(int data)
{
    node* newNode = createNode(data);

    node* curNode;
    curNode = head;

    if (head == NULL)
    {
        head = newNode;
        printf("\n\n\t\t노드 삽입(첫 노드로 연결)\n");
        return;
    }

    //마지막 노드로 이동
    while (curNode->next != NULL) //방문한 노드의 다음 노드가 있다면?
    {
        curNode = curNode->next; //다음 노드로 이동
    }

    curNode->next = newNode;
    printf("\n\n\t\t 노드 맨 뒤 삽입(일반적인 경우)\n");
    /*
    node* newNode;
    newNode = malloc(sizeof(node));
    newNode->value = data;
    newNode->next = NULL;

    if (head == NULL)
    {
        head = newNode;
        return;
    }
     */
}

//노드를 생성해서 생성된 노드의 주소를 리턴하는 함수
node* createNode(int data)
{
    node* newNode; //node* nNode;
    newNode = (node*)malloc(sizeof(node));
    newNode->value = data;
    newNode->next = NULL;

    return newNode;
}

void insertKthNode(int data, int k)
{
    int nodeCount = getNodeCount(); //노드의 개수를 구해 리턴하는 함수 호출

    if(k < 1 || k > nodeCount + 1)
    {
        printf("\n\n\t\t전달 된 값은 범위를 벗어난 값으로 추가할 수 없습니다.\n");
        printf("\t\t1 ~ %d 범위를 수를 입력해 주세요.\n", nodeCount + 1);
        return;
    }

    node* newNode = createNode(data); //노드 생성 함수 호출

    if (head == NULL)
    {
        head = newNode;
        printf("\n\n\t\tcase1. 노드 삽입(첫 노드로 연결)\n");
        return;
    }

    if (k == 1) // head에 저장된 값이 변경돼야 하기 때문이다.
    {
        newNode->next = head;
        head = newNode;
        printf("\n\n\t\tcase2. k == 1인 경우 맨 앞 삽입\n");
        return;
    }

    // 일반적인 경우(중간 삽입 - 마지막 노드까지 처리 가능)

    node* curNode = head;
    int i;
    for(i = 0; i < k - 2; i++) //삽입할 위치 이전으로 이동
    {
        curNode = curNode->next;
    }

    //새 노드랑 연결
    newNode->next = curNode->next;
    curNode->next = newNode;
    printf("\n\n\t\tcase3. k번째 노드 삽입(일반적인 경우)\n");

}

void insertSortedNode(int data)
{
    node* newNode = createNode(data);

    if (head == NULL)
    {
        head = newNode;
        printf("\n\n\t\tcase1. 노드 삽입(첫 노드로 연결)/n");
        return;
    }

    //가장 작은 값 삽입하는 경우?
    if(head->value > newNode->value)
    {
        newNode->next = head;
        head = newNode;
        printf("\n\n\t\tcase2. 가장 작은 값 삽입으로 맨 앞 추가\n");
        return;
    }

    //알반적인 경우(중간 삽입)
    node* prevNode = head;
    node* curNode = head;

    while(curNode->next != NULL) //마지막 노드 포함x
    {
        curNode = curNode->next;
        if(curNode->value > newNode->value)
        {
            //연결
            prevNode->next = newNode;
            newNode->next = curNode;
            printf("\n\n\t\tcase3. 일반적인 경우 중간 삽입\n");
            return;
        }
        prevNode = prevNode->next;
    }

    //가장 큰 값 삽입으로 맨뒤에 추가
    curNode->next = newNode;
    printf("\n\n\t\tcase4. 가장 큰 값 추가로 맨 뒤 삽입\n");
}