자료구조 선택 기준

연산 분포가 배열과 리스트의 승부를 가른다

조회, 삽입 위치, 삭제 빈도를 한 표에 놓으면 배열·연결 리스트·deque 후보가 더 선명해집니다.

조회 우세

인덱스 접근 우선

임의 인덱스 접근과 캐시 지역성이 중요하면 연속 배열 후보를 먼저 둡니다.

중간 변경

위치 기반 갱신

반복자 위치를 이미 알고 있고 삽입·삭제가 잦으면 연결 구조 비용을 비교합니다.

양끝 작업

양끝 처리 후보

앞뒤 삽입·삭제가 몰리면 리스트보다 deque가 구현과 성능 균형을 줄 수 있습니다.

연산 비율
입력 로그 read, insert, erase 비율을 추정해 지배 연산을 먼저 고정합니다.
구현 위험 포인터 오류와 인덱스 이동 비용 중 어느 쪽이 더 큰지 비교합니다.
교체 기준 성능 병목이 바뀌면 자료구조와 순회 코드를 함께 회귀 테스트합니다.