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


아래는 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;
        }
    }
}
}
  • 2016년 09월 18일에 작성됨

조회수 109


1 답변


좋아요
2
싫어요
채택취소하기

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)로 가게 됩니다.

  • 2016년 09월 18일에 작성됨
    C++을 중점으로 배우고 있는 학생입니다. 잘 부탁 드립니다!

  • 답변 감사합니다. pos가 의미하는 것은 현재 위치인가요? 제가 올린 코드에서 클래스 바로 다음에 있는 InputData* getInputData(string input) 함수 부분도 '인풋 데이터를 가공해주는 역할이다. ' 정도로는 알겠는데 일단 pos나 npos를 모르다보니 거기서부터 원리는 이해가 잘 가지 않네요..     이성우   2016.9.18 19:07     
  • 그리고 작성해주신 코드로 공부해보려고 해당코드를 넣고 아직 메인함수에서 콜 하지는 않은 상태에서 빌드해보았는데요. 뒷쪽 에 있는 *root->next = *pos; 줄에서 식에 클래스 포인터 형식이 있어야한다며 오류가 나오네요..ㅎㅎ    이성우   2016.9.18 19:16     
  • 죄송합니다. 군대 사지방에서 작성하니 컴파일 해보지 못해서 오류가 난 것 같습니다. 포인터 연산에 관한 우선순위 때문에 오류가 났습니다.    유현호   2016.9.20 20:35     
  • pos는 위치입니다. position의 약칭으로 자주 쓰이는걸 보았습니다. int 형의 불가리아표기법이 i 혹은 n을 접두어로 사용되니 nPos라고 대문자로 구별하시면 더 편하실 겁니다. pos의 역할은 head부터 tail까지 이어진 링크드 리스트에서 중간에 있는 값을 확인하기 위한 이동하기 편한 기억장소 입니다. 따라서 제가 올린 코드에서 pos의 역할은 현재 내가 어느 위치 혹은 몇 번째 값의 위치(예를 들면 cnt[3] 같은 위치입니다.)에 있으니 이 앞에 값을 집어넣으면 된다 라는 의미 입니다.    유현호   2016.9.20 20:35     

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close