배열보다 연결 리스트를 사용하는 기준은 무엇인가?

데이터의 추가와 삭제가 빈번하게 일어날 때다. 인덱스로 접근하지 않고 순차적으로 탐색해도 무방한 환경에서 유리하다.

배열은 연속된 메모리 공간을 사용한다. 삽입이나 삭제 시 나머지 요소를 모두 이동시켜야 하므로 비용이 크다.

반면 연결 리스트는 노드가 흩어져 있다. 앞뒤 노드의 주소값만 바꿔주면 되므로 데이터 이동 없이 빠르게 처리한다.

최근 CPU 캐시 지역성 때문에 단순 탐색은 배열이 대개 빠르다. 무작정 리스트를 쓰기보다 데이터 변경 빈도를 먼저 따져야 한다.