기술면접 알고리즘 [Linked List] : 링크드 리스트 노드 삭제 (Linked List Node deletion)

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

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

---

노드 삭제 (Linked List Node deletion)

Singly Linked List 에서 노드를 삭제할 때는, 간단하게 이전 노드의 다음 노드를 현재 노드의 다음 노드와 연결시켜주기만 하면 된다(prev->next = cur->next). 혹은, prev 노드 하나를 이용해도 된다(prev->next = prev->next->next).

    void delete_node(int x) {

        if (!head) {
            std::cout << "Linked list is empty" << std::endl;
            return;
        }

        Node* prev = head;
        Node* cur = head->next;

        if (head->data == x) {
            head = head->next;
            std::cout << "Head Node Deletion Complete" << std::endl;
            return;
        }

        while (cur) {
            if (cur->data == x) {
                prev->next = cur->next;
                delete cur;
                std::cout << "Node Deletion Complete" << std::endl;
                return;
            }
            cur = cur->next;
            prev = prev->next;
        }

        std::cout << "Node Not Found" << std::endl;
    }