240203_Linked List 구현

C언어도 처음 사용하고, 자료구조를 만드는 것도 처음이라 힘든 점이(특히 포인터) 많았는데, 어찌저찌 잘 구현되서 다행인 것 같다.

이번 Linked List에서 구현한 함수는 삽입(InsertNewNode), 삭제(DeleteNode), 인덱스검색(GetIndex), 인덱스를 통한 데이터 검색(GetData), 모든 노드 출력(PrintAllNode)이다.

---

먼저, 구조체 Node를 작성하고 전역 변수에 gHead 노드를 선언한다.

// Node 데이터 Struct
typedef struct Node
{
    int data;
    struct Node* next;
}Node;

// 전역 변수 gHead Node 초기화
Node* gHead = NULL;

---

그 후 먼저 오름차순 삽입(InsertNewNode) 함수를 구현한다.

// Inteager 오름차순 삽입
void InsertNewNode(int inputData)
{
    //Head Node 백업
    Node* tempHead = gHead;

    //신규 노드 생성
    Node* newNode = (Node *)malloc(sizeof(Node));
    newNode->data = inputData;
    newNode->next = NULL;

    // gHead에 연결된 것이 없다면 신규 노드 연결
    if(gHead == NULL)
        gHead = newNode;
    else
    {
        // 첫번째 데이터가 신규 노드의 데이터보다 작다면
        if(gHead->data < newNode->data)
        {
            // 신규 노드의 데이터보다 작을때, 다음 노드가 null일때까지 반복
            while(newNode->data > tempHead->next->data && tempHead->next != NULL)
            {
                tempHead = tempHead->next;
            }

            // 신규 노드가 제일 크다면(기존 마지막 노드까지 갔다면)
            if(tempHead->next == NULL)
            {
                tempHead->next = newNode;
            }
            // 중간에 신규 노드 연결
            else
            {
                newNode->next = tempHead->next;
                tempHead->next = newNode;
            }
        }

        // 첫번째 데이터보다 작다면
        else if(gHead->data > newNode->data)
        {
            newNode->next = gHead;
            gHead = newNode;
        }
    }
}

---

두번째로 모든 노드 출력(PrintAllNode) 함수를 테스트를 위해 구현하였다.

void PrintAllNode()
{
    // Head Node 백업
    Node* tempHead = gHead;

    // tempHead Node가 null일 때 까지(끝까지) Node 출력
    while(tempHead != NULL)
    {
        printf("tempHead[%p] , %d , next[%p]\n", tempHead, tempHead->data, tempHead->next);
        tempHead = tempHead->next;
    }
}

insert 후 출력 결과

처음 결과에서 주소값이 잘못찍혔는데, insert 함수 내에서

if(gHead == NULL)
        gHead = newNode->next;

이 부분이 잘못되어 수정하였다.

---

세번째로 노드 삭제(DeleteNode)함수를 구현하였다.

void DeleteNode(int deleteData)
{
    // Head Node 백업
    Node* tempHead = gHead;
    // Delete Node 저장용
    Node* deleteNode = NULL;

    // 만약 지워야하는 데이터가 첫번째 노드라면
    if(gHead->data == deleteData)
    {
        deleteNode = gHead;
        gHead = tempHead->next;
        deleteNode = NULL;

        free(deleteNode);
    }
    
    else
    {
        // while문 사용해서 해당 데이터를 가진 노드를 찾는다.
        while(tempHead->next->data != deleteData && tempHead->next->next != NULL)
        {
            tempHead = tempHead->next;
        }
        // 해당 데이터를 가진 Node가 없다면 text출력
        if(tempHead->next->next == NULL && tempHead->next->data != deleteData)
        {
            printf("해당 데이터가 없습니다.\n");
        }
        // 찾은 후 연결을 해제하고 메모리 할당 해제한다.
        else if(tempHead->next->next != NULL)
        {
            deleteNode = tempHead->next;
            tempHead->next = tempHead->next->next;
            deleteNode = NULL;

            free(deleteNode);
        }
    }
}

이 부분에서 다음 노드를 기준으로 삭제 데이터를 찾았는데, 이렇게 하면 첫번째 노드가 삭제 데이터인지 확인을 해야하는 코드가 작성되어야한다. 만약 Node 구조체 내에 자신의 왼쪽(즉 전에 위치한 노드)를 저장하는 변수가 있으면 더 좋을 것 같다는 생각을 했다.

삭제 결과

---

네번째로 인덱스 반환(GetIndex)함수를 구현하였다.

int GetIndex(int searchData)
{
    // Head Node 백업
    Node* tempHead = gHead;
    int index = 0;

    // SearchData와 같은 data를 가진 Node를 찾습니다.
    while(tempHead->data != searchData && tempHead->next != NULL)
    {
        tempHead = tempHead->next;
        index++;
    }

    // 만약, 마지막 노드의 데이터가 Searchdata와 같지 않다면 텍스트 출력 및 -1을 반환합니다.
    if(tempHead->data != searchData && tempHead->next == NULL)
    {
        printf("해당 데이터가 존재하지 않습니다.\n");
        return -1;
    }
    // 만약 같다면, 텍스트 출력 및 해당 index를 반환합니다.
    else if(tempHead->data == searchData)
    {
        printf("%d번째에 데이터가 존재합니다.\n", index);
        return index;
    }
}

결과

---

마지막으로 인덱스를 통해 데이터 값 찾기(GetData)함수 구현하였다.

// 인덱스를 통해 데이터를 반환합니다.
int GetData(int idx)
{
    // Head Node 백업
    Node* tempHead = gHead;
    int targetIndex = 0;
    
    // 해당 인덱스까지 검색합니다.
    while(tempHead->next != NULL)
    {
        // 만약 해당 인덱스에 도착했다면 현재 노드의 data를 반환합니다.
        if(targetIndex == idx)
            return tempHead->data;

        tempHead = tempHead->next;
        targetIndex++;
    }

    // 만약 반환이 안됐다면(인덱스를 찾지 못했다면) -1을 반환합니다.
    return -1;
}

결과

---

• 후기

모든 함수에 노드를 While문을 통해 순차 탐색을 진행하여 찾았는데, 더 나은 방법이 떠오르지 않았다. 리스트 자체를 포인터로 해서 하면 좀 더 나을까 했는데 비슷할 것 같아서 내일 구글링으로 다른 사람 코드를 참조해봐야겠다.