Linked List 코드에서 데이터가 뒤가 아닌 앞(Append)에 추가시키려면 어떻게 해야할까요?

Question

Linked List 코드에서 데이터가 뒤가 아닌 앞(Append)에 추가시키려면 어떻게 해야할까요?

조회수 1533회

c++

0

싫어요

아래는 singly linked list 코드의 일부입니다. 실행시킨 후에 'I 1', 'I 2', 'I 3' 을 각각 입력하면 나중에 입력된 3 이 헤드로서 가장 먼저 나오도록 하고 싶은데 반대로 1 2 3 순서로 나와버리고 getHead 헤드도 1로 나옵니다. 출력될때 순서를 거꾸로 시킬까 생각해보았지만 그렇게 하기에는 헤드 출력시 헤드는 여전히 처음 입력한 값이 헤드로 되어버리기 때문에 생각한 이 방법은 안 통할 것 같네요.. 원하는대로 바꾸려면 고쳐야 할 부분이 많을까요? 초보라서 잘 모르고 학교 커리큘럼상 따라가보고는 싶지만 역시나 어렵네요ㅠㅠ 쉽게 설명해주시면 더욱 감사하겠습니다.

class InputData
{
public:
    int data;
    char query;
};

class Node
{
public:
    Node* next;
    int value;

public:
    Node(InputData* inputData) {
        this->value = inputData->data;
    }

    Node(int value) {
        next = NULL;
        this->value = value;
    }

    Node() {
        next = NULL;
        this->value = -1;
    }

    void print() {
        cout << value << endl;
    }
};


InputData* getInputData(string input) {
    InputData* inputData = new InputData();

    std::string delim = " ";
    std::string token;
    int pos = input.find(delim);
    if (pos != std::string::npos) {
        token = input.substr(0, pos);
        inputData->query = token[0];
        input.erase(0, pos + delim.length());
    } else if (input.length() > 0) {
        inputData->query = input[0];
    }

    if (input.length() > 0) {
        inputData->data = atoi(input.c_str());
    }

    return inputData;
}

void insertData(Node** root, InputData* inputData) {
    if (*root == NULL) {
        *root = new Node(inputData);
        return;
    }
    Node* nextNode = *root;
    while (nextNode->next != NULL) {
        nextNode = nextNode->next;
    }
    nextNode->next = new Node(inputData);

Node* getHeadNode(Node* root) {
    if (root != NULL) {
        return root;
    }
    return NULL;
}

void printNode(Node* root) {
    Node* nextNode = root;
    while (true) {
        if (nextNode != NULL) {
            printf("%d ", nextNode->value);
            nextNode = nextNode->next;
        }
        else {
            break;
        }
    }
}
}

(•́ ✖ •̀)
알 수 없는 사용자

댓글 입력

score 2 · Accepted Answer

2중 연결이면 더욱 쉽게 사용 가능할 것 같습니다만 싱글이면 어쩔 수가 없습니다.

void AppendData(Node** root, Node** pos/*현재 위치*/, InputData* inputData)
 {
    if (*root == NULL) {
        *root = new Node(inputData);
        *pos = *root;
        return;
    }

    if(*pos == NULL)
    {
        // 현 위치를 모를때 루트의 앞에 넣거나 뒤로 넣거나 하도록 만들 수 있습니다.
        return;
    }

    if ( *root != *pos) // 루트가 아닌 중간에 삽입되는 경우
    {
        Node* nextNode = *root;

        while (nextNode->next != *pos) {
            nextNode = nextNode->next;
        }

        nextNode->next = new Node(inputData);
        (nextNode->next)->next = *pos;
    }
    else // 루트의 앞에 삽입될 경우(root == pos)
    {
        *root = new Node(inputData);
        (*root)->next = *pos;
    }
 }

앞에 삽입하는 방법은 비교적 쉽습니다. 미리 만들어 둔 객체의 next에 연결하면 뒤로 삽입하는 방법이지만 나중에 만든 객체의 next에 연결하면 미리 만든 객체가 뒤로 밀려나게 됩니다.

따라서 먼저 입력한 값이 뒤로 나중에 입력한 값이 앞(head)로 가게 됩니다.