[C] linked list reverse search with stack | 연결 리스트 역방향 탐색

www.notion.so/4-3f929c9129e541a98d860c38ae7f2afb

✔︎ 미션 4

1. 미션 제목

뒤에서 k번째 노드는 무엇일까요?

2. 지시문

이번에는 연결리스트의 응용 문제를 풀어보겠습니다. 연결리스트가 하나 주어졌을 때 해당 연결 리스트의 뒤에서 k번째 노드의 값은 무엇일지 알아낼 수 있을까요? 예를 들어, 9->8->4->14->5 라는 리스트가 주어질 때 뒤에서 2번째 노드를 출력하라고 하면 14가 출력이 되어야 합니다.

연결리스트가 이미 만들어져 있다고 가정하고, 아래와 같은 함수가 주어졌을 때 뒤에서 k번째 노드를 출력할 수 있을까요?

typedef struct node{
    int data;
    struct node* next;
} Node;

void append(Node* head, int data) {
    // 이 부분을 작성해 주세요!
}

int getLastNode (Node* head, int k) {
    // 이 부분을 작성해 주세요!
}

void printList(Node* head) {
    // 이 부분을 작성해 주세요!
}

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    append(head, 9);
    append(head, 8);
    append(head, 4);
    append(head, 14);
    append(head, 5);

    printList(head);

    printf("\n%dth last node is %d\n", 2, getLastNode(head, 2));
}

main 함수에는 정렬된 연결 리스트 1개가 미리 만들어져 있다고 가정합니다. 여러분이 작성하신 함수 getLastNode 함수에 main 함수에서 작성된 연결 리스트와 k를 파라미터로 주었을 때 뒤에서 k 번쨰 노드의 값이 나올 수 있을까요?

 

입력값:

미리 작성된 연결리스트와 k번째를 지칭하는 파라미터, 예들 들어 9->8->4->14->5 라는 리스트가 main 함수에 작성되어 있고, main 함수에서 해당 리스트와 k=2로 getLastNode를 호출

 

출력값:

9 8 4 14 5

2th last node is 14

 

3. 핵심 개념

#연결리스트 #리스트 삽입 #Slow Pointer #Fast Pointer

나의 풀이

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

typedef struct node {
    int data;
    struct node* next;
} Node;

void append(Node* head, int data) {
    // 이 부분을 작성해 주세요!
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data;
    n->next = NULL;

    Node* temp = (Node*)malloc(sizeof(Node));
    temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = n;
}

int getLastNode(Node* head, int k) {
    // 이 부분을 작성해 주세요!
    int data = -9999;
    Node* stack = (Node*)malloc(sizeof(Node));
    Node* temp = (Node*)malloc(sizeof(Node));
    if(stack == NULL || temp == NULL) data = -9999;

    stack->next = NULL;
    temp = head;
    while(temp->next != NULL) {
        Node* item = (Node*)malloc(sizeof(Node));
        item->data = temp->next->data;
        item->next = stack;
        stack = item;

        temp = temp->next;
    }
    for(int i = 0 ; i < k ; i++) {
        data = stack->data;
        stack = stack->next;
        if(stack == NULL) data = -9999;
    }
    return data;
}

