• 목차
• 참고

일반적인 배열과 파이썬의 리스트

• 일반적인 배열이라 할 수 있는 C언어의 배열과 파이썬의 리스트를 한번 비교해보자
• 참고)https://seoyeonhwng.medium.com/파이썬-리스트-내부-구조-f04847b58286
• 결론부터 말하면
  1. 초기 선언시 크기를 지정해주지 않아도 됨
  2. 리스트는 원소로 원소들의 값이 아닌 주소를 가지고 있음.
     • 그렇기 때문에 저장되는 자료형이 달라도 ㄱㅊ. 또한 처음에 저장할 변수의 자료형을 선언해줄 필요도 없음
     • 실제 원소의 값을 얻으려면 이동이 두번 필요함

C언어의 배열

• 아래의 코드는의 좌변은, 원소를 int로 가지는 4칸짜리 A를 가지겠다는 것
  • 칸수와 들어갈 원소의 타입을 미리 선언한다
• 우변은 그 4칸에 각각 2,4,0,5의 원소를 넣겠다는 것

#배열 생성
int A[4] = {2,4,0,5};

• 아래와 같이 2번인덱스의 원소에 +1을 해준다고 하자
  • A[2]값을 읽을 때, 1을 더할 때, A[2]에 더한값을 대입할 때, 대입한 값으로 A[2]를 쓸 때 총 네번의 기본연산이 발생한다. 결국 일련의 과정의 시간복잡도는 O(1)
  • 이때 배열 A는 자신의 시작점(즉 A[0]) 주소를 알고 있고, 따라서 A[2]의 위치역시 자료형의 byte값 *2를 해주면 바로알 수 있음. 숫자의 경우 4byte이므로 그냥 A[0] + 4bytes *2해주면 A[2]가 나옴
    • 그래서 A[2]를 찾는 것의 시간복잡도가 O(1)인 것(인덱스로 바로찾아지니까)
    • 이러한 원리로 일반적인 배열에서, 탐색(검색)의 시간복잡도는 O(1)이다
    • 또한 이렇게 그 다음 인덱스의 메모리 주소를 알기 위해, 자료형의 종류를 일치시켜줘야 한다
    • 자료형의 종류가 일치되어야 각 자료형마다 차지하는 byte의 크기를 알 수 있고, 그래서 각 인덱스별 자료의 메모리시작 위치를 계산해서 바로 알 수 있음
  • 결국 일반적인 배열이 가지고 있는 건, 배열의 길이값 / 원소의 데이터 타입 / 첫번째 시작점(A[0])의 메모리주소 뿐임

A[2] = A[2] + 1

파이썬의 리스트 특징1 : 원소로 메모리 주소값을 가짐

• 일반적인 배열이 가지고 있는 건, 배열의 길이값 / 원소의 데이터 타입 / 첫번째 시작점의 메모리주소’ 이며 이를 통해 각 원소의 값을 확인할 수 있다
• 이에 반해 파이썬의 리스트는 원소로 자료들의 메모리 위치를 주소로 가진다
  • 예를 들어 아래에서 리스트 A는 2의 메모리 주소, 원소 4의 메모리 주소,원소 0의 메모리 주소,원소 5의 메모리 주소를 가지고 있는 것
  • 이때 각 메모리 주소의 크기는 32비트 컴퓨터라면 4byte, 64비트 컴퓨터라면 8byte에 저장된다. 즉 리스트의 기본원소인 ‘데이터의 메모리 주소값’들은 배열처럼 무조건 동일한 크기의 데이터를 가진다.
  • 결국 배열처럼 첫번째 값을 알면 그 뒤의 원소들에 접근할 수 있고, 이렇게 리스트의 원소인 메모리 주소를 찾은 후 메모리 주소를 가지고 실제 자료가 있는 곳으로 한번 더 접근하는, 총 2번 주소를 따라가는 구조임