[자료구조] 이중연결 리스트 c

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

#pragma warning (disable : 4996)

typedef struct DNode
{
    int value;               //값
    struct DNode* prev;     //이전 주소
    struct DNode* next;     //다음 주소

}DNode;

//전역 변수: 함수 어디서든 사용 가능 변수
//프로그램 실행 시 메모리가 할당되어 종료될 때까지 메모리가 할당되어 있다.
DNode* head = NULL; //첫 노드의 주소를 저장하는 포인터
DNode* tail = NULL; //마지막 노드의 주소를 저장하는 포인터

/*
//노드 생성 후 생성된 노드의 주소를 리턴
DNode* createDNode(int data)
{
    DNode* newNode = (DNode*)malloc(sizeof(DNode)); //구조체 변수(노드) 선언
    newNode->value = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode; //생성된 노드의 주소를 리턴
}
 */

DNode* createDnode(int data);
void insertFrontDNode(int data);
void insertTailDNode(int data);
void displayDNode();
void removeFirstDNode();
void removeTailDNode();
int getDNodeCount();
DNode* searchDNode(int target);
int removeTargetDNode(int target);
int removekthDNode(int k);

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

        printf("\n\n\t *** 이중 연결 리스트(Doubly Linked List)\n\n");
        printf("=======================================================\n");
        printf("1. 맨 앞 삽입\n");
        printf("2. 맨 뒤 삽입\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);
            insertFrontDNode(data);
            break;
        case 2:
            printf("\n\n삽입할 정수 입력: ");
            scanf("%d", &data);
            insertTailDNode(data);
            break;
        case 3:
            break;
        case 4:
            break;
        case 5:
            removeFirstDNode();
            break;
        case 6:
            removeTailDNode();
            break;
        case 7:
            break;
        case 8:
            printf("\n\n삭제할 값 입력: ");
            scanf("%d", &data);

            //removeTargetDNode : 삭제 성공시 1리턴, 삭제 실패시 0 리턴
            if (removeTargetDNode(data))
            {
                printf("\n\n\t\t삭제를 성공했습니다.\n");
            }
            else
            {
                printf("\n\n\t\t삭제를 실패했습니다.\n");
            }

            break;
        case 9:
            printf("\n\n몇 번째 데이터를 삭제하시겠습니까? ");
            scanf("%d", &k);

            if (removekthDNode(k))
            {
                printf("\n\n\t\t삭제를 성공했습니다.\n");
            }
            break;
        case 10:
            displayDNode();
            break;
        case 11:
            printf("\n\n생성된 노드의 개수는 %d개 입니다.\n", getDNodeCount());
            break;
        case 12:
            // searchDNode함수 : 검색된 값이 있으면 검색 노드의 주소를 리턴, 없으면 NULL을 리턴
            printf("\n\n검색 노드의 갑 입력 : ");
                scanf("%d", &data);
            if (searchDNode(data))
            {
                printf("\n\n\t\t검색한 노드는 존재 하지 않습니다. ");
            }
            else
            {
                printf("\n\n\t\t검색한 노드는 존재합니다. ");
            }
            searchDNode(data);
            break;
        case 0:
        return 0; // 프로그램 종료
        }

        printf("\n\n\t\t");
        system("read");

    }
    return 0;
}

//노드 생성 후 생성된 노드의 주소를 리턴
DNode* createDNode(int data)
{
    DNode* newNode = (DNode*)malloc(sizeof(DNode)); //구조체 변수(노드) 선언
    newNode->value = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode; //생성된 노드의 주소를 리턴
}

void insertFrontDNode(int data)
{
    DNode* newNode = createDNode(data);

    if(head == NULL)
    {
        //새 노드는 첫 노드이자 마지막 노드가 된다.
        head = newNode;
        tail = newNode;
        printf("\n\n\t\t 노드 삽입(첫 노드로 연결)\n");
        return;
    }

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


void insertTailDNode(int data) //O(1)
{
    DNode* newNode = createDNode(data); // 노드 생성 함수 호출
    if (head == NULL)
    {
        head = newNode;
        tail = newNode;
        printf("\n\n\t\t 노드 맨 뒤 삽입(첫 노드로 연결)\n");
        return;
    }
    tail->next = newNode;
    newNode -> prev = tail;
    tail = newNode;
}

void displayDNode()
{
    DNode* curNode;
    if(head == NULL)
    {
        printf("\n\n\t\t연결리스트가 구성되지 않아 출력할 데이터가 없습니다.\n");
        return;
    }
    system("clear");
    printf("\n\nDoubly Linked List: ");
    curNode = head;
    while (curNode->next != NULL)
    {
        printf("%d => ", curNode->value);
        curNode = curNode->next;
    }

    printf("%d\n", curNode->value);
}

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

    delNode = head;
    head = head->next;
    free(delNode);

    if (head != NULL)
    {
        head->prev = NULL;
    }

    if (head == NULL)
    {
        tail = NULL;
    }
}

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

    delNode = tail;
    tail = tail->prev;
    free(delNode);
    printf("\n\n\t\t마지막 노드가 제거됐습니다.\n");

    if(tail != NULL)
    {
        tail->next = NULL;
    }

    if(tail == NULL)
    {
        head = NULL;
    }
}

