[Data Structure] 배열(Array)

배열

• 선형 자료 구조
• 많은 수의 데이터를 다룰 때 사용하는 자료구조
• 각 데이터를 인덱스와 1:1 대응하도록 구성
• 데이터가 메모리 상에 연속적으로 저장됨
  • Cache Hit Rate가 높음
• 배열의 장점
  • 인덱스를 이용하여 데이터에 빠르게 접근 가능
  • C++ 예시

  int arr[] = {1, 2, 3};
   cout << arr[0];	// 1
   cout << arr[1];	// 2
   cout << arr[2];	// 3 

  • Java 예시

  int[] arr = {1,2,3};
   System.out.println(arr[0]);	// 1
   System.out.println(arr[1]);	// 2
   System.out.println(arr[2]);	// 3

• 배열의 단점
  • 데이터의 추가/삭제가 번거롭다
    • 미리 최대 길이를 정해서 생성해야 함
    • 가변 길이 배열은 크기를 변경할 때마다 새로운 배열을 생성

배열의 시간 복잡도

• 임의의 원소에 접근 : $O(1)$
• 임의의 위치에 원소 추가/제거 : $O(N)$
  • 추가 시 이후 원소를 모두 뒤로 밀어야하기 때문
  • 삭제 시 이후 원소를 모두 앞으로 당겨야하기 때문

C++ STL vs Java

• C++에서 vector STL을 사용하여 동적으로 크기가 변경되는 배열을 사용 가능하다

#include <vector>

vector<int> v;
v.push_back(1);	 // [1]
v.push_back(2);  // [1, 2]
v.push_back(3);  // [1, 2, 3]
v.push_back(4);  // [1, 2, 3, 4]
v.pop_back();	 // [1, 2, 3]

cout << v.front();	// 1
cout << v.back();	// 3
cout << v.size();	// 3
cout << v.empty();  // 0
cout << v[0];		// 1  (접근 가능 여부 체크 x)
cout << v.at(0);	// 1  (접근 가능 여부 체크 o)

• Java에서 ArrayList 클래스를 사용하여 동적으로 크기가 변경되는 배열을 사용 가능하다

import java.util.ArrayList;
import java.util.List;

List list = new ArrayList();

list.add(1);    // [1]
list.add(2);    // [1, 2]
list.add(3);    // [1, 2, 3]
list.add(4);    // [1, 2, 3, 4]
list.add(5);    // [1, 2, 3, 4, 5]
list.remove(1);                  		// [1, 3, 4, 5]  (인덱스 값이 삭제됨)
list.remove(Integer.valueOf(3));    	// [1, 4, 5]     (실제 값이 삭제됨)
System.out.println(list.get(0));        // 1
System.out.println(list.isEmpty());     // false
System.out.println(list.size());        // 3