[Datastructure] 배열, 리스트

배열형태의 자료구조

의미

연속적인 메모리 공간에 저장된 곳의 주소에 접근하는 자료구조.

c언어에서 배열형태

특징

배열의 시작주소 자료형태 찾고자 하는 자료의 인덱스
이 세가지 정보만 알 수 있다면 저장된 곳의 주소를 계산할 수 있다.

a = [2,4,6,8]

a[2]의 주소를 찾고자 한다면,
a[0]의 시작 주소 + 자료형태에 따른 byte * 인덱스번호 로 찾을 수 있다.

C의 배열은 읽기와 쓰기형태만 제공한다.

자료형별 byte 참고

파이썬의 List

특징

파이썬의 리스트는 각 원소의 셀이 데이터가 저장된 곳의 주소를 저장한다는 것이다.

A[2,4,0,5]
각 셀은 2,4,0,5라는 객체가 저장되어있는 주소를 가진다.

동적배열

파이썬의 리스트는 셀의 개수가 필요에 따라 자동으로 증가하고, 감소한다.

만약 insert,append 연산위한 공간이 부족하다면, 크기가 더 큰 리스트를 만들고, 이전 리스트를 모두 이동한다.
만약 remove, pop 연산하고 공간이 남는다면, 크기가 더 작은 리스트를 만들고 이전 리스트를 모두 이동한다.

파이썬의 리스트는 항상 리스트 내부 크기와 가진 값의 개수를 항상 연산해야하므로, 빈 리스트도 메모리가 0byte보다 크다.

수행시간

1. A[i] = A[j] + 1
   쓰기, 대입, 읽기, 산술 연산을 하므로 O(1)

2. A.append(5)
   평균적으로 O(1) 시간

3. A.pop()
   평균적으로 O(1) 시간

4. A.pop(3)
   3번 인덱스의 값을 삭제하고 리턴하는데, 4부터 (len(A) - 1)까지의 값이 모두 왼쪽으로 밀려야하므로 O(N) 시간이 걸린다. 

5. A.insert(0,10)
   0번 인덱스에 10을 넣는다면, 오른쪽 1번인덱스부터 len(A)-1번째 인덱스까지 모두 오른쪽으로 밀려야하므로 O(N)시간

6. A.remove(9)
   처음으로 등장하는 9라는 값을 제거한다. 최악의 경우 리스트의 모든 요소를 모두 탐색해야하므로 O(N)시간.

7. A.index(9), A.count(9)
   remove와 같은 이치로 O(N)시간이 소요된다.

추가적으로 다른 연산자들의 시간복잡도에 대해서는 아래 페이지에 정리되어있다.
complexity of python operations

참고자료

개인적인 공부를 위한 글이며, 모든 저작권은 신천수 교수님께 있습니다.
자세한 강의 내용은 신천수 교수님 강의를 참고하시면 좋을 것 같습니다.
신천수 교수님 자료구조 강의