#2. 배열 (Array) / python list

배열은 데이터를 저장하는 아주 기본적인 자료구조이다. 

데이터를 순차적으로 저장하는 List는 크게 Array List 와 Linked List로 나뉘는데 먼저 배열부터 살펴보자.

 

List 

• Array List
  • Array 
  • Dynamic Array (Python의 list)
• Linked List 

배열은 다시 또 두가지로 나뉘는데 기본 정적 배열을 보완하여 동적 배열을 구현했다고 보면 된다.

파이썬의 리스트 타입 자료구조는 동적 배열로 구현되어 있다.

 

배열 (array) 

배열의 두가지 특징 

• 고정된 저장공간
• 순차적인 데이터 저장

 

배열 메모리 할당

int arr[5] = {1,2,3,4,5}

예를들어 위에 처럼 크기5의 배열을 선언한다면 int (4byte) * 5 = 20 byte의 공간을 메모리에 할당하고 각각 4byte의 공간에 1,2,3,4,5의 값을 저장하게 된다. 

 

Random Access 

배열을 처음 선언하면 배열 변수는 메모리의 첫번째 메모리 주소값을 저장하고 있다.

그리고 배열의 데이터에 접근할 때 index * 4byte 로 메모리 주소값을 계산해서 해당  메모리에 바로 접근할 수 있다.

그래서 배열에서 특정 원소에 접근하는 시간복잡도는 O(1)으로 아주 효율적이다.

 

배열의 한계점

배열은 순차적으로 데이터가 저장되어있다는 특성 때문에 데이터 검색이 아주 빠르지만, 공간할당을 처음부터 했기 때문에 할당한 크기가 꽉찼을 때 데이터추가가 어렵다. 그렇다고 애초에 크게 할당하면 메모리공간 낭비가 생긴다. 이를 보완한 방법이 동적 배열이다.

 

동적배열

처음 정의한 배열의 사이즈이상으로 데이터를 추가할 때 자동으로 공간을 추가해주는 배열이다.

 

a[4] = [1,2,3,4] 

이 배열에 5를 추가한다고하면 5를 저장하기 위한 공간을 늘려준다. 

이 때 공간을 늘려주는 방법은 현재 저장공간 * 2 사이즈(더블링) 의 공간을 다시 메모리에 할당해서 기존 데이터를 복사해서 넣어준 뒤 새로운 데이터를 추가해주게 된다. 이를 resize라고하는데 이때 시간 복잡도가 O(N) 이 걸리게된다.

그래서 동적배열은 데이터 추가시에 O(n)이 걸리게 될 수도 있다. (하지만 자주 일어나는 일은 아니기때문에 O(1)이라고 하자)