1. List란
List는 C++ STL에서 제공하는 양방향 연결 리스트(double linked list)로 구현된 컨테이너이다. List는 STL에서 시퀀스 컨테이너 중 하나로, vector와 달리 메모리 할당이 연속적으로 이루어지지 않는다.
2. 특징
- 임의의 위치에서의 삽입 및 삭제가 O(1)의 시간 복잡도를 가진다.
- 연속적인 메모리 공간을 필요로 하지 않기 때문에 삽입 및 삭제가 빈번한 경우 vector보다 성능이 우수하다.
- 순차적으로 접근하는 경우 vector보다 성능이 떨어진다.
- 노드에 대한 포인터를 포함하고 있기 때문에 메모리 사용량이 vector보다 크다.
- 반복자를 통해 원소에 접근할 수 있으며, 양방향 반복자를 제공한다.
3. 장단점
장점 :
- 임의의 위치에서의 삽입 및 삭제가 O(1)의 시간 복잡도를 가진다.
- 연속적인 메모리 공간을 필요로 하지 않기 때문에 삽입 및 삭제가 빈번한 경우 vector보다 성능이 우수하다.
- 양방향 반복자를 제공하므로 양쪽 방향으로 순회가 가능하다.
단점 :
- 순차적으로 접근하는 경우 vector보다 성능이 떨어진다.
- 노드에 대한 포인터를 포함하고 있기 때문에 메모리 사용량이 vector보다 크다.
- 임의의 위치에서의 삽입 및 삭제가 O(1)의 시간 복잡도를 가지지만 실제로는 메모리 할당 및 해제가 빈번하게 일어나기 때문에 vector보다 느릴 수 있다.
4. 시간복잡도
- 접근 - O(n)
임의 원소 접근: List는 양방향 연결 리스트로 구현되어 있기 때문에 임의의 원소에 접근하는 데 O(n)의 시간복잡도가 소요된다. 이는 vector와 달리 메모리 할당이 연속적으로 이루어지지 않기 때문이다.- 검색 - O(n)
검색: List는 연결 리스트로 구현되어 있기 때문에 검색하는 데 O(n)의 시간복잡도가 소요된다.- 삽입 및 삭제 - O(1)
삽입 및 삭제: List는 양방향 연결 리스트로 구현되어 있기 때문에 임의의 위치에서의 삽입 및 삭제가 O(1)의 시간 복잡도를 가진다. 실제로는 메모리 할당 및 해제가 빈번하게 일어나기 때문에 vector보다 느릴 수 있다는 단점이 있지만, vector보다는 삽입 및 삭제에 더 빠른 성능을 보인다.
5. 사용법
1) 초기화
list<int> myList; // 빈 리스트 생성 list<int> myList = {1, 2, 3, 4}; // {1, 2, 3, 4}를 원소로 갖는 리스트 생성 list<int> myList1 = {1, 2, 3, 4}; list<int> myList2(myList1); // myList1을 복사하여 myList2 생성 vector<int> vec = {1, 2, 3, 4, 5}; list<int> myList(vec.begin(), vec.end()); // 벡터 vec의 원소를 myList에 복사 class MyClass { public: MyClass() : myList({1, 2, 3, 4}) {} private: std::list<int> myList; }; // 생성자 member initializer list를 이용하여 초기화하기2) 멤버 함수
Iterators
begin() : 첫 번째 원소를 가리키는 반복자를 리턴한다.
cbegin() : 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
end() : 마지막 원소를 가리키는 반복자를 리턴한다.
cend() : 마지막 원소를 가리키는 상수 반복자를 리턴한다.
rbegin() : 역 순차열의 첫 번째 원소를 가리키는 반복자를 리턴한다.
crbegin() : 역 순차열의 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
rend() : 역 순차열의 마지막 원소를 가리키는 반복자를 리턴한다.
crend() : 역 순차열의 마지막 원소를 가리키는 상수 반복자를 리턴한다.Element access
front() : 첫 번째 원소의 참조를 리턴한다.
back() : 마지막 원소의 참조를 리턴한다.Capacity
empty() : 원소 존재 유무를 체크한다. 아무것도 없으면 true, 있으면 false를 리턴한다.
size() : 원소의 개수를 리턴한다.
max_size() : 담을 수 있는 원소의 최대 개수를 리턴한다.
resize(size, value) : list의 크기를 변경하고 default 값이나 임의 값으로 초기화한다.Modifiers
clear() : list의 모든 원소를 제거한다.
assign() : 기존 원소들은 모두 제거 후, 임의 값으로 n개의 원소를 할당한다.
assign(iter1,iter2) : iter1부터 iter2까지의 데이터 할당
assign(size,value) : size개의 value를 리스트에 삽입
insert(iter, args) : 임의 위치에 임의 값을 삽입한다.
emplace(iter, args) : 원소 삽입시 컨테이너 내부에서 생성 후 임의 위치에 임의 값을 삽입한다.
erase() : 임의 위치의 원소나 지정 범위의 원소를 삭제한다.
erase(iter1,iter2) : 1~2범위 삭제
erase(iter) : 해당 위치 삭제
push_front() : list의 처음에 원소를 추가한다.
emplace_front() : 원소 삽입시 컨테이너 내부에서 생성 후 컨테이너의 처음에 원소를 추가한다.
pop_front() : list의 처음 원소를 제거한다.
push_back() : list의 끝에 원소를 추가한다.
emplace_back() : 원소 삽입시 컨테이너 내부에서 생성 후 컨테이너의 끝에 원소를 추가한다.
pop_back() : list의 마지막 원소를 제거한다.
swap() : list1.swap( list2 )일때 list1과 list2를 swap한다.List operations
merge() : list1.merge( list2 )일때 list1에 list2를 정렬하면서 병합한다.
splice() : 2개의 list 중 인자로 주어지는 list의 지정된 원소들을 대상 list로 이동시킨다.
remove() : 인자로 받은 값으로 받은 값과 같은 값의 원소를 모두 제거한다.
remove_if() : 함수객체의 조건을 만족하는 원소를 모두 제거한다.
reverse() : list에 담긴 원소의 순서를 역순으로 바꾼다.
unique() : list에 담긴 원소 중 연속적으로 중복된 값이 배치된 원소를 제거한다.
sort() : list에 담긴 원소를 정렬한다. 예 : list.sort( std::greater<int>() )
