순차적 자료구조에는 배열과 리스트가 있다. 리스트는 파이썬에만 있는 구조이다.
C언어
배열의 한칸은 4byte로 구성되어 있고 A[n]의 주소 = A[0]의 주소 + n * 4 bytes 이다.
배열: 어떤 특정위치에 있는 값을 상수시간 내에 읽어올 수 있고, 쓸 쑤 있는 두개의 기본 연산을 제공하는 자료구조
Python
객체를 직접 저장하는 배열과는 다르게 리스트는 객체의 주소를 저장한다.
append, pop, insert, remove, index, count 등과 같은 연산이 있다.
리스트는 용량을 자기 스스로 조절할 수 있다. 배열은 안됨
리스트의 용량이 저장될값의 개수보다 크지 않다면 현재 용량의 2배크기인 리스트를 새로 할당해서 만들고 기존 값들을 옮겨담는다. 이건 O(n)이지만 용량이 더크면 O(1)로 작동된다.
append, pop : O(1)
insert, remove : O(n) 한칸씩 뒤로 다 밀어내고 연산해서
index, count : O(n)
공부일기