배열

*stack, heap

heap 영역이 동적 !

 

동적 배열 = 리스트 (파이썬의 배열)

(파이썬의 배열은 동적이다 !!)

 

탐색 기능이 막강(인덱싱->한번에 찾음) & 마지막에서 삽입, 연산 good !

* 중간에 삽입/삭제시 원소들 옮겨야됨 ㅜㅜ

 

ADT

operation

.is_empty()기능

->

[] 빈 리스트 자체가 false임

.insert(index, n)

[]

.pop() ->마지막 원소 삭제 후 그 원소 반환

.pop(index) -> 인덱스 원소 삭제 후 반환

.append(n) :맨뒤에 추가

.remove(아이템) -> 배열안에 그 아이템 있으면 그거 삭제

 

특징

-> 선형적으로 이어져있다

-> 캐시히트가 발생시 시간 매우 절약 ! (캐시로가져올때 주변 데이터까지 같이 가져오므로, 배열은 유리)

 

요소의 추가

1. append/pop (맨뒤)

* 배열이 확보한 메모리 공간 = capacity / 채워진 데이터 크기 = size

• capacity>size -> 하나만 추가하면 되니까 O(1) !
• capacity=size -> 충분공간 확보후(약2배정도) 기존 배열을 다복사하고나서 하나 추가해야됨 !! O(n) 하고 O(1)

2. 중간

-> 중간에 끼는거 다음 애들이 다 이동함 !!! O(n)