5. List & Forward List

list(리스트)는 벡터, 덱과는 또 다른 시퀀스 컨테이너로, 벡터와 덱이 배열 기반 컨테이너인 반면 리스트는 노드 기반 컨테이너이다. 헤더파일 <list>를 인클루드하면 list를 사용할 수 있으며, <list> 내부에서 인클루드하는 헤더파일 <bits/stl_list.h>에 list 클래스가 정의되어 있다. list는 이중 연결 리스트로 구현된다.

 

리스트의 선언과 초기화 역시 벡터, 덱과 같은 방법으로 할 수 있다. 연산자는 벡터, 덱에서 사용할 수 있는 것들 중 []을 제외한 $7$가지를 사용할 수 있다.

 

list의 멤버 함수는 vector, deque와 약간 다르다. 다음은 vector 또는 deque에 내장된 것과 유사한 멤버 함수들이다.

list::push_back
list::pop_back
list::push_front
list::pop_front
list::assign
list::resize
list::insert
list::front
list::back
list::size
list::clear
list::empty
list::erase
list::begin
list::end
list::rbegin
list::rend
list::emplace
list::emplace_back
list::emplace_front
list::max_size
list::swap

그밖에 vector, deque에는 내장되지 않은 함수들은 다음과 같다.

l.merge(k);	k를 l에 오름차순 합병 정렬한다.
l.merge(k,p);	k를 조건 p를 기준으로 l에 합병 정렬한다.
l.splice(p,k);	p가 가리키는 위치에 k의 모든 원소를 삽입한다.
l.splice(p,k,q);	p가 가리키는 위치에 k의 q가 가리키는 원소를 삽입한다.
l.splice(p,k,b,e);	p가 가리키는 위치에 k의 반복자 구간 [b,e)에 포함된 원소를 삽입한다.
l.remove(x);	l에서 x 원소를 모두 삭제한다.
l.remove_if(p);	l에서 조건 p가 참인 원소를 모두 삭제한다.
l.reverse();	l 순차열을 뒤집는다.
l.unique();	l의 인접한 원소들이 같다면 하나만 남기고 모두 삭제한다.
l.unique(p);	l의 인접한 원소들이 조건 p를 만족한다면 하나만 남기고 모두 삭제한다.
l.sort();	l의 모든 원소를 오름차순으로 정렬한다.
l.sort(p);	l의 모든 원소를 조건 p를 기준으로 정렬한다.

---

forward_list는 list와 비슷하지만 단방향 연결 리스트라는 차이가 있다. 따라서 각각의 노드가 저장하는 정보가 더 적기 때문에 list보다 성능은 약간 빠르지만 list에서 사용할 수 있는 멤버 함수의 일부를 사용할 수 없다. 다음의 함수들은 앞서 소개한 것과 비슷하게 이해할 수 있다.

forward_list::push_front
forward_list::pop_front
forward_list::assign
forward_list::resize
forward_list::front
forward_list::clear
forward_list::empty
forward_list::begin
forward_list::end
forward_list::emplace_front
forward_list::max_size
forward_list::swap

그밖에 앞에서는 나오지 않았던 forward_list의 멤버 함수는 다음과 같다.

fl.insert_after(p,x);	p가 가리키는 위치 뒤에 x를 삽입한다.
fl.insert_after(p,n,x);	p가 가리키는 위치 뒤에 n개의 x를 삽입한다.
fl.insert_after(p,b,e);	p가 가리키는 위치 뒤에 반복자 구간 [b,e)에 포함된 원소를 삽입한다.
fl.erase_after(p);	p가 가리키는 위치의 원소를 삭제한다.
fl.erase_after(b,e);	반복자 구간 (b,e)에 포함된 원소를 삭제한다.
fl.before_begin();	fl의 첫 번째 원소 앞의 반복자를 참조한다. 단독으로 참조하는 것은 UB이다.
fl.emplace_after(p,x);	p가 가리키는 위치 뒤에 x를 삽입한다.
fl.splice_after(p,k);	p가 가리키는 위치 뒤에 k의 모든 원소를 삽입한다.
fl.splice_after(p,k,q);	p가 가리키는 위치 뒤에 k의 q가 가리키는 원소를 삽입한다.
fl.splice_after(p,k,b,e);	p가 가리키는 위치 뒤에 k의 반복자 구간 [b,e)에 포함된 원소를 삽입한다.

forward_list::before_begin을 제외하면 모두 list의 내장 함수 뒤에 _after가 붙은 것들이다. _after가 붙지 않은 함수와의 차이는 원소들의 삽입/삭제가 일어나는 시작 위치이다. _after가 붙은 함수들은 p가 가리키는 위치 뒤부터 삽입/삭제가 일어나기 때문에, 이 함수들에서 맨 앞의 원소에 접근할 수 있게 하기 위해서 forward_list::before_begin 함수가 존재한다.

 

→ solved.ac tag: linked_list