연속 공간 vs 노드 연결
배열은 인덱스와 캐시에 강하고, 리스트는 노드 참조가 있을 때 연결 변경이 빠릅니다.
구조 선택 전, 세 축을 먼저 고정한다
저장 방식, 연산 비용, 경계 입력을 함께 보면 “삭제가 많으니 무조건 리스트” 같은 선택 실수를 줄일 수 있습니다.
탐색 비용까지 합산
삽입·삭제가 O(1)이어도 위치를 찾는 데 O(N)이 들면 이득이 사라질 수 있습니다.
큰 N에서 다시 계산
N=200000 같은 입력에서는 한 번의 이동·탐색이 누적되어 시간 초과가 됩니다.
오답 패턴
삭제가 많으면 리스트?
삭제할 위치를 매번 처음부터 찾는다면 리스트도 매 연산 O(N)입니다. “위치를 이미 알고 있는가”가 핵심 조건입니다.
조회 중심
랜덤 접근이 많으면 배열을 우선 후보로 둡니다.
수정 중심
앞/뒤 수정은 덱, 위치를 아는 중간 수정은 리스트를 봅니다.
반례 확인
큰 입력에서 탐색 횟수와 이동 원소 수를 숫자로 셉니다.
자료구조 이름보다 “위치를 찾는 비용 + 실제 변경 비용”의 합이 작아지는 선택이 정답입니다.