특징
#include <list>- 이중 연결 리스트(doubly linked list) 구조
- Heap 영역에 동적할당
- 각 노드가 데이터와 다음 노드의 포인터를 저장
- 리스트의 각 요소는 포인터로 연결되어 있어 메모리상으로 연속적이지 않아도 됨
| 장점 | 단점 | |
| 속도 | 삽입, 삭제 O(1) | 임의 접근이 불가능하므로 순차적 접근 O(n) |
| 메모리 | 크기가 가변적이므로 배열에 비해 메모리 효율 좋음 |
링크 하나에 4byte인데 양방향이므로 8byte가 추가로 필요함 배열에 비해 메모리 사용량이 많음 |
생성
| 설명 | 코드 |
| 리스트 생성 | list<int> lt |
| N개의 0을 가진 리스트 생성 | list<int> lt(N, 0) |
| lt2을 복사한 리스트 생성 | list<int> lt(lt2) |
참조 및 반복자
| 설명 | 코드 |
| 첫번째 원소 참조 | lt.front() *lt.begin() |
| 마지막 원소 참조 | lt.back() |
| 첫번째 원소의 주소값 | lt.begin() |
| 마지막 원소의 다음 주소값 | lt.end() |
| 마지막 원소의 주소값을 시작점으로 설정 | lt.rbegin() |
| 첫번째 원소의 주소값을 끝점으로 설정 | lt.rend() |
수정자
| 설명 | 코드 |
| N개의 0을 리스트에 할당 | lt.assign(N, 0) |
| i번째 위치에 0을 삽입 | lt.insert(i ,0) |
| iter가 가리키는 원소를 제거 | lt.erase(iter) |
| 첫번째 원소 앞에 0을 삽입 | lt.push_front(0) |
| 마지막 원소 뒤에 0을 삽입 | lt.push_back(0) |
| 첫번째 원소 제거 | lt.pop_front() |
| 마지막 원소 제거 | lt.pop_back() |
| lt와 lt2의 원소를 교환 | lt.swap(lt2) |
| 모든 원소 제거 | lt.clear() |
크기
| 설명 | 코드 |
| 리스트의 크기 반환 | lt.size() |
| 크기를 N개로 재할당 ※ 크기가 더 커지면 0 할당 |
lt.resize(N ,0) |
| 리스트가 비어있으면 True, 아니면 False를 반환 | lt.empty() |
연산
| 설명 | 코드 |
| 오름차순 정렬 | lt.sort() |
| 순서를 거꾸로 뒤집음 | lt.reverse() |
| 인접한 원소가 같으면 중복된 값을 삭제하여 유일하게 함 | lt.unique() |
| k와 같은 원소 모두 제거 | lt.remove(k) |
| 단항 조건자 predicate에 해당하는 원소 모두 제거 | lt.remove_if(predicate) |
| lt의 iter가 가리키는 곳에 it2의 모든 원소를 잘라 붙임 | lt.splice(iter, lt2) |
| lt의 iter가 가리키는 곳에 lt2의 iter2가 가리키는 원소를 잘라 붙임 | lt.splice(iter, lt2, iter2) |
| lt의 iter가 가리키는 곳에 lt2의 [iter2_1, iter2_2] 범위의 원소를 잘라 붙임 | lt.splice(iter, lt2, iter2_1, iter2_2) |
| lt 내부로 lt2를 합병 정렬 | lt.merge(lt2) |