[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

 

---

알아두어야 할 점

캐싱 미스 문제

• 리스트는 연속적인 메모리(contiguous memory)가 아닌, 각 노드의 메모리가 임의의 위치에 존재하므로 주변에 있는 메모리 블록을 가져와도 리스트의 데이터를 가져오지 못할 가능성이 높다.
• 즉, 리스트의 메모리는 여기저기 분산되어 있어 공간 지역성의 이점이 제대로 작동하지 못해, 캐시 미스가 끔찍하게 많이 일어난다.

데이터 접근 속도 최적화

• 리스트는 원소의 삽입 / 삭제가 O(1)으로 매우 빠르지만, 삽입 / 삭제를 하기 위한 데이터 접근이 O(N)으로 느려 삽입/삭제가 빠르다는 장점을 살리지 못한다.
• ⇒ skip list와 같은 방법으로 데이터 접근 속도를 O(logN) 높여 사용한다.

리스트에서의 반복자(iterator)

• 리스트의 반복자(iterator)는 증감 연산자를 사용할 수 있지만, iterator + 5와 같은 형식은 사용할 수 없다.

itr++; itr--; // 가능
itr + 10 // 불가능

 

---

참고 자료

https://modoocode.com/314

https://modoocode.com/223

https://en.cppreference.com/w/cpp/container/list