[자료구조] 배열 (Array)

이번 포스팅에선 배열 (Array)에 대해 살펴볼 것이다.

저번 포스팅에서 필요할 때마다 메모리를 할당받아 데이터를 저장하는 방법인 연결 리스트(Linked List)를 다뤘으니

이번 포스팅에선 미리 메모리를 확보한 다음 연속된 공간에 저장하는 방법인 배열에 대해 알아보자.

 

배열은 자료구조를 배우기 이전에도 컴퓨터 과학을 공부했다면 다 들어봤을 만한 기초적이고 중요한 것이다.

배열이란?

배열(array)은 같은 타입의 변수들로 이루어진 유한 집합으로 정의된다.

배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.

배열은 같은 종류의 데이터를 많이 다뤄야 하는 경우에 사용할 수 있는 가장 기본적인 자료구조이다.

 

 

 

배열의 탐색

배열은 배열의 주소와 인덱스만 알면 바로 접근 가능하다.

이것이 배열의 가장 큰 핵심이다.

 

첫번째 셀의 주소 + (데이터 타입의 크기 * 해당 데이터의 인덱스)

ex) int 배열의 주소가 400일때 다섯 번째 셀의 주소는 400 + 4*5 = 420

⇒ 배열은 데이터에 대한 접근이 쉽고 빠르다는 장점이 있다.

 

 

x가 몇 번 인덱스인지 return하는 함수이다.

1. x가 몇 번 인덱스인지 알기 위해 0번 인덱스부터 순회한다.(for, while)

2. 만약 x가 배열의 i번째 인덱스 값과 같다면 i를 return 한다.

3. 일치하는 인덱스 i가 없다면 -1을 return 한다.

 

배열의 삽입

int형 배열의 a 번째 인덱스에 b를 삽입하는 함수이다.

1.  배열의 크기 - 1부터 a까지 for문을 순회하며 b가 삽입될 a번째 인덱스를 확보하기 위해 한 칸씩 뒤쪽으로 값들을 이동시킨다.

2. a번째 인덱스에 b를 삽입한다. 

 

 

배열의 삭제

int형 배열의 x가 담겨있는 인덱스를 삭제하는 함수이다.

1. 삭제될 인덱스부터 배열의 크기 - 1까지 for문을 순회하며 한 칸씩 앞쪽으로 값들을 이동시킨다.

2. 배열의 크기 - 1 번째 인덱스를 0으로 설정한다.(삭제됨을 의미)