파이썬에서는 array 배열을 지원하지 않는다. 외부 라이브러리를 이용해야 사용할 수 있다.
그래서 파이썬으로 pl에 입문하는 사람들이 list와 array의 차이를 이해하지 못하는 경우가 종종 있다.
이 글에서는 파이썬 리스트와 배열의 비교를 중심으로 리스트의 특징에 대해 설명하려한다.
기본 구조
배열과 리스트 모두 변수들을 연속적으로 담아두고 빠른시간에 접근하기 위한 자료구조이다.
- 배열: 어떤 자료를 얼만큼 저장할 지 미리 선언하여 생성한다. ex) int A[4] // 정수 4개를 저장하는 연속된 메모리공간
배열의 시작 주소, 저장된 값의 종류, 몇 번째 데이터인지(인덱스)의 정보로 빠르게 해당 정보에 접근할 수 있다. - 리스트: 파이썬에서 리스트는 배열에 실제 값을 저장하지 않고 데이터가 저장된 곳의 메모리주소가 저장된다.
주소의 크기가 같기 때문에 모든 셀의 크기가 같아. 빠르게 접근할 수 있다.
또한 해당 주소에 저장된 데이터를 동적으로 변경할 수 있기 때문에 다양한 형태의 자료형을 저장할 수 있게 된다.
따라서 모두 O(1)의 시간에 접근할 수 있다.
만약 배열에 다른 크기의 데이터를 저장한다면, 시작점과 인덱스 만으로 해당 데이터에 접근할 수 없게된다. 사진같은 저장은 파이썬 리스트에서만 가능하다.
또 다른 차이점은 파이썬은 동적배열 이라는 것이다.
append, pop연산등에 따라서 배열의 크기가 사용자의 추가조치 없이 변경된다.
데이터 삽입, 삭제
연속된 데이터의 양 끝 또는 중간에 데이터를 삽입, 삭제하는데 걸리는 시간에 대한 설명이다.
- 배열: 기본 할당된 사이즈를 벗어나는 경우 새로 사이즈를 지정해주어야 한다(resize). 따라서 추가 데이터를 삽입하면 새로운 큰 배열에 모든 데이터를 옮겨주어야 한다. 따라서 O(n)의 시간이 소요된다.
- 리스트: 리스트는 처음 선언될 때 부터 default 64의 주소공간을 할당한 채로 생성된다. 이후 추가 공간이 필요한 경우 두배 단위로 이루어 진다. resize가 발생하는 경우 O(n) 그렇지 않은 경우 O(1)의 시간에 데이터를 추가할 수 있다.
마지막에 데이터를 추가하는 append() 의 경우 평균적으로 O(1)에 수렴하는 시간복잡도를 가지는 것이 알려져 있다.
리스트는 append 연산을 수행할 때 다른 조치없이 시간적으로 효율적인 연산을 할 수 있다. 배열에서는 이런 연산이 발생하지 않도록 처음부터 큰 배열을 만드는 등의 조치를 취해주어야 한다.
파이썬 리스트는 메모리 인심이 넉넉하다. 빈공간을 많이 할당하는 것 외에도 길이를 저장하는(len(A)) 다른 메모리들을 동적으로 활용하여, 사용자가 신경쓰지 않는채로 사용할 수 있게 돕는다.
하지만 데이터를 리스트 가운데에 넣거나 중간에 있는 데이터를 지우는(가운데 삭제 후 뒤의 데이터들 일일히 옮겨 주어야함) 경우에는 O(n)의 복잡도를 가진다. 많이 사용하게되는 자료구조인 만큼 각 연산에 대한 소요시간을 숙지해야 한다.
| 함수 | 예시 | Big-O | note |
| Index | list[i] | O(1) | |
| Store, Update | list[i] = a | O(1) | |
| Length | len(list) | O(1) | |
| Append | list.append(a) | O(1) | |
| Pop | list.pop() | O(1) | |
| Clear | list.clear() | O(1) | |
| Slice | list[i:j] | O(n) | O( j - i ) // 최대 n |
| Extend | list.extend(..) | O(n) | ..의 길이에 대한시간 |
| Construction | list(..) | O(n) | ..의 길이에 대한 시간 |
| == or != | list == list2 | O(n) | |
| Insert | list.insert(i, a) | O(n) | |
| Delete | del list[i] | O(n) | |
| Remove | list.remove(...) | O(n) | |
| Containment | (.. in list) | O(n) | |
| Copy | list.copy() | O(n) | == list[:] |
| Sort | list,sort() | O(n) | |
| Reverse | list.reverse() | O(n) |