[자료 구조] 동적 배열 vs 연결 리스트

동적 배열과 연결 리스트의 가장 큰 차이점은 삽입, 삭제, 임의 원소 접근에 드는 시간입니다.

삽입과 삭제를 할 일이 없거나, 배열의 끝에서만 삽입, 삭제를 하면 되는 경우, 동적 배열의 거의 항상 좋습니다.

임의 원소에 빠르게 접근할 수 있으며, 메모리에 연속적으로 배치되어 있기 때문에 CPU 캐시 효율이 높습니다.

 

특정 원소의 삭제가 빈번히 일어나는 경우에는 연결 리스트가 좋습니다.

 

비교 요약

특징	연결 리스트	동적 배열
이전 원소/ 다음원소 찾기	O(1)	O(1)
메모리 할당	필요할 때마다 동적 할당	초기 크기 할당 후 동적 증가
접근 속도	O(n)	O(1)
삽입/삭제 속도	O(1) (특정 위치)	O(n)
메모리 오버헤드	높음 (포인터 저장)	낮음
캐시 적중률	낮음	높음
구현 복잡성	높음	낮음