[DataStructure] Array, Dynamic Array, Associative Array

이미지 출처: https://images.shiksha.com/mediadata/ugcDocuments/images/wordpressImages/2022_05_Arrays-in-Java-1.jpg

Array(배열)

• 배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료 구조이다.
• 각 데이터는 인덱스로 접근 가능하며, 인덱스는 배열에서 오프셋 개념으로 이해된다.
• 인덱스는 0부터 시작하여 각 원소에 대한 위치를 가리킨다.
• 데이터는 연속된 메모리 공간에 할당되며, 인덱스는 해당 위치를 가리킨다.
• 이러한 동작 원리로 배열은 같은 타입의 데이터를 메모리에 연속적으로 저장한다.
• 2차원 배열은 메모리상 1차원으로 표현되며, 각 행은 메모리 주소로 구성됨.
• 연속적인 메모리 공간으로 데이터를 저장하면 CPU 캐시를 통해 데이터 접근 시간을 단축할 수 있음.

객체를 배열에 저장하는 경우

• 객체 배열은 각 객체의 레퍼런스를 연속적인 메모리 공간에 저장하고, 실제 객체들은 메모리에 띄엄띄엄 저장됨.

Dynamic Array(동적 배열)

• Dynamic Array(동적 배열)은 크기가 변할 수 있는 Array 구조로, 데이터 추가 및 삭제가 가능하며 리스트 등 다양하게 불림.
• Dynamic Array는 크기를 동적으로 조절하며 동작한다. 데이터 추가 시 공간 부족 시 현재 배열 크기를 두 배로 늘리고 데이터를 복사하여 채운다.

Associative Array(연관 배열)

• Associative Array(연관 배열)는 key-value 쌍을 저장하는 ADT(Abstract Data Type)로, 같은 key를 가지는 pair는 최대 한 개만 존재한다.
• 'map' 또는 'dictionary'로 불리며, 파이썬의 dictionary가 이 Associative Array를 구현했다고 볼 수 있다.

ADT(Abstract Data Type)?

• 어떻게 동작해야 하는지만 명시한 타입으로, 구현이 되어있지 않다.

참고

• https://youtu.be/Hpg6zS0Nq28?si=AfDaY8kOOfgyIF1x