[연결 리스트] 잦은 삽입 시 사용하는 알고리즘 (Feat. JAVA, C++)

 

 

연습하기 좋은 문제 : 

1228. [S/W 문제해결 기본] 8일차 - 암호문1

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14w-rKAHACFAYD

SW Expert Academy

 

1228. [S/W 문제해결 기본] 8일차 - 암호문1

1. node 클래스 설정 

 

 

어떤 언어를 사용하든 간단하게 Node를 작성한다. 

단, node는 next, data 요소를 가지고 있어야 한다. 

2. nodeList 클래스 설정 

nodeList의 구조는 다음과 같다.

 

NodeList는 head를 가지고 있어야 한다. 

 

 

각각의 함수는 다음과 같은 기능이 있다. (C++)

addNode

cnt만큼 node를 추가한다. 만약, head가 null인 경우 head를 저장한다. 

struct NodeList
{
    Node *head = NULL;

    void addNode(int cnt)
    {
        Node *node = head;
        for (int i = 0; i < cnt; i++)
        {
            cin >> m;
            Node *newNode = new Node;
            newNode->data = m;

            if (head == NULL)
            {
                head = newNode;
            }
            else
            {
                node->next = newNode;
            }
            node = newNode;
        }
    }
}

 

insertHead

새로운 노드를 head로 저장하고 insertNode함수로 다시 돌아간다.

struct NodeList
{
    Node *head = NULL;

   void insertHead(int cnt)
    {
        Node *newHead = new Node;
        cin >> m;
        newHead->data = m;
        newHead->next = head;
        head = newHead;
        insertNode(0, cnt - 1);
    }
}

insertNode

새로운 노드를 이전 노드의 다음으로 저장한다. 

 

struct NodeList
{
    Node *head = NULL;

    void insertNode(int x, int cnt)
    {
        if (x == -1)
        {
            insertHead(cnt);
            return;
        }
        Node *node = getNode(x);
        for (int i = 0; i < cnt; i++)
        {
            Node *newNode = new Node();
            cin >> m;
            newNode->data = m;

            newNode->next = node->next;
            node->next = newNode;
            node = newNode;
        }
    }
}

 

getNode

head부터 n번째 노드를 뽑아낸다

struct NodeList
{
    Node *head = NULL;

    Node *getNode(int n)
    {
        Node *node = head;
        for (int i = 0; i < n; i++)
        {
            node = node->next;
        }
        return node;
    }
}

 

print

head부터 10개만큼 노드의 data를 출력한다. 

struct NodeList
{
    Node *head = NULL;

    
    void print(int t)
    {
        cout << "#" << t;

        Node *node = head;

        for (int i = 0; i < 10; i++)
        {
            if (node == NULL)
                break;
            cout << " " << node->data;
            node = node->next;
        }

        cout << "\n";
    }
}

 

 

참고 ) 메인 함수

최대한 함수 사용을 최적화하기 위해 노력했다.

n개만큼 노드 생성 후, Insert되는 수만큼 insertNode함수를 실행한다. 

 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int t = 1; t <= 10; t++)
    {
        NodeList *nodeList = new NodeList;
        cin >> n;
        nodeList->addNode(n);

        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a >> x >> y;
            nodeList->insertNode(x - 1, y);
        }
        nodeList->print(t);
    }

    return 0;
}