[자료구조] 배열(Array)

배현호·2021년 4월 13일
1

자료구조

목록 보기
2/10

스도쿠

특징

배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조이다.
연속적인 메모리 공간에 순차적으로 데이터를 저장한다.
배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다.
선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다.

배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있다.
예를 들어 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)가 되는 것이다.

배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다.
여기서 인덱스는 0부터 시작하며, 마지막 인덱스는 배열의 요소의 개수 - 1이다.

시간복잡도

인덱스를 알고 있다면, 인덱스에 접근하는 시간복잡도는 O(1)이다.
데이터를 배열에 삽입을 하려면 기존에 있는 데이터를 한 칸 shift 한 후 데이터를 넣어야 하기에 시간복잡도는 O(n)이 걸린다.
마찬가지로 배열에서 데이터를 삭제하는 작업 또한 삭제한 뒤, 나머지 데이터들을 한 칸 shift 해줘야 해서 삽입과 마찬가지로 시간복잡도가 O(n)이 걸리게 된다.

장단점

장점

  • 구현이 쉽다.
  • 참조를 위한 추가적인 메모리가 필요하지 않는다.
  • 연속적이므로 메모리 관리가 편하다.
  • 인덱스를 통해 접근하므로 검색이 빠르다.

단점

  • 배열의 크기를 변경할 수 없다.
    - 크기를 변경하려면 새로운 배열을 만든 후, 기존의 데이터를 옮겨야 한다.
  • 메모리 낭비가 발생하게 된다.
    - 배열을 선언한다 하더라도 사용하지 않는 공간은 배열을 선언할 때 공간이 할당되어 있어서 낭비가 된다.

예제코드

Java

int arr[] = new int[10];

for(int i = 0; i < 10; i++) {
	arr[i] = i+1;
}

for(int i = 0; i < 10; i++) {
	System.out.print(arr[i]);
}

Kotlin

fun main() {
    var arr = Array<Int>(3, {0})
	var arr = IntArray(3)
    arr[1] = 1
    arr[2] = 2

    arr.forEach { println(it) }
}
profile
Spring Boot 공부하고 있는 고등학생입니다.

0개의 댓글