삽입·삭제가 어디서 반복되는지로 넘어갑니다.
조회 비율과 수정 위치로 후보를 줄인다
시간복잡도 표를 외우기보다, 아래 질문을 순서대로 통과시키면 배열, 리스트, 덱 중 무엇을 먼저 검토할지 빠르게 정할 수 있습니다.
질문 1
랜덤 조회가 지배적인가?
인덱스 접근이나 순차 순회가 반복되는지 봅니다.
YES
배열 우선
O(1) 접근과 캐시 친화성이 병목을 줄입니다.
NO
수정 위치 확인
질문 2
수정이 앞/뒤에 몰리는가?
큐, 슬라이딩 윈도우, 앞삽입 로그를 확인합니다.
YES
덱 후보
양끝 삽입·삭제가 반복되면 이동 비용이 작습니다.
NO
중간 위치 확인
중간 수정이면 위치를 이미 아는지가 핵심입니다.
질문 3
중간 노드를 이미 아는가?
탐색 비용 없이 링크만 바꿀 수 있는지 확인합니다.
YES
리스트 후보
연결 변경이 많을수록 이동 비용을 줄입니다.
NO
배열 재검토
탐색 O(N)이 크면 리스트 장점이 사라집니다.
배열
조회와 순회 중심
랜덤 접근, 순차 반복, 작은 구현 비용이 중요할 때.
리스트
위치를 아는 중간 변경
탐색 없이 링크 변경만 반복할 수 있을 때.
덱
양끝 삽입·삭제
앞뒤 변경이 많고 중간 접근이 적을 때.