[자료구조] 01. 배열

배열(Array)

배열은 값을 나열하고, 각 값을 인덱스에 대응하도록 구성한 자료구조이다.

 

배열이 필요한 이유

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
• 같은 종유의 데이터를 순차적으로 저장

 

장점

• 값에 빠른 접근이 가능하다. (시간복잡도 O(1))

 

단점

• 중간에 값을 추가, 삭제하기가 쉽지 않다.
• 미리 크기를 할당해야한다. 또는 배열의 크기를 가변할 수 없다.

---

위의 내용들을 자바로 예를 들어서 알아보려고 한다.

우선 먼저 배열을 만들어주는데, 위의 단점에 설명했듯이 배열은 선언할 때 미리 크기를 할당해야한다.

그래서 아래와 같이 크기가 7인 배열을 하나 만들어주자.

int[] arr = new int[7];

위의 그림처럼 크기가 7인 배열이 생성된다. int형의 배열을 생성했기 때문에 int 자료형의 기본값인 0이 모든 위치에 저장되어 있다.

그리고 배열은 인덱스라는 개념이 있기 때문에 인덱스를 통해 배열에 값을 조회,추가,삭제를 해야 한다.

 

위의 그림처럼 인덱스는 0번부터 시작한다. 배열 첫 번째 위치에 5라는 값을 저장하고 싶으면 인덱스 0번에 5를 넣어주면 된다.

이를 코드로 표현한다면 아래와 같다.

arr[0] = 5;

 

위와 같이 배열은 인덱스로 접근을 하여 추가 또는 삭제를 하기 때문에 추가, 삭제 시 O(1)의 시간 복잡도를 갖게 된다.

마찬가지로 접근을 할 때도 당연히 인덱스를 통해 접근을 하기 때문에 접근 또한 O(1)의 시간 복잡도를 갖게 된다.

 

하지만 어떤 특정 값을 찾기 위해서는 즉, 검색을 할때는 배열은 순차검색을 하여 값을 찾아야한다.

배열에 저장되어 있는 값을 순차적으로 하나하나 확인해서 찾아야 한다는 것이다.

public class ArrayTest {
	public static void main(String[] args) {
		int[] arr = new int[7];

		arr[0] = 5;

		System.out.println(indexOf(arr, 5));
	}

	public static int indexOf(int[] arr, int searchValue) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == searchValue)
				return i;
		}

		return -1;
	}
}

 

특정 값이 위치한 인덱스 값을 반환하는 indexOf 메서드를 위와 같이 구현해봤다. 위의 예제처럼 배열에서 특정 값을 찾기 위해서는 배열을 순회하여 값을 찾아야한다. 지금 위의 예제로는 0번에 5라는 값이 들어있기 때문에, O(1)의 시간이 걸리는데, 만약 찾으려는 값이 맨 마지막 배열에 위치할 경우에는 O(n)의 시간이 걸린다. 시간 복잡도는 최악의 상황을 표현하므로 배열의 검색은 O(n)의 시간 복잡도를 갖게 된다.

---

시간 복잡도

• 추가, 삭제 : O(1)
• 검색 : O(n)