[C++ STL] std::list 개요

 

※ std::list 요약

std::list는 double linked list(이중 연결 리스트)라는 자료구조를 이용하여 만든 시퀀스 컨테이너다.
템플릿 기반이므로 임의 타입을 요소로 가질 수 있으며, 요소 개수에 따라 동적으로 메모리를 관리한다.
double linked list로 되어 있기에 double linked list의 특징을 거의 그대로 가지고 있으며 linked list 자료구조에 대한 이해가 있어야 알맞는 상황에 알맞게 사용할 수 있다. 필자는 std::list를 거의 사용하지 않는다. 나뻐서 안 사용한다기 보다는 std::vector로도 충분한 상황이 대부분이기 때문이다.

※ std::list 특징

- 고정 길이인 배열에 비해 길이가 가변적이다.
- std::vector와 달리 데이터의 중간 삽입, 중간 삭제 속도가 빠르다.
- 데이터 중간 삽입, 삭제시 요소 개수에 상관없이 동일한 상수시간이 소요된다.(상수 시간 복잡도의 수행 성능 보장)

- list의 순회 속도는 O(n), 즉 요소 개수가 많을 수록 순회 속도는 느리다.

- 각 노드는 앞쪽, 뒤쪽 노드와 연결된 이중 연결 리스트다.(반대는 std::forward_list로써, 단일 연결 리스트다)

- 노드 기반이므로 []나 at()을 지원하지 않는다.

 

※ std::list를 사용해야 하는 경우

- 저장할 데이터의 개수가 가변적일때
- 저장된 요소를 자주 검색하지 않을때
- 중간에 데이터 삽입, 삭제가 자주 발생할때
- 랜덤 엑세스를 자주 안할때