1.5.1 std::forward_list에서 원소 삽입과 삭제

std::forward_list에서 원소를 삽입할 때에는 push_front()와 insert_after() 함수를 사용합니다. 이 두 함수는 std::vector에서 원소를 삽입할 때와는 조금 다른 동작을 수행합니다. push_front() 함수는 연결 리스트 맨 앞에 새로운 원소를 삽입합니다. std::forward_list는 마지막 원소에 직접 접근할 수 없으므로 push_back() 함수를 제공하지 않습니다. 특정 위치에 원소를 삽입하려면 insert()가 아니라 insert_after() 함수를 사용해야 합니다. 이는 연결 리스트에서 새로운 원소를 삽입한 후, 해당 위치 앞에 있는 원소의 next 포인터를 수정해야 하기 때문입니다. std::forward_list에서 반대 방향으로 이동하는 것이 허용되지 않으므로 특정 원소 뒤에 새로운 원소를 삽입한 후, 해당 원소의 next 포인터를 수정하는 것이 타당합니다.

연결 리스트에서 원소 삽입은 노드의 포인터 조작으로 구현되므로, 삽입 후 다른 원소를 이동할 필요가 없습니다. 그러므로 std::forward_list의 삽입 함수는 모두 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작합니다. std::forward_list의 삽입 함수는 리스트의 원소 크기에 영향을 받지 않으며, 시간 복잡도는 O(1)입니다. 다음 예제에서 이들 함수의 사용 방법에 대해 알아보겠습니다.

다음은 연결 리스트에 원소를 삽입하는 다양한 코드 예제입니다.

std::forward_list<int> fwd_list = {1, 2, 3};

fwd_list.push_front(0);       // 맨 앞에 0 추가: {0, 1, 2, 3}

auto it = fwd_list.begin();

fwd_list.insert_after(it, 5); // 맨 처음 원소 뒤에 5 추가: {0, 5, 1, 2, 3}

fwd_list.insert_after(it, 6); // 같은 위치에 6 추가: {0, 6, 5, 1, 2, 3}