더북(TheBook)

1.7 std::list

앞에서 설명했듯이 std::forward_list는 아주 기본적인 형태로 구현된 연결 리스트입니다. std::forward_list는 다른 유용한 기능 중에서도 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능은 제공하지 않습니다. 이는 메모리를 적게 쓰고 빠른 성능을 유지하기 위함입니다. 이외에도 std::forward_list의 반복자는 매우 적은 기능만 지원합니다. 컨테이너의 크기를 얻어오거나 또는 자료 구조 맨 뒤에 새로운 데이터를 추가하는 등의 기능은 매우 유용하고 빈번하게 사용되지만 std::forward_list에서는 지원되지 않습니다. 그러므로 std::forward_list는 빠른 원소 삽입이 필요한 모든 경우에 어울리는 컨테이너는 아닙니다. 이러한 std::forward_list의 단점을 보완하기 위해 C++는 std::list를 제공합니다. std::list는 양쪽 방향으로 연결된 리스트, 즉 이중 연결 리스트(doubly-linked list) 구조로 되어 있으며, 덕분에 std::forward_list에 비해 더 많은 기능을 제공합니다. 다만 std::forward_list에 비해 메모리를 조금 더 사용합니다.

이중 연결 리스트에서 사용하는 노드의 기본 형태는 다음과 같습니다.

struct doubly_linked_list_node
{
    int data;
    doubly_linked_list_node* next;
    doubly_linked_list_node* prev;
};

앞 코드에서 볼 수 있듯이 이중 연결 리스트 노드는 이전 노드를 가리키는 포인터가 추가로 있습니다. 이 포인터를 이용하여 역방향으로 이동할 수 있으며, 맨 마지막 원소와 리스트 크기를 따로 저장하여 빠른 push_back() 또는 size() 함수를 지원할 수 있습니다. 또한 std::forward_list와 마찬가지로 템플릿 매개변수로 사용자 정의 할당자를 지정할 수도 있습니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.