[CS] 자료구조 - 배열 (Array)

배열 (Array)

배열(Array)은 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조이다. 같은 종류의 데이터를 순차적으로 저장하며 데이터를 효율적으로 관리하기 위해 사용한다.

 

배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택 영역에 할당되며, 주소값(인덱스)은 힙 영역에 생성되는 배열의 주소값이다.

• 장점
  • 빠른 접근이 가능함. (인덱스를 이용해 접근하기 때문)
  • 데이터의 크기가 확정적일 때 메모리나 처리속도 면에서 좋다.
• 단점
  • 선언할 때 크기가 고정되기때문에 데이터 추가/삭제의 어려움이 있다. (사이즈를 넘어가면 배열을 새로 만들어야 함)
  • 중간에 요소를 삽입하거나 삭제할 경우에는 해당 요소 뒤에 있는 요소들의 위치를 이동시켜야 한다.

🌟 element : 배열을 구성하는 각각의 값. 요소 혹은 원소라고 부른다.

🌟 index : 배열에서의 주소를 가리키는 숫자값 (배열의 index는 0부터 시작)

// 배열의 선언 방법
public class Array {

  // 배열을 선언하면서 동시에 크기 할당
  int[] arrA = new int[10];

  // 배열을 선언하면서 동시에 값을 할당
  int[] arrB = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
}

int 자료형 뿐만 아니라 String, char, boolean 등 다른 자료형의 배열도 선언할 수 있다.

배열의 길이는 중괄호 { } 사이에 제공되고 쉼표 , 로 구분된 값의 수에 따라 결정된다.

---

배열의 시간복잡도

 

접근

배열 내에서 n번째 인덱스에 해당하는 값을 찾는 접근 연산은 O(1)의 시간복잡도를 갖는다.

 

검색

배열의 검색은 순차검색으로 인덱스를 알지 못할 때 원하는 값을 찾기 위해서는 배열을 하나하나 확인해봐야 하기 때문에 O(n)의 시간복잡도를 갖는다.

 

추가, 삭제

추가하거나 빼려는 인덱스를 정확하게 알고 있다면 O(1), 그게 아니라면 O(n)