배열(Array)과 연결 리스트(Linked List)는 조회 및 삽입·삭제 비용이 어떻게 다른가요?

이렇게 답해 보세요 (핵심 답변)

고전적인 연속 배열은 인덱스로 즉시 위치를 계산해 조회가 O(1)이지만, 중간 삽입·삭제에는 뒤쪽 요소를 밀고 당기는 O(n) 이동 비용이 듭니다. 반면 연결 리스트는 원하는 위치를 찾아가는 순차 탐색에 O(n)이 걸리지만, 대상 노드의 참조를 이미 알고 있다면 포인터 연결만 바꾸는 O(1) 갱신이 가능합니다. 다만 자바스크립트의 Array는 동적 크기와 희소 요소를 허용하는 객체여서 C 언어처럼 고정된 연속 메모리 배열이라는 언어 차원의 보장은 없습니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 단일 연결 리스트는 다음 링크만 두고, 이중 연결 리스트는 이전·다음 링크를 함께 두어 메모리를 더 쓰는 대신 역방향 이동과 노드 삭제를 쉽게 만듭니다.
2. 연결 리스트의 중간 삽입 비용을 말할 때는 그 위치까지 찾아가는 탐색 비용 O(n)과 포인터 수정 비용 O(1)을 나누어 설명해야 정확합니다.

면접에서 자주 하는 실수

대상 노드를 찾는 탐색 과정을 빼먹고 연결 리스트의 모든 삽입·삭제가 무조건 O(1)이라고 말하면 안 됩니다.