[Data Structure] Vector 와 List의 차이

Vector

• 연속적인 메모리 공간에 저장
• 동적임
• 삽입 삭제가 중간에서 발생할 시 원소를 옮겨줘야함
• 접근 O(1)
• 원소 변경시 iterator 변화
• 선할당이 발생(size와 capacity 값이 다른 이유)
• 메모리 할당은 미리 하기 때문에 LIST 보다 빠름(push_back은 list 보다 빠름)

List

• Doubly Linked List로 구현
• 원소 접근이 느림O(n)
• list 중간에 삽입 삭제하는 것은 vector 보다 빠름
• 원소가 변경되도 iterator 동일