c++ list (stl)
-list란?
노드들이 포인터를 통해 서로 양방향 포인터로 연결된 형태의 자료구조이다.
검색 시간은 오래걸리지만 삽입,삭제는 빠르다는 장점을 갖고 있다.
-헤더파일
#include<list>
-생성
1)default 생성자:
list<data_type> li;
비어있는 list를 생성
2) 크기 지정 생성자:
list<data_type> li(4);
노드수가 4인 vector 생성 원소들은 0으로 초기화 된다.
3)크기와 초기화 쌍 생성자:
list<data_type> li (4,100);
노드수가 4이며 모두 100으로 초기화
4) 다른 list의 원하는 범위 지정 생성자:
list<data_type> li(first_iterator , last_iterator);
다른 list의 복사 하기를 원하는 시작 위치와 끝 위치의 다음 iterator를 매개변수로 전달하여 li에 복사
5) 다른 vector 통째로 복사시키는 생성자
list<data_type> li (a);
list a를 그대로 li에 복사
-함수
1)begin():
시간복잡도:O(1)
시작 위치를 가리키는 정방향 iterator 반환
2)end():
시간복잡도:O(1)
마지막 요소 다음 위치(맨 마지막 요소 다음)를 가리키는 정방향iterator 반환
3)rbegin():
시간복잡도:O(1)
끝 요소를 가리키는 역방향 iterator 반환
4)rend():
시간복잡도:O(1)
시작 요소 전 위치를 가리키는 역방향 iterator 반환
*정방향 iterator와 역방향 iterator의 차이를 모른다면 여기로https://zero-stone.tistory.com/22
5)assign()
시간복잡도:O(N)
기존 list의 원소들을 새로운 원소들로 대체한다.
2가지 유형이 존재
첫번째> void assign (원소갯수, 초기값)
두번째> void assign ( first_iterator, last_iterator)
*frist_iterator, last_iterator은 포인터도 가능
6)back():
시간복잡도:O(1)
가장 맨 뒤에있는 (참조)값을 리턴
7)front():
시간복잡도:O(1)
가장 맨 앞에있는 (참조)값을 리턴
8) clear():
시간복잡도:O(N)
list에 있는 모든 노드 삭제
9)size():
list에 저장된 노드 갯수 리턴
10) empty():
시간복잡도:O(1)
list가 비어있으면 1을 리턴 아니면 0을 리턴
11)max_size():
시간복잡도:O(N)
int max_size()
list가 가질 수 있는 최대 노드수 리턴
12)erase:
시간복잡도:O(N)
원하는 위치의 iterator를 매개변수로 넘겨주면 해당 위치 요소 제거한다.
중간 값을 없애도 자동적으로 list를 조절해 연결 구조를 유지한다.
*2가지 유형
->첫번째= iterator erase(iterator) iterator가 가리키는 위치 원속 삭제
->두번째= iterator erase(iterator first , iterator last) first~last직전원속들 삭제
삭제된 노드의 전방 노드 iterator를 반환
13) remove:
시간복잡도:O(N)
void remove ( type value)
list내 value를 값으로 갖는 노드를 모두 삭제
14) remove_if:
시간복잡도:O(N)
void remove_if (함수명)
list내 조건을 만족하는 노드를 모두 삭제
함수가 true 를 반환 하는 조건에 해당하는 노드를 모두 제거
참조)https://www.cplusplus.com/reference/list/list/remove_if/
13) insert(3가지 유형):
매개변수로 전달한 iterator 위치 전방에 노드를 삽입
시간복잡도=O(N)
첫번째> iterator insert (iterator position , type& val)
position위치에 val을 값으로하는 노드 삽입
ex) v.insert( it , 5 );
두번째> void insert (iterator position , int n , type& val)
position위치에서 부터 n개의 val을 값으로 하는 노드 삽입
ex) v.insert( it , 10 , "abc" );
세번째> void insert (iterator position , iterator first , iterator last)
position위치에서 부터 first~last이전 노드들을 삽입
ex) v.insert( it , it_1 , it_2 );
*first와 last위치에는 포인터도 가능.
14) push_back & push_front:
시간복잡도=O(1)
void push_back (type value);
void push_front (type value);
list 맨뒤(앞)에 노드 추가
15) pop_back & push_front:
시간복잡도=O(1)
void pop_back();
void pop_front();
list 맨뒤(앞) 노드 삭제
16) reverse:
시간복잡도=O(N)
void reverse()
list를 순서를 반전시킨다.
1->2->3 순이였다면
3->2->1 순으로
17) resize:
시간복잡도=O(N)
void resize ( int n , type value)
list의 크기를 n으로 만든다.
만약 n이 현재 size보다 작으면 n+1번째 노드부터는 없앤다.
n이 현재 size보다 크면 value부분을 생략한 경우 n-size개를 0을 값으로 갖는 노드로 채우고
value를 지정해주면 해당 n-size개를 value로 값으로 갖는 노드로 채운다.
( 2번째 매개변수는 생략 가능)
18) merge:
시간복잡도=O(N)
void merge (list &x, Compare comp);
정렬된 2개의 list를 병합하는 함수이다.
(정렬 안돼있으면 에러리턴, Compare comp는 비교함수 생략시 오름차순)
19) sort:
시간복잡도: O(N logN)
void sort( 함수명)
함수가 true를 리턴하는 조건에 따라서 정렬한다.
결과:
5
3
1
19) splice:
void splice (iterator position , list& x , iterator first , iterator last);
첫번째> void splice ( position , x) 시간복잡도=O(옮기는 수)
li.splice(it ,x)
li의 it위치서 부터 x의 모든 노드를 옮긴다. x의 모든 노드는 삭제된다.
두번째> void splice ( position , x , it) 시간복잡도=O(옮기는 수)
li.splice( it , x , it_1)
x에서 it_1위치 부터 쭉 li의 it위치에서 부터 쭉 옮긴다. x의 it위치 부터 쭉 삭제
세번째> void splice ( position, x, first ,last) 시간복잡도=O(N)
x의 first~last이전 것들 옮기고 삭제
20) unique:
시간복잡도=O(N)
-void unique()
-void unique( 함수명)
list내 중복된 value를 제거한다.
매개변수로 함수를 전달하면 해당 조건을 만족하는 노드들에만 적용한다.