[자료구조] 배열이란 무엇인가?

---

☑️ 배열이란 무엇인가?

배열은 연속된 자료구조(Contiguous Data Structures)를 가지는 대표적인 예시다. 연속된 자료구조는 단일 메모리 청크에 모든 원소를 저장하며, 모든 원소의 접근 소요 시간은 일정하게 O(1)을 가진다. 또, 연속된 자료구조의 특징으로 캐시 지역성(Cache Locality)이 있는데, 이는 연속된 자료구조의 특성 상, 원소와 원소가 인접하기 때문에 주변 원소에 접근할 때 빠르게 접근할 수 있도록 원소 하나를 가져올 때, 주변 원소를 캐쉬(Cache)에 가져오는 것이다.

 

위의 설명한 특성들로 인해서 배열의 원소들은 각자 같은 크기의 메모리 공간을 가지는데, 이 공간들은 연속성을 가진다. 그렇기 때문에 다음과 같은 수식을 통해서 인덱스의 위치를 찾을 수 있다.

배열 원소가 가지는 메모리 공간 : b
첫 번째 원소의 메모리 위치 : a
첫 번째 원소의 Index : s
주소를 찾고자 하는 원소의 Index : i

🟧 찾는 원소의 시작 메모리 주소

a + b( i - s )
= 첫 번째 원소의 메모리 위치 + 원소의 메모리 공간(주소를 찾고자 하는 원소의 Index - 첫 번째 원소의 Index)

 

🟧 찾는 원소의 끝 메모리 주소

a + b( i - s + 1 ) - 1
= 첫 번째 원소의 메모리 위치 + 원소의 메모리 공간(주소를 찾고자 하는 원소의 Index - 첫 번째 원소의 Index + 1) - 1

 

 

🔍 내 생각에는..

참고했던 책에서 설명한 배열은 시작 인덱스가 0이 아니라, 1으로 시작되는 경우도 염두한 것 같다. 만약에 0에만 한정된다면 아래의 사진을 예로 들고 다음과 같은 공식이 가능하다.

🟧 찾는 원소의 시작 메모리 주소

시작 주소 + (배열 원소의 크기 * 찾는 인덱스)

 

🟧 찾는 원소의 끝 메모리 주소

시작 주소 + (배열 원소의 크기 * 찾는 인덱스) - 1