C++ List

List

std::List

양방향 연결 리스트를 구현한 표준 라이브러리 컨테이너입니다.
이는 삽입과 삭제가 리스트의 양쪽 끝에서 모두 빠르게 이어지도록 하는 자료구조입니다.

std::list의 주요 특징

1. 양방향 연결 리스트: 각 요소는 이전 요소와 다음 요소에 대한 포인터를 가지고 있어, 리스트 내에서 양쪽으로 탐색할 수 있습니다.
2. 동적 크기 조절: 리스트는 동적으로 크기를 조절할 수 있으며, 삽입 및 삭제가 O(1)에 가능합니다.
3. 탐색 : O(N), 특정한 노드를 탐색하기 위해서는 head부터 탐색하는 방법 말고는 없으므로 O(N)의 시간이 걸립니다.

std::list의 기본 사용법

#include <list>
#include <iostream>

int main() {
    std::list<int> myList;

    // 요소 추가
    myList.push_back(1);
    myList.push_front(2);
    myList.insert(std::next(myList.begin()), 3);

    // 요소 출력
    for (const auto& element : myList) {
        std::cout << element << " ";
    }
    
    return 0;
}

주요 멤버 함수

• push_back(value) 및 push_front(value): 리스트의 끝 또는 시작에 요소를 추가합니다.
• pop_back() 및 pop_front(): 리스트의 끝 또는 시작에서 요소를 제거합니다.
• insert(position, value): 특정 위치에 요소를 삽입합니다.
• erase(position) 또는 erase(start, end): 특정 위치 또는 범위의 요소를 제거합니다.
• size(): 리스트의 현재 크기를 반환합니다.
• begin(), end(), rbegin(), rend(): 순차적인 반복자를 반환합니다.
• clear(): 리스트의 모든 요소를 제거합니다.
• splice(position, otherList): 다른 리스트의 모든 요소를 특정 위치에 이동시킵니다.
• sort(): 리스트의 요소를 정렬합니다.

std::list는 반복자(iterator)를 통해 요소에 접근하고 조작할 수 있습니다. 자주 사용되는 연산은 삽입, 삭제, 순회 등이며, 이를 위해 반복자를 사용합니다.

문제 풀이

문제 1.

std::list의 주요 특징에 대해서 설명해주세요.