배열

배열이란

• 연속된 메모리 공간에 순차적으로 저장된 데이터 모음
• 임의접근이 용이하다.저장된 곳의 주소를 통해 매우 빠른 시간에 접근할 수 있는 자료구조
  • 2번째 셀의 주소 = 시작주소 + 2*(자료형의 byte 수)
  • 배열의 시작주소, 저장된 값의 타입(바이트 개수), 인덱스만으로 값이 저장된 주소 계산 가능
• 접근하고자 하는 데이터가 어디에 위치하건, 첫번째에 있는 데이터와 N번째에 있는 데이터에 접근하는데 드는 비용이 같다
• 대부분 프로그래밍 언어에서는 동일타입의 데이터를 저장함(int[]에는 int만)
• 정적배열, 동적배열이 있다.

정적배열

• 선언시 배열의 크기를 지정하고, 크기 변경 불가능

동적배열

• 일반 배열은 지정된 크기를 변경할 수 없지만, 동적배열은 배열 크기의 변경이 가능하다.
  • 현재 지정된 배열의 크기가 다 찼을 때, 뒤에 새로운 자료를 추가하게 되면, 현재 차지하고 인쓴 공간보다 더 큰 새로운 공간을 할당받고 그 위치에 원래 있던 자료들을 다 옮기고 그 뒤에 새로운 자료를 추가하는 원리이다.
• 중간 원소의 삽입, 삭제에 불리하다.
  • 중간 원소 삭제시 해당 인덱스 뒤의 모든 자료를 한 칸 씩 당겨줘야함
  • 중간에 원소 삽입시 해당 인덱스 뒤의 모든 자료를 한칸씩 밀어줘야함.

배열의 시간복잡도

- 읽기 O(1)

- 정적배열 데이터 배정: O(1)

- 동적배열의 중간원소 삽입, 삭제: O(n)