C++ std::list erase() 사용시 연결은 왜 끊기지 않을까?

std::list erase() 사용 시 연결은 왜 끊기지 않을까?

그동안 무심코 사용해왔던 std::list erase(), 생각해 보면 std::list는 포인터들의 연결이고 중간 삽입, 삭제가 빠르다 정도로 알고 있었다. 그러다가 연결된 리스트인데 중간을 제거하면 끊기는 거 아닌가라는 막연한 생각이 들기 시작했다.

• std::list는 이중 연결 리스트(doubly linked list) 구조이다.
• 이중 연결 리스트 구조이기 때문에 각 노드는 자신의 앞뒤 노드에 대한 위치 정보를 갖는다.
• 아래의 사슬과 같은 구조를 생각하면 쉽다.

std::list는 포인터들을 연결한 노드 체인이다.

erase() 제거 과정

• A <->B<->C 의 리스트에서 B를 erase() 하면
• A의 next를 C로 변경
• C의 prev를 A로 변경
• B 메모리 해제
• 결과적으로 A<->C가 완성
• B를 제거하였지만 연결은 끊기지 않는다.

erase() 내부 구현 코드

erase()의 내부 구현 코드를 보면 제거 시 prev, next를 앞뒤 노드에 연결하고 스스로를 제거하는 간단한 내용이라는 것을 알 수 있다. 그렇기 때문에 erase()를 통한 매우 빠른 제거가 가능하다. (O(1)의 시간 복잡도)

iterator erase(iterator pos)
{
    Node* node = pos.node;

    if (node == sentinel)
        return end(); // end() erase 방지

    Node* prev = node->prev;
    Node* next = node->next;

    prev->next = next;
    next->prev = prev;

    delete node;
    --count;

    return iterator(next);
}

정리하자면

• std::list는 "포인터를 연결한 노드 체인"이다.
• std::list는 이중 연결 리스트(doubly linked list) 구조이다.
• erase() 함수는 그 체인의 고리 하나를 제거하고 그 부분을 앞뒤로 연결하는 작업이다.