기술면접 알고리즘 [Linked List] : 링크드 리스트 정렬 삽입 (Linked List insert in sorted way)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

링크드 리스트 정렬 삽입 (Linked List insert in sorted way)

 

정렬된 링크드 리스트에서, 삽입을 수행할 때 정렬된 상태를 유지하려면 어떻게 해야 할까?

1. 링크드 리스트가 비어 있을 경우 삽입되는 노드를 헤드로 만든다.

2. 원소가 하나일 경우, 삽입되는 노드를 헤드로 만들고 기존 헤드와 연결한다.

3. 원소가 여러 개일 경우, 순회를 하며 알맞은 위치에 끼워 넣는다.

#include <stdio.h>
#include <memory>
#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int data) : data{data}, next{nullptr} {}
};

struct List {
    List() : head{nullptr} {}
    
    void insert(int x) {
        Node* newNode = new Node(x);
        
        if (!head) {
            head = std::move(newNode);
            return;
        }
        
        if (head->data > x) {
            newNode->next = head;
            head = std::move(newNode);
            return;
        }

        Node* prev = head;
        Node* cur = head->next;
        
        while (cur) {
            if (cur->data < x) {
                cur = cur->next;
                prev = prev->next;
            } else {
                break;
            }
        }
        
        newNode->next = cur;
        prev->next = newNode;
    }
    
    friend std::ostream& operator<<(std::ostream &os, const List &list);
    
private:
    Node* head;
};

std::ostream& operator<<(std::ostream &os, const List &list) {
    Node* temp = list.head;
    
    while (temp) {
        os << temp->data << " ";
        temp = temp->next;
    }
    os << std::endl;
    
    return os;
}

int main()
{
    List l;
    
    l.insert(3);
    l.insert(5);
    l.insert(1);
    l.insert(2);
    l.insert(4);
    l.insert(7);
    l.insert(8);
    l.insert(6);
    
    std::cout << l;
    
    return 0;
}