배열(Array)

• 데이터 원소들의 리스트
• 한 자료형의 여러 값들이 메모리상에 모여 있는 구조

읽기

• O(1) 소요

  • 컴퓨터는 모든 메모리 주소에 한 번에 접근 가능
  • 각 배열에는 메모리의 시작 주소가 저장됨
  • 배열의 인덱스는 0부터 시작

→ 인덱스의 메모리 주소가 1068인 배열이 있다면 인덱스 3에 접근 할 때는 1068+3인 1071 메모리 주소로 바로 가면 된다.

검색

• 정렬된 배열일 경우 O(log n) 소요

  • 이진 검색 사용 (아래는 수도코드이다)

  Function binary_search(array, value)
  	lower_bound = 0
  	upper_bound = array.length - 1
  
  	while lower_bound <= upper_bound do
  		midpoint = (upper_bound + lower_bound) / 2 and round off midpoint
  		value_at_mid = array[midpoint]
  
  		if value < value_at_mid
  			upper_bound = midpoint - 1
  		else if value > value_at_mid
  			lower_bound = midpoint + 1
  		else if value is same with value_at_mid
  			return midpoint
  
  // 상한선과 하한선이 같아졌는데도 value랑 value_at_mid가 일치하지 않았다면
  // array 안에 value가 없다는 의미
  
  	return null

• 정렬되지 않은 배열일 경우 O(n) 소요

  • 한 번에 한 셀씩 값을 발견할 때까지 확인하기 때문 (선형검색)

삽입

• 맨 뒤에 삽입하는 경우 O(1)
• 가운데 삽입하고 싶으면 삽입하고 싶은 위치 뒤에 있는 요소를 전부 1칸씩 오른쪽으로 옮긴 뒤 삽입해야 함 → N+1 단계 → O(n)
• 단, 정렬된 배열일 경우 검색 연산 먼저 수행햐야 함

삭제

• N단계 → O(n)

💡 정렬된 배열: 삽입은 다소 느리지만(O(n)) 검색은 훨씬 빠르다(O(log n)).

💡 정렬되지 않은 배열: 삽입은 빠르지만(O(1)) 검색이 훨씬 느리다(O(n)).

복제

int[] a = {1, 2, 3, 4, 5};
int[] b = a.clone();

출력

System.out.print("a =");
for (int i = 0; i < a.length; i++)
	System.out.print(" " + a[i]);

Source

A Common-Sense Guide to Data Structures and Algorithms