int getDNodeCount()
{
    DNode* curNode;
    int count;

    if (head == NULL)
    {
        return 0;
    }

    count = 0;
    curNode = head;
    while (curNode != NULL)
    {
        ++count;
        curNode = curNode->next;
    }

    return count; //개수를 리턴
}

DNode* searchDNode(int target)
{
    if (head == NULL)
    {
        return NULL;
    }

    // 첫노드부터 순회 하면서 검색한 노드가 존재하면 그 노드의 주소를 리탄
                    //검색한 노드가 존재하지 않는다면? NULL을 리턴
    DNode* curNode = head;
    while (curNode) //while (curNode != NULL)
    {
        if(curNode->value == target)
        {
            return curNode; //검색 노드의 주소를 리턴
        }
        curNode = curNode->next;
    }

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

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

    if(head->value == target) // 첫 노드를 삭제하는 경우? => head가 변경되야 하기 때문이다.
    {
        /*
        delNode = head; //첫 노드가 삭제할 노드
        head = head->next;
        free(delNode);

        //노드가 한 개인 경우 삭제 됐다면 발생되는 예외
        if (head != NULL)
        {
            head->prev = NULL;
        }
        if (head == NULL)
        {
            tail = NULL;
        }
         */
        removeFirstDNode(); //첫 노드를 제거 함수 호출 //위에 주석처리 대신해서 쓸 수 있다 (완전 동일한 코드이기 때문)
        printf("\n\n\t\tcase1. 특정 값이 첫 노드인 경우 제거 성공\n");
        return 1;
    }

    if(tail->value == target)// 마지막 노드를 삭제하는 경우? => tail이 변경돼야 하기 때문이다.
    {
        /*
        delNode = tail; //마지막 노드가 삭제할 노드
        tail = tail->prev;
        free(delNode);

        //노드가 한 개인 경우 삭제 됐다면 발생되는 예외
        if (tail != NULL)
        {
            tail->next = NULL;
        }
        if (tail == NULL)
        {
            tail = NULL;
        }
         */
        removeTailDNode(); //마지막 노드 제거하는 함수 호출 //위에 함수랑 코드가 동일해서
        printf("\n\n\t\tcase2. 특정 값이 마지막 노드인 경우 제거 성공\n");
        return 1;
    }

    //일반적인 경우
    DNode* curNode = head;
    while (curNode->next) //while(curNode->next != NULL)
    {
        curNode = curNode->next; //다음 노드로 이동
        if (curNode->value == target)
        {
            //노드 제거
            curNode->prev->next = curNode->next;
            curNode->next->prev = curNode->prev;
            free(curNode);
            printf("\n\n\t\tcase 3.중간 값 제거 성공\n");
            return 1; //삭제 성공
        }
    }

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

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

    int nodeCount = getDNodeCount(); //노드의 개수를 구하기

    if(k < 1 || k > nodeCount)
    {
        printf("\n\n\t\t전달 받은 값은 삭제할 수 없는 수 입니다.\n");
        printf("\t\t1 ~ %d 사이의 수를 입력해 주세요.\n", nodeCount);
        return 0; //삭제 실패
    }

    if(k == 1) //삭제할 노드가 첫 노드인 경우?
    {
        removeFirstDNode(); //첫 노드 제거함수 호출
        return 1; //삭제 성공
    }

    if(k == nodeCount) //삭제할 노드가 마지막 노드인 경우?
    {
        removeTailDNode(); //마지막 노드 제거 함수 호출
        printf("\n\n\t\tcase1. 마지막 노드 제거\n");
        return 1; //삭제 성공
    }

    //일반적인 경우
    if (k < nodeCount + 1 - k)
    {
        DNode* curNode = head;
        for(int i = 1; i <= k - 1; i++) //삭제할 위치로 이동
        {
            curNode = curNode->next;
        }

        curNode->prev->next = curNode->next;
        curNode->next->prev = curNode->prev;
        free(curNode);
        printf("\n\n\t\tcase3. 중간 값 제거");
        return 1;
    }

    else //뒤에서부터 읽는게 더 효울적
    {
        DNode* curNode = tail;

    }
	return 0;
}