자료구조: 배열(Array)

 

배열(Array)

: 같은 종류의 데이터를 순서대로 저장하는 자료 구조

• 모든 프로그래밍 언어에서 기본적으로 제공하는 자료 구조

 

 

 

배열의 장단점

장점

• 읽기/쓰기와 같은 참조에는 O(1)의 성능을 가짐

 

단점

• 데이터 크기를 예측하거나 확정하기 어려워 메모리 낭비가 발생할 수 있음
• 데이터의 삽입, 삭제가 비효율적임

 

 

 

배열이 메모리에서 어떤 모습을 하고 있는지

int arr[10] = { 1, 2, 3, 4, 5 };

• 운영체제는 메모리에서 숫자 10개가 들어갈 수 있는 연속된 빈 공간을 찾아서 순서대로 1, 2, 3, 4, 5를 할당함
• 할당하지 않은 남은 공간에는 의미 없는 쓰레기 값이 저장되어 있음
  

  

 

 

 

배열 요소에 접근하는 방식

• 운영체제는 배열의 시작 주소(1이 들어간 주소)만 기억함
• 원하는 값에 접근하려면 인덱스로 접근함
  
  • ex) arr[2]에 접근할 때
    → 운영체제는 배열의 시작 주소를 알고 있기 때문에 시작 주소 + 2칸 떨어진 위치의 데이터를 가져옴

• 배열은 이렇게 인덱스를 이용한 직접 접근이 가능하기 때문에
  → 배열의 길이에 상관없이 언제나 O(1)의 성능을 가짐
  👉 따라서 배열은 읽기/쓰기(참조)에 좋은 성능을 가짐 👍

 

 

 

배열의 크기를 확장했을 때

arr[14] = 15;

• 운영체제는 처음에 크기 10인 메모리 공간을 요청 받았고, 그에 맞는 연속된 메모리 공간을 찾아서 할당함
  
• 배열의 끝에는 이미 다른 데이터가 있기 때문에 더 확장할 수 없는 상황 발생
  → 운영체제는 크기 15인 연속된 공간을 다시 찾아서 새롭게 할당해야 함
  → 기존에 저장되어 있던 1~10까지의 데이터를 전부 새 메모리 공간으로 복사해야 함
  👉 배열은 삽입/삭제에 성능이 좋지 않음👎

 

 

 

---

자바스크립트의 배열

• 일반적인 배열과는 조금 다름
  
  • 자바스크립트에서 배열은 상황에 따라 연속적/불연속적으로 메모리를 할당하지만, 대부분 불연속적으로 할당함
    → 불연속적으로 할당된 메모리를 내부적으로 연결하여 사용자에게는 배열인 것처럼 보임