List는 순서가 중요한 자료구조이다.
(1, 2, 3) !== (3, 1, 2)이다.
자료구조에서 List는 두 종류로 나뉠 수 있다. 바로, Array list와 Linked list이다.
둘을 간단히 비교하자면, 아래와 같다.
Array list- 연속적인 데이터
Linked list- 비연속적인 데이터
- Node 구성 필요
이번 글에서는 Array list에 대한 기록이다. 파이썬에서 사용하는 list는 자료구조의 List와 개념이 다르다. 더 정확히 말하자면, 자료구조 List 안에 나뉘는 두 가지 중 하나인 Array list가 파이썬에서 사용하는 list이다.
1. Array list ?
Array list는 또 두 가지로 나뉜다. Array와 Dynamic list이다. Array list는 Dynamic list로 구현되고, Dynamic list는 Array로 구현된다. 이 두 가지는 C 언어 영역이긴 하지만, 파이썬의 list(자료구조의 Array list)와 자료구조의 List를 이해하기 위해서는 어느 정도 개념을 알아야 한다.
1) (static) array
특성 :
배열 선언 시 사이즈를 정하고(1) 해당 사이즈 만큼 연속된 메모리를 할당(2) 받아, 연속적/순차적으로 데이터를 저장(3)하는 자료구조.
1> 고정된 저장 공간 (fixed size)
2> 순차적인 데이터 저장
2) Random access
메모리에 저장된 데이터에 접근하려면 해당 주소값을 알아야 한다. 배열 변수는 할당 받은 메모리의 첫 주소를 가리킨다.
예시>
Int arr[5] = {3, 6, 2, 1, 4} 예를 들어, arr[3]의 위치를 찾고 싶다면, 메모리의 첫 주소인 arr[0]의 주소 위치로 이동해, 4바이트씩 네 번 이동하면 된다.
배열 arr의 주소값과 arr[0]의 주소값은 동일하다.
배열은 연속적/순차적으로 데이터를 저장하는 특성이 있기 때문에, 첫 주소값만 안다면 어떠한 index에도 즉시 접근 가능하다. 이러한 특성을 ramdon access 혹은, direct access라고 한다.
n번 째 데이터에 접근하는 방법은, 배열 arr의 주소값 + 4 * (n - 1)이다.
* Linked list는?
Array list와 달리 Linked list는 비연속적인 배열이기 때문에, Random access가 불가능하다. array와 달리 n번 째 데이터에 접근하기 위해 n번의 연산이 필요하다. 따라서, 시간 복잡도는 O(n)이 된다.
3) Dynamic array (동적 배열)
static array 한계점
데이터 갯수가 정해진 경우, static array 사용은 효율적이다. 하지만, 선언시 정한 사이즈보다 더 많은 데이터를 저장해야 할 경우, 공간이 남지 않아서 문제가 발생할 수 있다.
그렇다고 매번 크기가 엄청 큰 배열을 선언한다면, 메모리 비효율 발생하게 된다. 이런 문제점을 해결할 수 있는 방안은, dynamic array이다.
** Dynamic array는 Static array와 달리 선언 이후 사이즈를 늘릴 수 있다.
Resizing O(n)
아래 과정을 resize라고 말한다. resize 과정 덕분에 데이터를 추가 저장 가능하다.
<과정>
1> 기존 배열보다 두 배 더 큰 배열을 만든다. (더블링이라고 함)
2> 데이터를 새 배열로 옮긴다
3> 기존 배열을 삭제한다.
따라서, O(1)에서 O(n)으로 시간복잡도가 변경된다.
ㄴ 기존 배열에서 새 배열로 데이터를 옮기는 과정, 기존 배열 삭제 과정 등 때문.
그리고 그 다음 배열부터는 다시 O(1)으로 데이터를 저장할 수 있다.
<정리>
동적 배열은 배열 사이즈를 변경할 수 있다.Fixed-size인static array의 한계를 보완하고자 고안한 배열이다.
선언 시 배열 크기를 정하지 않아도 되기 때문에, 코딩테스트에서 자주 사용한다.
파이썬에서list자료형을 통해 이미 구현해 뒀기 때문에 직접 구현할 필요 없음.
문제에서 배열을 사용하는 경우,list선언해 사용하면 된다. 우리가 알아야 할 점은,list구현이 아니라, 연산 시 시간복잡도가 어떻게 되는가를 구하는 것이다.
