Array

✏️ 배열 (Array)

• 같은 타입의 값들을 하나의 묶음으로 묶은 자료 구조
  
• 연속된 메모리 공간에 순차적으로 데이터 저장
• 요소 (element)
  • 배열을 구성하는 각각의 값
• 인덱스 (index)
  • 배열에서의 위치를 가리키는 숫자

특징

장점

• index를 이용한 접근이 가능해 모든 요소에 빠르게 접근 가능 - O(1)
• 구조가 간단

단점

• 데이터 삽입/삭제가 어려움 - O(N)
  • 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 중간에 특정 요소를 삽입/삭제하는 경우 삽입/삭제된 요소로부터 뒤에 있는 요소들을 모두 이동시켜야 하기 때문
• 배열 선언 이후 할당된 정적 메모리 때문에 길이 변경 X
• 배열의 크기가 정적으로 결정되므로 삽입/삭제가 동적으로 발생하는 경우 적절한 배열의 크기를 미리 결정하는 것이 어려움

📌 값 접근 - O(1)

• index로 배열의 요소에 접근 가능
• 각 요소는 0부터 시작하는 인덱스를 가짐
• index로 접근하면 배열이 가진 첫 번째 요소의 주소값 + 인덱스*요소의 크기로 해당 요소의 주소값을 구해 값을 읽어옴
  • ex. arr[3]
    • 해당 요소의 주소값 = arr의 주소값 + 3(index) * 요소의 크기 (byte)
    • 요소의 크기는 타입에 의해 결정됨
      • ex. int = 4 byte

삽입/삭제 연산

삽입 - O(N)

• 중간에 요소를 삽입하는 경우 뒤에 있는 데이터를 요소의 수만큼 뒤로 이동시킨 후 데이터를 넣어야 함

삭제 - O(N)

• 해당 데이터를 삭제한 후 뒤에 있는 데이터를 삭제한 요소 수만큼 앞으로 이동시켜줘야 함
  

활용

• 데이터 크기가 자주 바뀌지 않고 삽입/삭제가 없는 경우
• 어떤 특정 요소를 빠르게 읽어야 하는 경우