Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 단일 연결 리스트의 중간 노드 삭제하는 방법

연결 리스트 구조 정의

먼저 데이터(data)와 다음 노드를 가리키는 포인터(next)로 구성된 연결 리스트의 기본 구조를 정의하겠습니다.

struct Node {
    int data;
    struct Node* next;
};

노드 생성 함수 만들기

다음으로 createNode(int data) 함수를 작성합니다. 이 함수는 int 타입의 데이터를 매개변수로 받아, 해당 값을 새로 생성한 노드에 할당한 후 그 노드를 반환합니다. 새 노드의 next 포인터는 NULL로 초기화됩니다.

Node* createNode(int data){
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

중간 노드 삭제 함수 만들기

이제 핵심 역할을 하는 deleteMiddle(struct Node* head) 함수를 살펴보겠습니다. 이 함수는 리스트의 루트(헤드) 노드를 매개변수로 받으며 다음과 같이 동작합니다.

  • 헤드가 NULL이면 빈 리스트이므로 그대로 NULL을 반환합니다.
  • 노드가 하나뿐이라면 해당 노드를 삭제한 후 NULL을 반환합니다.
  • 그 외의 경우에는 전체 노드 개수를 세어 중간 위치(mid)를 계산하고, 중간 노드 바로 앞 노드의 next를 중간 노드의 다음 노드에 연결해 중간 노드를 건너뜁니다.
  • 마지막으로 수정된 리스트의 헤드인 temphead를 반환합니다.
struct Node* deleteMiddle(struct Node* head){
    if (head == NULL)
        return NULL;
    if (head->next == NULL) {
        delete head;
        return NULL;
    }
    Node* temphead = head;
    int count = nodeCount(head);
    int mid = count / 2;
    while (mid-- > 1) {
        head = head->next;
    }
    head->next = head->next->next;
    return temphead;
}

리스트 출력 함수 만들기

마지막으로 리스트의 헤드를 받아 전체 노드를 순회하며 출력하는 printList(Node *ptr) 함수를 작성합니다.

void printList(Node * ptr){
    while (ptr!= NULL) {
        cout << ptr->data << "->";
        ptr = ptr->next;
    }
    cout << "NULL"<<endl;
}

전체 구현 예제

지금까지 설명한 내용을 모두 종합하면, 단일 연결 리스트의 중간 노드를 삭제하는 완전한 프로그램을 다음과 같이 작성할 수 있습니다.

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
Node* createNode(int data){
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
int nodeCount(struct Node* head){
    int count = 0;
    while (head != NULL) {
        head = head->next;
        count++;
    }
    return count;
}
struct Node* deleteMiddle(struct Node* head){
    if (head == NULL)
        return NULL;
    if (head->next == NULL) {
        delete head;
        return NULL;
    }
    Node* temphead = head;
    int count = nodeCount(head);
    int mid = count / 2;
    while (mid-- > 1) {
        head = head->next;
    }
    head->next = head->next->next;
    return temphead;
}
void printList(Node * ptr){
    while (ptr!= NULL) {
        cout << ptr->data << "->";
        ptr = ptr->next;
    }
    cout << "NULL"<<endl;
}
int main(){
    struct Node* head = createNode(2);
    head->next = createNode(4);
    head->next->next = createNode(6);
    head->next->next->next = createNode(8);
    head->next->next->next->next = createNode(10);
    cout << "Original linked list"<<endl;
    printList(head);
    head = deleteMiddle(head);
    cout<<endl;
    cout << "After deleting the middle of the linked list"<<endl;
    printList(head);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Original linked list
2->4->6->8->10->NULL

After deleting the middle of the linked list
2->4->8->10->NULL

동작 원리 정리

  1. nodeCount() 함수로 전체 노드 개수를 셉니다.
  2. mid = count / 2 공식으로 중간 위치를 계산합니다.
  3. while 반복문을 통해 중간 노드의 바로 앞 노드까지 포인터를 이동시킵니다.
  4. 앞 노드의 next 포인터를 중간 노드의 다음 노드에 연결하여 중간 노드를 제거합니다.

시간 · 공간 복잡도

  • 시간 복잡도: O(n) — 노드 개수를 세는 과정과 중간 지점까지 이동하는 과정에서 각각 리스트를 순회하기 때문입니다.
  • 공간 복잡도: O(1) — 추가적인 자료구조 없이 포인터 변수만 사용합니다.

참고로, 이동 속도가 다른 두 개의 포인터(느린 포인터와 빠른 포인터)를 활용하면 리스트를 한 번만 순회해서도 중간 노드를 찾을 수 있습니다. 빠른 포인터는 두 칸씩, 느린 포인터는 한 칸씩 이동하다가 빠른 포인터가 리스트의 끝에 도달하면 느린 포인터가 정확히 중간에 위치하는 원리를 이용한 방법입니다.