*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)