배열이 직접 접근에 강하다
몇 번째 원소인지 자주 묻는 문제는 링크를 따라가는 리스트보다 배열이 단순하고 빠릅니다.
배열과 리스트 선택 기준표
배열과 리스트의 차이는 자료 이름보다 연산 분포에서 결정되므로 조회, 삽입 위치, 순회 방식을 따로 놓고 봅니다.
리스트는 이동 축소
원소 자체를 밀지 않아도 되지만, 원하는 위치를 찾는 탐색 비용은 여전히 남습니다.
캐시 locality도 고려
전체를 차례대로 훑는 작업은 배열의 연속 저장이 실제 성능에서 유리할 수 있습니다.
제출 전 남길 증거
배열 선택
조회와 구간 처리 비율이 높고 크기 변화가 적을 때 우선합니다.
리스트 선택
이미 위치를 알고 있는 노드 주변 변경이 많을 때 후보가 됩니다.
혼합 판단
입력 크기가 작으면 구현 단순성이 성능 차이보다 중요할 수
있습니다.