자료구조
순차적 자료구조(배열과 리스트)
굽이굽이
2022. 3. 1. 15:00
배열(Array)과 리스트(List)
- Python에서는 리스트가 배열 자료구조다.
- 배열과 리스트는 데이터를 연속적인 메모리 공간에 저장하고, 저장된 곳의 주소를 통해 접근하는 자료구조다.
- 좌측의 그림은 int Array[4]를 통해 정수 4개를 저장할 수 있는 연속적인 메모리 공간을 할당한 것이다.
- 각각의 메모리 공간은 주소를 갖는다.
- 주소가 4씩 커지는 이유는 정수의 크기가 4Byte니까.
위의 그림과 같이 메모리의 주소가 주어지면, 단위시간에 값을 읽거나 저장하는 것이 가능하다.
print(A[2]) # A[2]의 값을 읽을 수 있다.
A[2] = 8 # A[2]의 메모리에 값 8을 저장할 수 있다.그래서 중요한 사실은~
1️⃣ 배열의 시작 주소
2️⃣ 저장된 값의 종류(int인지 string인지 등 각각이 몇 바이트씩 차지하는지 알아야 하니까)
3️⃣ 몇 번째에 저장되어 있는지를 나타내는 인덱스
이렇게 세가지를 정보를 통해 데이터가 저장된 곳의 주소를 알 수 있다는 것이다.
| C언어 배열 자료구조 | Python의 리스트 자료구조 |
| 배열의 셀에 데이터 저장 | 리스트의 셀에 데이터를 가리키는 주소를 저장 |
| 읽기, 쓰기만 지원 | 읽기, 쓰기 + append, insert 등 다양한 메서드 제공 |
C의 배열은 어떤 타입의 데이터가 들어올지 모르니까 그 때 그 때 메모리를 할당해줘야 함.
Python은 어떤 타입의 데이터를 가리키든 주소값을 저장할 공간만 있으면 되니까 4byte혹은 8byte로 고정.
1️⃣ 좌측 그림에서 각각의 셀에 저장된 주소가 데이터값을 가리키고 있다.
2️⃣ 'A[2] = A[2] + 2'를 통해 두번째 인덱스 데이터에 2를 더한 값을 대입.
3️⃣ 아래의 그림과 같이 기존의 데이터는 사라지지 않고 함께 들어가 있음.
❓만약에 append나 insert 등으로 데이터가 계속해서 추가되거나 pop, remove등으로 데이터가 제거된다면?
➡️ Python의 리스트는 '동적배열'(dynamic array)인 만큼 알아서 메모리 공간을 조정한다.
- 위의 코드를 통해 리스트의 메모리 공간을 확인
- 데이터가 추가되거나 제거되면 동적으로 메모리 공간을 조정
- 동적배열을 위해 python내부적인 변수가 필요하다.
- 내부적인 변수가 빈 리스트도 0Byte가 아닌 이유가 된다.
➡️ append연산을 통해 메모리를 늘려야 한다면, 이전 리스트의 값을 새로운 리스트로 일일이 이동해야 해서 연산시간에도 영향을 준다.