[Data Structure & Alogrithm] Array

📝Array

📌 핵심 요약

"배열은 같은 Type의 데이터 여러개를 저장하기 위한 자료구조다. 원소들의 논리적 순서와 물리적 순서가 같기 때문에 index로 상수시간에 원소에 접근할 수 있다. 또한 배열의 원소들은 메모리의 연속된 공간에 저장되기 때문에 캐시 효율성이 높아 빠르다."

📌 설명

• 배열은 같은 Type의 데이터 여러개를 저장하기 위한 자료구조이다.

• 원소들의 논리적 순서와 물리적 순서가 같다.

• 배열의 원소들은 메모리의 연속된 위치에 저장된다. (캐시의 효율성과 직결)

⚔️ 배열의 장점

◾ 배열의 데이터들은 메모리에 연속적으로 저장된다. 따라서 locality로 인한 cache hit rate가 높아서 데이터 처리가 빠르다.

◾ 연결 리스트는 데이터가 메모리에 연속적으로 저장되지 않는다. 따라서 locality가 보장되지 않고 cache hit rate배열에 비해 낮다.

📌 시간 복잡도

• 탐색 O(1) : index를 통해 상수 시간에 원소에 접근할 수 있다. (Random Access)
• 삽입 O(N) : 원소를 삽입하기 위해 배열내 원소들을 하나씩 뒤로 shift 해줘야한다.
• 삭제 O(N) : 원소를 삭제한 후에 뒤에 있는 원소들을 하나씩 앞으로 shift 해줘야한다.