[자료구조] 배열 Array

배열이란?

같은 타입의 데이터 요소들을 연속된 메모리 공간에 저장하는 자료구조이다.각 요소들은 index를 통해 접근할 수 있다.

 

배열의 주요 특징

배열의 각 요소는 0부터 시작하는 인덱스 번호를 갖는다. -> 첫 번째 원소가 저장된 위치에서 X번째 떨어진 원소에 접근하겠다는 의미와 같다. offset 개념으로 사용된다.

 

배열의 요소들은 메모리 상에서 연속적으로 할당된다. -> 인덱스를 통한 빠른 접근이 가능한 이유!

 

배열 선언 시, 기본적으로 크기는 고정된다.

 

하나의 배열은 일반적으로 같은 데이터 타입의 요소만 저장할 수 있다.

 

 

배열의 주요 연산에 대한 시간복잡도는 다음과 같다.1. 접근: O(1), 인덱스를 통한 직접 접근2. 검색: O(n), 정렬되지 않은 배열에서의 선형 탐색3. 삽입: O(n), 최약의 경우(배열의 처음에 삽입)4. 삭제: O(n), 최악의 경우(배열의 처음에서 삭제)

 

배열의 장단점

장점

인덱스를 통한 O(1)의 시간복잡도로 직접 접근이 가능하다.연속된 메모리 할당으로 캐시 지역성을 활용한다.

단점

기본 배열은 크기 변경이 어렵다.삽입과 삭제에서 요소의 이동이 필요하기 때문에 O(n)의 시간복잡도를 갖는다.미리 할당된 크기보다 적은 요소를 저장할 경우 메모리를 낭비한다.

 

배열이 요소의 위치를 계산하는 방법?

 

요소가 저장된 위치는 Base Address + Offset으로 계산된다.

Base Address는 배열의 첫 번째 원소의 메모리 주소이고, Offset은 배열의 첫 번째 원소와 다른 원소의 위치 차이이다.

 

 

동적 배열이란?

일반적인 배열과 달리 크기가 변할 수 있는 배열이다.

동적 배열은 프로그래밍 언어 자체에서 지원되며, 내부적으로는 정적 배열을 사용하여 동작한다.

C++에서는 Vector, Java에서는 ArrayList로 구현되어 있다.

 

사이즈가 초과될 때 데이터를 어떻게 추가하는지?

 

Java에서 별도 메모리 사이즈 지정 없이 ArrayList를 생성하면 기본 사이즈는 10이다.

 

데이터를 추가할 때 메모리 공간이 남는다면 배열 끝 부분에 차례대로 추가되지만,

메모리가 꽉 찬 상태라면 동적 배열은 더 큰 메모리 사이즈를 할당한 새로운 배열을 만들어 기존 데이터를 모두 옮기고 그 뒤에 이어 데이터를 추가한다.