Node·List 구현

이 Part에서 다루는 것

• self-referential Node가 왜 가능한지
• 단방향/양방향 리스트 차이와 더미 노드(Dummy)의 의미
• 핵심 연산(AddAtHead, AddAtTail, Insert, Remove)의 연결 순서
• “리스트 삽입/삭제가 빠르다”의 정확한 조건

학습 목표

• 포인터 재연결 4줄이 어떤 불변식을 유지해야 하는지 설명할 수 있다.
• 더미 노드를 두는 이유(예외 처리 단순화)를 코드로 설명할 수 있다.
• 위치를 이미 아는 경우와 인덱스로 찾는 경우의 복잡도 차이를 설명할 수 있다.

---

Node 개념: self-referential 구조

template <typename T>
struct Node {
    explicit Node(const T& data = T()) : data(data) {}

    T data{};
    Node* prev = nullptr;
    Node* next = nullptr;
};

핵심:

• Node*는 Node “객체 자체”가 아니라 Node의 주소를 저장합니다.
• 그래서 Node 안에 Node*가 있어도 무한 중첩이 아니라, 링크(연결)만 만들어집니다.

---

단방향 vs 양방향

항목	단방향(Singly)	양방향(Doubly)
링크	next	prev + next
뒤로 이동	어려움	가능
중간 삭제	이전 노드 찾기 필요	이전/다음 링크 바로 갱신 가능
구현 난이도	낮음	조금 높음

실무 감각:

• 일반 학습/응용에서는 양방향 + 더미 노드 구조가 구현 안정성이 높습니다.

---

더미 노드(Dummy Node): 예외 처리를 줄이는 핵심

구조:

[HeadDummy] <-> [data1] <-> [data2] <-> ... <-> [TailDummy]

빈 리스트:

HeadDummy <-> TailDummy

리스트 불변식(Invariant)

• _head->next는 항상 첫 데이터 노드 또는 _tail
• _tail->prev는 항상 마지막 데이터 노드 또는 _head
• 빈 상태 판단: _head->next == _tail

소멸자에서 delete 순서(중요)

Node<T>* node = _head;
while (node != nullptr) {
    Node<T>* toDelete = node; // 1) 삭제 대상 백업
    node = node->next;        // 2) 먼저 다음으로 이동
    delete toDelete;          // 3) 삭제
}

포인트:

• delete 후 원래 포인터를 역참조하면 UB입니다.
• “다음 포인터를 먼저 저장”이 핵심 습관입니다.

---

AddAtHead / AddAtTail: 포인터 4개 재연결

AddAtHead

Node<T>* AddAtHead(const T& data)
{
    Node<T>* node = new Node<T>(data);
    Node<T>* nextNode = _head->next;

    node->prev = _head;
    node->next = nextNode;
    _head->next = node;
    nextNode->prev = node;

    return node;
}

AddAtTail

Node<T>* AddAtTail(const T& data)
{
    Node<T>* node = new Node<T>(data);
    Node<T>* prevNode = _tail->prev;

    node->prev = prevNode;
    node->next = _tail;
    prevNode->next = node;
    _tail->prev = node;

    return node;
}

핵심:

• 더미 노드가 있으면 빈 리스트/첫 삽입/마지막 삽입을 같은 로직으로 처리할 수 있습니다.

---

GetNode / Insert / Remove

GetNode(index): 탐색 O(N)

Node<T>* GetNode(int index)
{
    if (index < 0)
        return nullptr;

    Node<T>* node = _head->next;
    for (int i = 0; i < index; ++i) {
        if (node == _tail)
            return nullptr;
        node = node->next;
    }
    return (node == _tail) ? nullptr : node;
}

Insert(pos, data): 위치를 알면 O(1)

void Insert(Node<T>* posNode, const T& data)
{
    if (posNode == nullptr || posNode == _head)
        return;

    Node<T>* node = new Node<T>(data);
    Node<T>* prevNode = posNode->prev;

    node->prev = prevNode;
    node->next = posNode;
    prevNode->next = node;
    posNode->prev = node;
}

Remove(node): 위치를 알면 O(1)

Node<T>* Remove(Node<T>* node)
{
    if (node == nullptr || node == _head || node == _tail)
        return nullptr; // 더미 삭제 금지

    Node<T>* prevNode = node->prev;
    Node<T>* nextNode = node->next;

    prevNode->next = nextNode;
    nextNode->prev = prevNode;

    delete node;
    return nextNode;
}

---

“리스트 삽입/삭제 빠름”의 정확한 뜻

정답:

• 노드 위치를 이미 알고 있으면 삽입/삭제는 O(1)
• 인덱스로 위치를 먼저 찾으면 탐색 O(N) + 수정 O(1) = 총 O(N)

실전 예:

• 대기열 작업 객체의 노드 포인터를 따로 기억해두고 취소할 때 -> O(1) 삭제 가능
• “17번째 원소 지워줘”처럼 인덱스 기반이면 -> O(N) 탐색이 먼저 필요

체크 질문 (스스로 답해보기)

• 더미 노드를 두면 어떤 if 분기가 사라지는가?
• Remove에서 더미 노드를 삭제하면 왜 위험한가?
• 리스트가 벡터보다 삽입/삭제가 빠르다는 말이 언제 참이고 언제 거짓인가?

---