데이터를 저장할 때 연속된 공간에 몰아넣을 것인가(Array), 아니면 흩어진 공간을 연결할 것인가(Linked List)? 이 선택에 따라 프로그램의 성능은 극명하게 갈린다.
두 구조의 물리적 배치와 성능 특성을 분석한다.
메모리 구조의 대조
-
배열 (Array): 메모리의 연속된 공간을 점유한다.
인덱스를 통한 직접 접근(O(1))이 가능한 것이 최대 강점이다. -
연결 리스트 (Linked List): 불연속적인 공간에 데이터를 노드 단위로 배치한다.
각 노드는 다음 노드의 주소를 저장하여 논리적으로 연결된다.
[ 배열 ] - 연속적 배치
주소: 1000 1004 1008 1012
데이터: [ 10 ][ 20 ][ 30 ][ 40 ]
[ 연결 리스트 ] - 포인터 연결
Node1(1000) -> [ 10 | Next: 2050 ]
Node2(2050) -> [ 20 | Next: 1500 ]
Node3(1500) -> [ 30 | Next: NULL ]
시간 복잡도와 효율성
| 작업 유형 | 배열 | 연결 리스트 |
| :— | :— | :— |
| 조회 (Access) | O(1) | O(N) |
| 삽입/삭제 (Middle) | O(N) | O(1) (탐색 제외) |
배열은 조회 성능이 뛰어나지만 중간 데이터 삽입 시 요소 이동 오버헤드가 발생한다.
연결 리스트는 탐색이 느린 대신 링크 변경만으로 삽입/삭제를 처리할 수 있어 유연하다.
캐시 효율성과 선택 기준
배열은 물리적 인접성 덕분에 CPU 캐시 히트율이 높다.
데이터 크기가 고정적이고 조회가 빈번하다면 배열이, 데이터 규모 변화가 심하고 삽입/삭제가 잦다면 연결 리스트가 적합하다.
P.S
완벽한 자료구조는 존재하지 않는다.
해결하려는 문제의 주된 작업 패턴을 분석하여 메모리 효율성과 처리 속도 사이의 최적점을 찾는 설계가 필요하는 것 같다.
