Access
임의 인덱스 조회가 많으면 배열이나 벡터 쪽이 유리합니다.
구조 선택 기준
배열 리스트 실무 선택 기준표
문제의 연산 분포를 먼저 세고, 자료구조의 비용과 구현 안정성을 함께 비교합니다.
선택 순서
Insert
앞이나 중간 삽입이 많으면 이동 비용과 링크 조작 비용을 비교합니다.
Delete
삭제 위치를 이미 알고 있는지, 찾아야 하는지에 따라 결과가 달라집니다.
Memory
연속 메모리의 캐시 장점과 노드 포인터 오버헤드를 함께 봅니다.
Mix
연산 비율이 섞이면 작은 입력으로 후보 구조를 빠르게 검증합니다.
구조별 신호
Array
조회와 순회가 중심이고 크기 변화가 적으면 가장 단순하고 빠릅니다.
Vector
뒤 삽입은 편하지만 중간 삽입은 원소 이동을 피하기 어렵습니다.
List
노드 위치를 알고 있으면 삽입과 삭제가 빠르지만 탐색은 느립니다.
Deque
양끝 삽입과 삭제가 많으면 배열과 리스트 사이의 대안이 됩니다.
Hybrid
정렬, 인덱스, 빈도표 같은 보조 구조를 붙이면 기본 구조의 약점을 줄일 수 있습니다.
자료구조 선택은 이름이 아니라 입력에서 실제로 반복되는 연산의 비율로 결정하세요.