배열 (Array)

배열 (Array)

동일한 타입의 데이터를 연속된 메모리 공간에 순차적으로 저장하는 선형 자료구조로, 인덱스를 통해 O(1) 시간에 임의 접근이 가능

목적: 임의 접근, 연속 메모리 활용, 캐시 효율, 고정 크기 데이터 저장

특징: 연속 메모리, 고정 크기, 인덱스 접근, 캐시 친화적

구성요소: 베이스 주소, 인덱스, 요소 크기, 길이

주소 계산: Address(A[i]) = Base + i × ElementSize

시간 복잡도

• •접근(Access): O(1)
• •검색(Search): O(n) - 순차, O(log n) - 정렬+이진탐색
• •삽입(Insert): O(n) - 중간, O(1) - 끝
• •삭제(Delete): O(n) - 중간, O(1) - 끝

공간 복잡도: O(n)

장점: 빠른 임의 접근(O(1)), 캐시 지역성, 메모리 효율, 간단한 구현

단점: 고정 크기, 삽입·삭제 비효율(O(n)), 메모리 낭비(미사용 공간)

적용사례: 정렬 알고리즘, 룩업 테이블, 행렬 연산, 버퍼

비교: 배열(연속/고정/O(1)접근) vs 연결 리스트(분산/동적/O(n)접근)

연관: 동적 배열, 다차원 배열, 인덱스, 메모리 레이아웃