지금까지 살펴본 배열, 벡터 같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적입니다. 그래서 연결 리스트와 같은 형태의 자료 구조가 등장합니다. 많은 응용 프로그램에서 자료 구조 중간에 삽입 또는 삭제 작업을 필요로 합니다. 예를 들어 탭을 지원하는 브라우저는 언제든 새로운 탭을 임의의 위치에 옮길 수 있어야 하며, 음악 플레이어는 재생 목록 중간에 새로운 노래를 추가할 수 있어야 합니다. 이러한 경우 빠른 동작을 위해 연결 리스트를 사용할 수 있습니다. 뒷부분에서 음악 플레이어를 만드는 ‘실습 문제 1: 음악 재생 목록 구현하기’에서 연결 리스트의 사용 예를 볼 수 있을 것입니다. 일단 C++에서 제공하는 연결 리스트 관련 컨테이너에 대해 알아보겠습니다.

기본적인 연결 리스트를 구성하려면 포인터를 하나 가지고 있어야 하고, new와 delete 연산자를 이용하여 메모리를 할당하고 해제할 수 있어야 합니다. 이러한 기능을 구현하는 것이 그리 어렵지는 않지만 자칫 잘못하면 찾기 어려운 버그를 양산할 수 있습니다. C++는 C 스타일 배열에 대한 래퍼 클래스 std::array를 제공하듯이 기본적인 연결 리스트에 대한 래퍼 클래스인 std::forward_list 클래스를 제공합니다.

std::forward_list는 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공합니다. 성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않습니다. 즉, 맨 처음 원소에 접근하는 front() 함수를 제공하지만, 반대 방향의 원소로 이동하는 back() 같은 함수는 제공하지 않습니다. 원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 제공합니다. 이러한 기능은 기본적인 연결 리스트의 메모리 사용량이나 성능에 영향을 주지 않습니다.

std::vector와 마찬가지로 std::forward_list도 두 번째 템플릿 매개변수에 사용자 지정 할당자를 지정할 수 있습니다. 따라서 맞춤형 메모리 관리가 필요한 고급 응용 프로그램에서도 std::forward_list를 사용할 수 있습니다.