C++ 연결 리스트 삽입 정렬 구현 방법

C++ 연결 리스트 삽입 정렬이란?

연결 리스트(linked list)가 주어졌을 때, 이 리스트를 삽입 정렬(Insertion Sort)로 오름차순 정렬하는 문제를 살펴보겠습니다. 예를 들어 리스트가 [9,45,23,71,80,55]라면, 정렬 결과는 [9,23,45,55,71,80]이 되어야 합니다.

배열과 달리 연결 리스트는 임의 접근(random access)이 불가능하지만, 노드의 삽입과 삭제가 포인터 조작만으로 O(1)에 가능하기 때문에 삽입 정렬과 특히 잘 어울리는 자료구조입니다.

알고리즘 접근 방법

삽입 정렬의 핵심 아이디어는 각 노드를 하나씩 꺼내서, 이미 정렬된 부분 리스트에서 올바른 위치를 찾아 삽입하는 것입니다. 단계별로 정리하면 다음과 같습니다.

임시 더미(dummy) 노드를 생성합니다. 이 노드는 정렬된 결과 리스트의 시작점 역할을 하며, head 삽입 로직을 단순화해 줍니다.
원본 리스트의 head를 가리키는 node 포인터를 준비합니다.
node가 NULL이 아닌 동안 다음 과정을 반복합니다.
- 다음 노드를 nextNode에 미리 저장해 둡니다. 삽입 과정에서 포인터가 변경되므로, 원본 리스트 순회를 이어가기 위해 필요합니다.
- 더미 노드부터 시작해 정렬된 리스트를 처음부터 순회하며, 현재 노드의 값보다 큰 값을 가진 첫 번째 노드(또는 리스트의 끝)를 찾습니다.
- 찾은 위치 바로 앞에 현재 노드를 삽입합니다.
- node를 nextNode로 이동해 다음 노드를 처리합니다.
모든 노드를 처리한 후, 더미 노드의 다음 노드(dummy->next)를 반환합니다.

C++ 구현 예제

위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.

class Solution {
public:
    ListNode* insertionSortList(ListNode* a) {
        // 정렬된 결과를 담을 더미 노드
        ListNode* dummy = new ListNode(-1);
        ListNode* node = a;

        while(node != NULL){
            // 원본 리스트 순회를 이어가기 위해 다음 노드를 미리 저장
            ListNode* nextNode = node->next;

            // 정렬된 리스트에서 삽입 위치 탐색
            ListNode* dummyHead = dummy->next;
            ListNode* prevDummyHead = dummy;

            while(dummyHead != NULL && dummyHead->val <= node->val){
                prevDummyHead = dummyHead;
                dummyHead = dummyHead->next;
            }

            // 현재 노드를 올바른 위치에 삽입
            node->next = dummyHead;
            prevDummyHead->next = node;

            // 다음 노드로 이동
            node = nextNode;
        }
        return dummy->next;
    }
};

실행 예시

입력

[9,45,23,71,80,55]

출력

[9,23,45,55,71,80]

복잡도 분석

시간 복잡도: O(n²) — 최악의 경우(역순으로 정렬된 리스트)에는 각 노드마다 정렬된 부분 리스트 전체를 순회해야 합니다. 다만 리스트가 거의 정렬되어 있다면 내부 반복문이 빠르게 종료되므로, 실제로는 훨씬 효율적으로 동작합니다.

공간 복잡도: O(1) — 더미 노드와 몇 개의 포인터만 추가로 사용하며, 제자리(in-place) 정렬 방식입니다.

마무리

배열에서의 삽입 정렬은 요소를 한 칸씩 뒤로 밀어야 하지만, 연결 리스트에서는 포인터 연결만 변경하면 되므로 삽입 자체는 상수 시간에 수행됩니다. 따라서 데이터 크기가 크지 않거나 리스트가 대체로 정렬되어 있는 경우에 안정적이고 효율적인 선택이 될 수 있습니다.