배열과 리스트 선택 의사결정표
조회 비율과 수정 위치를 먼저 보고, 위치를 이미 알고 있는지와 반복 비용까지 확인해 후보를 추린다.
배열·리스트 선택 기준
배열
리스트
덱
조회 비율
랜덤 접근 중심
높을수록 유리
인덱스 O(1)
낮을 때 검토
탐색 O(N)
끝 접근 위주
중간 조회는 약함
앞/중간 삽입
이동 비용 확인
중간 이동 큼
반복되면 누적
노드 알면 유리
연결 변경 중심
앞뒤 삽입 후보
양끝 O(1)
삭제 위치
위치를 아는가
인덱스면 단순
뒤 원소 이동
노드 참조 필요
탐색이면 이득 감소
양끝 삭제 안정
중간 삭제는 비주력
반복 비용
캐시와 예측성
캐시 친화적
순회 비용 안정
포인터 비용
메모리 분산 가능
양끝 반복 안정
큐/슬라이딩 윈도우
조회가 지배적이면 배열
랜덤 조회, 순차 반복, 캐시 친화성이 핵심일 때 우선한다.
노드를 알면 리스트
중간 삽입/삭제가 많아도 위치 탐색 비용을 따로 계산한다.
양끝 수정이면 덱
앞뒤 삽입/삭제가 반복되면 배열보다 안정적인 후보가 된다.