void printList(Node* head) {
    // 이 부분을 작성해 주세요!
    Node* temp = (Node*)malloc(sizeof(Node));
    temp = head;
    while (temp->next != NULL) {
        printf("%d ", temp->next->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    append(head, 9);
    append(head, 8);
    append(head, 4);
    append(head, 14);
    append(head, 5);

    printList(head);

    int lastNum = 0;
    printf("\n%dth last node is %d\n", lastNum, getLastNode(head, lastNum));
}

사소한 부분 때문에 상당히 애를 먹은 미션이었습니다.

우선 Node 구조체를 보면 data와 next를 가지고 있습니다.

append()

append함수는 연결 리스트에 아이템을 추가하는 함수입니다.

이때 고려해야 할 점이 연결 리스트를 어떤 방향으로 설정할 것인가 입니다.

저는 이후에 나올 printList() 함수로 리스트 항목을 출력하기 편하도록

head→item1→item2→...→NULL 의 방향으로 설정했습니다.

void append(Node* head, int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data;
    n->next = NULL;

    Node* temp = (Node*)malloc(sizeof(Node));
    temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = n;
}

새 데이터를 가지는 n을 선언하여 data를 삽입하고, next에 NULL을 삽입하여 NULL을 가리키도록 하였습니다.

 

이후 temp를 선언하여 head의 주소를 입력했습니다. 여기서 가장 헷갈렸던 부분은 temp를 사용하지 않고 head만을 사용하여 append 함수를 수행할 수 있기 때문에 처음에는 head만을 이용하여 함수를 작성하였습니다.

 

하지만 문제는 head를 사용하여 item을 추가하였기 때문에 최종적으로는 head는 마지막에 추가된 head를 가리키고 있을 것입니다. 이렇게 되면 연결 리스트의 시작 부분에 대한 정보를 잃게 되는 것이었습니다.

 

이를 해결하기 위해 temp를 선언한 것입니다.

printList()

printList 함수는 리스트의 값들을 모두 출력하는 함수입니다.

void printList(Node* head) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp = head;
    while (temp->next != NULL) {
        printf("%d ", temp->next->data);
        temp = temp->next;
    }
    printf("\n");
}

이 함수에서도 역시 리스트의 시작 부분에 대한 정보(head)를 유지하기 위해 temp를 별도로 선언하여 사용해야 합니다.

 

append() 함수에서 새로 추가되는 아이템을 가리키는 방향으로 연결 리스트의 방향을 설정했기 때문에 printList 함수에서 연결된 아이템들을 순차적으로 접근하여 출력하면 되는 것입니다.

getLastNode()

getLastNode는 이 프로그램의 핵심이자 가장 난이도가 높았던 부분입니다.

파라미터로 k를 받아 리스트의 뒤에서부터 k번째에 저장된 아이템이 무엇인지 출력하는 함수입니다.

int getLastNode(Node* head, int k) {
    int data = -9999;
    Node* stack = (Node*)malloc(sizeof(Node));
    Node* temp = (Node*)malloc(sizeof(Node));
    if(stack == NULL || temp == NULL) data = -9999;

    stack->next = NULL;
    temp = head;
    while(temp->next != NULL) {
        Node* item = (Node*)malloc(sizeof(Node));
        item->data = temp->next->data;
        item->next = stack;
        stack = item;

        temp = temp->next;
    }
    for(int i = 0 ; i < k ; i++) {
        data = stack->data;
        stack = stack->next;
        if(stack == NULL) data = -9999;
    }
    return data;
}

stack

    stack은 파라미터로 받은 연결 리스트를 순회하며 반대 순서로 아이템들을 저장하기 위한 메모리입니다.

    즉, 연결 리스트의 방향을 반대로 바꿔서 저장하기 위한 공간입니다.

temp

    temp는 위의 함수들과 마찬가지로 리스트 시작 부분의 정보를 잃지 않고 순회하기 위한 임시 메모리 입니다.

 

stack은 입력 받은 연결 리스트와 반대 방향으로 저장되어야 하기 때문에 시작 부분이 NULL을 가리킵니다. (입력 받은 연결 리스트는 끝 부분이 NULL을 가리킵니다)

 

while문

    while문에서 item 노드를 만들고 temp→next의 데이터를 저장합니다. 최초에 temp는 head를 가리키고 있고, head는 아무 데이터고 가지지 않기 때문에 실제 데이터가 저장되기 시작하는 head→next 즉, temp→next를 저장하는 것입니다.

여기서 stack은 아이템이 저장되는 끝 주소와 같은 주소를 가집니다. (stack = item)

temp를 순회하면서 반복적으로 수행합니다.

 

for문

    while문을 순회하면서 stack에 연결 리스트 반대 방향으로 저장이 완료된다.

예를 들어 head→9→8→4→14→5→NULL 이 입력되었다면 stack=5→14→4→8→9→0→NULL이 저장됩니다.

for문에서는 저장된 stack에서 파라미터로 입력 받은 k만큼 반복하며 원하는 데이터를 찾습니다.

만약 파라미터로 연결 리스트의 크기보다 큰 값이 들어왔다면 -9999를 반환합니다.

파라미터로 0이 입력되어도 -9999를 반환합니다. (이 부분은 data가 선언될 때 초기화 된 부분입니다)

처음에 가장 막혔던 부분은 getLastNode 함수에서 while문 안에서 item을 동적으로 할당 할 때 while문의 마지막에 free(item)으로 item 메모리를 해제했습니다. 하지만 여기서 발생한 문제가 item을 해제하고 다음 반복에서 item을 새로 메모리에 생성할 때 기존에 item이 생성되었던 주소에서 그대로 다시 메모리가 할당되어서 stack이 계속 연결되지 못하고 무한루프에 빠지는 문제가 있었습니다.

free(item)을 삭제함으로써 문제가 해결됐습니다.

main함수와 결과창

주어진 예제보다 더 많은 값(10개)을 삽입했습니다.

그리고 뒤에서 0과 2, 11번째 값을 찾아보았습니다.

 

뒤에서 0번째는 없는 값이므로 -9999가 출력되었습니다.

뒤에서 2번째는 6이 정상적으로 출력되었습니다.

뒤에서 11번째는 연결 리스트의 크기보다 크기 때문에 -9999가 출력되었습니다.