[C++ - TIL] 인접 리스트 기반 그래프 구현 및 동적 메모리 관리

🎮 주제 : 인접 리스트 기반 그래프 구현 및 동적 메모리 관리

태그 : #C++ #자료구조 #그래프 #인접리스트 #포인터배열 #메모리관리

---

📌 학습 요약

• 인접 리스트(Adjacency List)의 효율성 : 정점마다 연결된 정점 정보를 연결 리스트로 관리하여, 간선이 적은 희소 그래프(Sparse Graph)에서 인접 행렬보다 뛰어난 메모리 효율성을 확보함
• 포인터 배열 구조 설계 : Node** list 구조를 통해 각 정점이 개별적인 연결 리스트의 헤드(Head)를 가질 수 있도록 이중 포인터 기반의 동적 배열 설계
• 동적 리스트 확장 및 초기화 : 정점 추가 시 resize를 통한 용량 관리와, 간선 추가 시 인접 리스트 배열을 안전하게 생성하고 nullptr로 초기화하는 프로세스 정립
• 연쇄적 메모리 해제 : 소멸자에서 포인터 배열뿐만 아니라 각 정점에 매달린 모든 Node들을 순회하며 삭제하여 메모리 누수를 원천 차단하는 기법 체득

---

🛠 주요 코드 및 구현 상세

1. 인접 리스트의 노드 구조와 그래프 골격

template <typename T>
class Graph {
private:
    struct Node {
        T data;
        Node* next;
        Node(T data, Node* link = nullptr) : data(data), next(link) {}
    };

    int size;       // 현재 정점 개수
    int capacity;   // 할당된 배열 용량
    T* vertex;      // 정점 데이터 저장 배열
    Node** list;    // 각 정점의 연결 리스트 헤드를 담는 포인터 배열
};

2. 간선 추가 및 리스트 초기화 (edge)

void edge(int i, int j) {
    if (size <= 0 || i >= size || j >= size) return;

    // 인접 리스트 배열이 없다면 정점 개수만큼 생성
    if (list == nullptr) {
        list = new Node*[size];
        for (int k = 0; k < size; k++) list[k] = nullptr;
    }

    // 양방향 그래프: i의 리스트에 j 추가, j의 리스트에 i 추가
    // 새 노드를 리스트의 가장 앞에 삽입하여 O(1) 성능 확보
    list[i] = new Node(vertex[j], list[i]);
    list[j] = new Node(vertex[i], list[j]);
}

3. 안전한 메모리 해제 로직 (소멸자)

~Graph() {
    for (int i = 0; i < size; i++) {
        Node* deleteNode = list[i];
        while (deleteNode != nullptr) {
            Node* nextNode = deleteNode->next; // 다음 노드 미리 저장
            delete deleteNode;                 // 현재 노드 삭제
            deleteNode = nextNode;             // 다음 노드로 이동
        }
    }
    delete[] list;   // 포인터 배열 해제
    delete[] vertex; // 정점 배열 해제
}

---

✅ 주요 문법 및 개념 정리

항목 인접 행렬 (Matrix) 인접 리스트 (List)

공간 복잡도	O(V^2)	O(V + E)
연결 확인	O(1)	O(Degree(V))
탐색 효율	모든 정점 조사 필요	연결된 정점만 즉시 조사 가능
적합한 그래프	밀집 그래프 (Dense Graph)	희소 그래프 (Sparse Graph)

💡 주의 : 소멸자 내 포인터 제어

• 핵심 : delete를 호출한 직후에는 해당 객체의 멤버(next)에 접근할 수 없습니다.
• 해결 : 반드시 delete 수행 전에 nextNode = deleteNode->next를 통해 다음 목적지를 확보해야 안전하게 전체 리스트를 순회할 수 있습니다.

---

✨ 느낀 점

• 인접 리스트는 메모리 효율이 좋지만, 동적 할당된 Node들을 관리해야 하므로 인접 행렬보다 구현의 정밀도가 더 요구됨을 배움
• Node**와 같이 포인터를 담는 배열을 다루면서 이중 포인터와 메모리 구조에 대한 이해가 한층 깊어짐
• 소멸자에서 while문을 이용해 연결 리스트를 순차적으로 삭제하는 로직을 통해 메모리 관리의 엄격함을 다시금 실감함
• 간선을 추가할 때 리스트의 맨 앞에 새 노드를 삽입하는 방식이 push_back보다 효율적일 수 있다는 설계적 통찰을 얻음