[Data Structure] 배열(array)

---

배열

 

 

자리를 나타내는 인덱스(index)와 동일한 자료형의 데이터 값으로 된 집합이 연속적인 형태로 되어 있는 자료구조이다. 연속적인 형태라는 것은 데이터 값이 메모리에 저장될 때 순차적으로 저장된다는 뜻이다. 이때 순차적으로 붙은 각 번호가 인덱스이다.

또한 데이터의 자료형이 모두 동일하기 때문에 특정 값에 접근할 때 그 값의 인덱스를 알 수 있다면 메모리 주소 역시 알 수 있다. 즉 원소들이 연속적으로 배치되어 있기 때문에 각 원소에 접근할 때 시간복잡도가 $ \mathcal{O}(1) $ 인 임의접근(random access)이 가능하다.

대부분 언어에서 기본적으로 별도의 라이브러리 없이 지원하며, 인덱스를 통해 배열의 값에 접근할 때 [] 를 주로 사용한다. 또한 대부분의 언어에서 배열 인덱스의 시작은 1 이 아니라 0 이다. 

아주 기초적인 자료구조로 임의접근은 불가능하지만 배열보다 원소의 삽입/삭제가 빠른 연결 리스트(linked list)와 비교되곤 한다.

백준의 배열 합치기 문제(링크)를 통해서 배열을 다루는 것을 연습해볼 수 있다.

 

---

ADT

 

객체 (Object)

• <인덱스, 값> 쌍의 집합

연산 (Operation)

• create(size) ::= size 만큼의 원소를 저장할 수 있는 배열을 생성한다.
• get(index) ::= index 에 위치한 배열 값을 반환한다.
• set(index, value) ::= index 에 위치한 배열 값에 value 를 대입한다.