[자료구조] 배열, 리스트(Array, List)

배열이란?

데이터를 연속적인 메모리 공간에 저장하고, 저장된 곳의 주소(address, reference)를 통해 매우 빠른 시간에 접근할 수 있는 가장 많이 쓰이는 기본적인 자료구조

 

Array

 

C언어의 배열(Array)

• 크기가 고정되어 있으며, 한 번 생성한 배열은 크기를 변경하는 것이 불가능하다.
• 배열의 시작 주소, 저장된 값의 종류(바이트 개수), 몇 번째에 저장되어 있는지를 나타내는 인덱스(index) 세 가지 정보만으로 값이 저장된 곳의 주소를 계산할 수 있다.
• 읽기와 쓰기 연산에 O(1) 시간 소요

 

Python의 리스트(List)

• C의 배열의 셀에는 실제 값(데이터)이 저장된 형식이지만, Python 리스트의 셀에는 데이터가 아닌 데이터가 저장된 곳의 주소(address 또는 reference)가 저장된다.
• 항상 객체의 주소만 저장하기 때문에, 리스트의 셀의 크기를 메모리의 주소를 표현할 수 있는 (4 바이트 또는) 8 바이트로 고정하면 된다.
• 모든 셀의 크기가 같기 때문에 index에 의해 O(1) 시간 접근이 가능하다
• 단순한 읽기/쓰기 연산 외에도 다양한 연산을 지원한다(append, pop, insert, count 등).

List

동적 배열(Dynamic Array)

• 리스트는 크기(셀의 개수)가 필요에 따라 자동으로 증가/감소한다.
• 그래서 append 또는 insert 연산을 위한 공간(메모리)이 부족하면 더 큰 메모리를 할당받아 새로운 리스트를 만들고
  이전 리스트의 값을 모두 이동한다. 이를 더블링이라고 한다.
• 반대로 pop 연산을 하면서 실제 저장된 값의 개수가 리스트 크기에 비해 충분히 작다면 더 작은 크기의 리스트를 만들고 모두 이동한다.
• 이렇게 필요에 따라 크기가 변하는 배열을 동적 배열(dynamic array)라 부른다. 따라서 사용자는 배열의 크기를 전혀 신경쓰지 않아도 된다. 
• Java에서는 ArrayList, C++에서는 std::vector와 같은 동적 배열 자료형을 지원한다.

>>> A = []
>>> sys.getsizeof(A)
64 # 빈 리스트도 64 바이트 할당
>>> A.append("Python") # append 후 96 바이트로 재할당
>>> sys.getsizeof(A)
96

Dynamic Array

Python의 Array

• Python에서는 또한 numpy모듈에서 array 자료구조를 지원한다.
• 특정 원소에 대해 O(1) 접근 가능
• mutable하다
• 한 종류의 값만 저장 가능
• 메모리를 리스트보다 적게 사용한다.
• 배열 단위의 연산이 매우 빠르다.

>>> import numpy as np
>>> A = np.arange(10) # range(start, stop, step) 유사
>>> A
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> print(A)
[0 1 2 3 4 5 6 7 8 9]

참고

Data Structures with Python(신찬수 저)

파이썬 알고리즘 인터뷰(박상길 저)