1.7 std::list

std::forward_list의 단점: 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능을 제공하지 않는다.

 

std::list

양방향 연결 리스트. 이중 연결 리스트다. 

 

std::list멤버 함수

insert()

emplace()

push_back()

emplace_back()

pop_back()

[참고] std::forward_list와 std::list의 push_front(), insert(), pop_front(), erase() 함수의 시간 복잡도는 같지만, 실제로는 list가 두배의 연산을 수행해야한다. 이중 연결 리스트는 한 노드에 두 개의 포인터를 갖고 있기 때문!

#include <iostream>
#include <list>
int main(){
	std::list<int> list0 = {1, 2, 3};
	//원소 삽입
	list0.push_back(4);	// {1, 2, 3, 4}
	list0.insert(next(list0.begin()), 0);	// {1, 0, 2, 3, 4} 
	list0.insert(list0.end(), 5);	// {1, 0, 2, 3, 4, 5}
	//원소 삭제
	list0.pop_back();	// {1, 0, 2, 3, 4}
}

 

iterator

양방향 반복자(bidirectional iterator):

역방향 연산 가능. 그러나 순차적 접근만 가능. -> 선형 시간 복잡도