참고: https://jhnyang.tistory.com/230
📋 벡터
: 동적 배열구조 클래스
👉 배열
: 같은 타입의 데이터를 연속된 공간에 나열하고 인덱스를 부여하는 것.
( 같은 타입인 이유 : 타입별로 메모리에 할당되는 크기가 다르기 때문에 )
👉 배열과 비교하기
-
같은 점
- 인덱스를 지원하여 임의의 요소에 O(1) 시간으로 접근이 가능하지만, 삭제하거나 추가할때는 재정렬 하므로 O(n)의 시간이 소요된다.
-
다른 점
- 배열과 달리 정의 후에 크기를 추가하거나 줄일 수 있다. (클래스이기 때문에 가능)
- 매번 size를 확인하여 배열이 꽉차게 되면 자동으로 용량을 늘린다. 이 과정에서 메모리를 해제했다가 다시 할당하고 값을 복사하게 됨 > 잦은 할당은 fragmentation 발생할 수 있음
👉 벡터의 장단점
-
장점 : 구현과 접근이 쉬움
-
단점 : 삽입, 삭제가 많은 경우 비효율적임
📋 리스트
: 순서가 있는 선형 객체의 집합으로 Stack, Queue, Tree, Graph 등의 자료구조 구현에 활용되는 기초 자료구조 이다.
👉 리스트 특징
- C++의 리스트는 double-linked-list 형태로, 시작과 마지막 원소의 위치만을 기억하고 접근하기 위해서는 링크를 따라가야한다.
(출처: https://modoocode.com/223)
👉 리스트 장단점
-
장점 : 삽입, 삭제가 빠름
-
단점 : 인덱스를 지원하지 않아 접근이 어려움
