[코테-List] Array

튜플은 순서가 중요하지 않음 (3,2,1) = (1,2,3)

리스트는 순서가 중요함 [1,2,3] != [3,2,1] 

 

List 란?

1. Array list(Dynamic array) : 배열을 기반으로 만들어짐 -> 우리가 아는 python
2. Linked list: 메모리상에서 비연속적으로 저장됨

---

배열(array)의 특성

1. 고정된 저장 공간(fixed - size) : 선언시에 size가 정해져 있다.
2. 순차적인 데이터 저장(order) : 정해진 size 만큼의 연속된 메모리를 할당받아 데이터를 연속적/순차적으로 저장한다.

static array 정적 배열

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

메모리에 저장된 데이터에 접근하려면 주소값을 알아야 한다. 배열변수 (arr)는 자신이 할당받은 메모리의 첫 번째 주소값(0x4AF57)을 가리킨다. 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능하다. 이를 direct access 또는 random access라고 부른다.

만약 첫 번째 데이터가 저장된 주소값이 (0x4AF57)라면 2번째 데이터는 (0x4AF57 + 4 * 1)에, 3번째 데이터는 (0x4AF57 + 4 * 2), n번째 데이터는 (0x4AF57 + 4 * n)에 저장되어 있다. 아무리 긴 배열이라고 한 번의 연산으로 원하는 데이터에 바로 접근이 가능하다. 즉 O(1)의 시간복잡도를 갖는다.

Linked list는 메모리상에서 연속적/순차적으로 저장되어 있지 않기 때문에 random access는 불가능하다. n번째 데이터에 접근하기 위해서 array는 1번의 연산만 해도 되지만 O(1), linked list는 n번의 연산을 해야 하기 때문에 시간복잡도는 O(n)이다.

 

static array의 한계

데이터의 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 매우 효율적이다. 하지만 선언 시에 정한 size 보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않아서 문제가 발생할 수 있다. 그렇다고 매번 크기가 엄청 큰 배열을 선언하면 메모리 비효율이 발생한다. 그래서 이런 문제점을 해결할 수 있는 것이 dynamic array이다.

 

Dynamic array 동적배열

선언 이후 size를 변경할 수 없는 정적배열과 다르게 동적배열은 size를 늘릴 수 있다. fixed-size 인 static array의 한계점을 보안하고자 만들었다. 동적 배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮긴다. 그리고 기존의 배열은 삭제 한다. 이 과정을 resize라고 한다. 

 

예시)
size = 3

a = [1, 2, 3] → O(n)
a[0] → O(1)
a[1] = 9 → O(1)
a.append(4) → O(1)
a.append(5) → O(1)
a.append(6) → O(1)
a.pop() → O(1)
a.pop() → O(1)
a.insert(1, 10) → 리스트 중간에 데이터 추가 : O(n) 한 칸씩 밀어 넣어야 하기 때문
a.pop(2) → 리스트 중간에 데이터 삭제 : O(n)

	Static array	Dynamic array
access / update	O(1)	O(1)
insert_back	O(1)	amortized O(1)
delete_back	O(1)	O(1)
insert_at	O(n)	O(n)
delete_at	O(n)	O(n)