리스트를 구현하려면 포인터를 가지고 있어야 하고, new와 delete 연산자를 이용해 메모리를 할당하고 해제할 수 있어야 한다.
list1.sort(std::greater<int>()); //기본은 less<value_type>
이중 연결리스트
노드로 구현
front 첫번째 원소
back 마지막 원소
size 크기
capacity는 없다. vector와 다르게
[] 임의 접근도 없다. 노드에서 포인터로 다음 노드 가리키니까
begin 맨 앞의 원소를 가리키는 iterator 반환
end 맨 뒤의 원소의 다음을 가리킨느 iterator 반환
insert(it,k) iterator로 삽입할 위치 지정. 삽입한 원소 위치 iterator로 반환
push_back(), pop_back()
erase iterator로 삭제
pop_front
remove(10) 10을 모두 삭제
list의 반복자는 양방향으로 이동할 수 있어서 양방향 반복자라고 부른다. 반복자를 이용하여 특정 위치로 이동하는 작업은 선형시간 복잡도를 가진다.
vector의 경우에 메모리 재할당을 한 경우 기존의 반복자와 포인터, 참조는 무효화 된다. 하지만 list는 그럴 걱정이 없다.
여러 메모리 블록 할당. 필요시 메모리 블록 추가
vector 처럼 기존의 것 삭제하고 새로 만들지 않음
중간에서 삽입되거나 삭제되면 데이터들의 이동이 발생
(벡터와 달리 앞으로 늘어나거나 뒤로 늘어난다. 데이터가 적은 쪽)
[]를 사용해 임의 접근 가능
임의 접근 반복자