나만의 작은 도서관
[C++][STL Container] 시퀀스 컨테이너 #2. 리스트(List) 본문
시퀀스 컨테이너란?
- 시퀀스 컨테이너(Sequence Container)는 C++에서 제공하는 STL 컨테이너 종류(시퀀스 컨테이너, 연관 컨테이너, 컨테이너 어뎁터) 중 하나로, 원소들을 순차적으로 저장하는 컨테이너이다.
시퀀스 컨테이너의 종류
- 벡터(vector)
- 리스트(list, forward_list) - [현재 글]
- 데크(deque)
- 배열(array)
리스트(List)란?
- 리스트는 이중 연결 리스트(double linked list) 방식으로 구현된 자료구조로, 양방향 연결 구조를 가진다.
- forward-list는 단일 연결 리스트 방식으로 구현된 자료구조.
- 임의의 위치에 대한 데이터 접근이 느리다. (시간복잡도 O(N))
- 원소를 삽입 / 삭제하는 작업이 빠르다. (시간복잡도 O(1))
- 삽입 / 삭제 위치 앞, 뒤 노드의 링크만 바꿔주면 되기 때문.
- “맨 끝, 맨 앞”에 원소를 삽입 / 삭제하는 작업이 빠르다. (시간복잡도 O(1))
- “임의의 위치”에 원소를 삽입 / 삭제하는 작업은 빠르지 않다. (시간복잡도 O(N))
- 해당 위치에 접근하기 위해 시작 위치부터 한 노드씩 이동해야하기 때문.
리스트 멤버 함수
원소 접근 관련(Element access)
front() | 첫번째 원소에 접근 |
back() | 마지막 원소에 접근 |
수정 관련(Modifiers)
push_back() | 맨 끝에 원소 삽입 |
pop_back() | 맨 끝에 원소 삭제 |
push_front() | 맨 앞에 원소 삽입 |
pop_front() | 맨 앞에 원소 삭제 |
insert() | 지정한 위치에 원소 삽입 |
erase() | 지정한 위치에 원소 삭제 |
clear() | list를 비운다. |
resize() | list의 크기(size)를 재조정한다. |
emplace() | 지정한 위치에 원소 삽입 (insert와 유사. 사용 추천 X) |
emplace_back() | 맨 끝에 원소 삽입 (push_back과 유사. 사용 추천 X) |
emplace_front() | 맨 앞에 원소 삽입 (push_front와 유사. 사용 추천 X) |
swap() | 지정한 list와 swap한다. |
크기 관련(Capacity)
empty() | list의 size가 0인지 확인한다(bool 타입 반환) |
size() | list의 크기(원소의 개수) |
max_size() | 가능한 최대 size 반환. |
더 자세한 내용은 아래 링크 참조
https://en.cppreference.com/w/cpp/container/list
std::list - cppreference.com
template< class T, class Allocator = std::allocator > class list; (1) (2) (since C++17) std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported.
en.cppreference.com
알아두어야 할 점
캐싱 미스 문제
- 리스트는 연속적인 메모리(contiguous memory)가 아닌, 각 노드의 메모리가 임의의 위치에 존재하므로 주변에 있는 메모리 블록을 가져와도 리스트의 데이터를 가져오지 못할 가능성이 높다.
- 즉, 리스트의 메모리는 여기저기 분산되어 있어 공간 지역성의 이점이 제대로 작동하지 못해, 캐시 미스가 끔찍하게 많이 일어난다.
데이터 접근 속도 최적화
- 리스트는 원소의 삽입 / 삭제가 O(1)으로 매우 빠르지만, 삽입 / 삭제를 하기 위한 데이터 접근이 O(N)으로 느려 삽입/삭제가 빠르다는 장점을 살리지 못한다.
- ⇒ skip list와 같은 방법으로 데이터 접근 속도를 O(logN) 높여 사용한다.
리스트에서의 반복자(iterator)
- 리스트의 반복자(iterator)는 증감 연산자를 사용할 수 있지만, iterator + 5와 같은 형식은 사용할 수 없다.
itr++; itr--; // 가능
itr + 10 // 불가능
참고 자료
'C++ > 문법 및 메소드(STL)' 카테고리의 다른 글
[C++][STL Container] 시퀀스 컨테이너 #4. 배열(Array) (0) | 2025.03.15 |
---|---|
[C++][STL Container] 시퀀스 컨테이너 #3. 데크(deque) (0) | 2025.03.15 |
[C++][STL Container] 시퀀스 컨테이너 #1. 벡터(vector) (0) | 2025.03.15 |
[C++][STL] 컨테이너(Container) (0) | 2025.03.14 |
[C++][STL] 반복자(Iterator) (0) | 2025.03.13 |