vector(array list)란?
배열의 확장된 개념이다. 배열의 고정된 크기에 대한 단점을 더 큰 배열을 할당받아 크기를 키움으로써 보완한 개념이다.
배열에 기반하였으므로 접근, 삽입, 삭제를 index를 통해서 수행한다.
주요 methods:
at(int i): 인덱스 i의 요소를 제거 없이 리턴
set(int i, o): 인덱스 i의 요소를 o로 대체
insert(int i, o): 인덱스 i에 o를 삽입
erase(int i): 인덱스 i의 요소를 제거
추가적인 methods:
size()
empty()
벡터의 적용
시간복잡도
size, empty = O(1)
at(i) = O(1)
set(i,o) = O(1)
insert(i,o) = O(n)
erase(i) = O(n)
만약 insert(0, x)와 erase(0) 처럼 0번 인덱스에 대한 삽입, 삭제의 경우에서는 원형배열을 통해 O(1)의 시간복잡도를 가짐.
Growable Array-based Vector(Extendable Array)
확장가능한 배열
- index없이 insert(o)를 하는 경우 항상 끝에 삽입된다.
- 배열이 꽉 차면 더 큰 배열로 대체한다.
배열을 증가시키는 방법 두가지.
-> Incremental strategy: c만큼 size를 증가시킴.
-> Doubling strategy: 두배로 증가시킴.
process
크기 N인 새로운 배열 A를 할당 -> 기존 배열 S[i]를 A[i]로 이동.(i = 0, ..., N-1) -> S를 할당 해제, S에 A를 할당.
Position, Iterators, Lists
Position
임의의 자료구조의 '주소'를 모델링
유일한 method
element(): 주어진 위치에 해당하는 값 리턴 ( c++의 *p와 동일한 기능. )
Iterators
배열이나 그와 유사한 자료구조의 내부요소를 순회하는 객체다.
반복자는 포지션의 확장된 개념(포인터와 동일한 역할)이며 다음과 같은 기능을 갖는다.
- 노드의 요소에 접근
- 컨테이너를 앞뒤로 순회
반복자 역시 배열 기반과 리스트 기반으로 나뉜다.
(다음에 깊게 다루겠다.)
반복자는 begin(), end() 함수를 통해 초기화되는데 여기서 주의할 점은 리스트에서 end() 함수를 통해 리턴되는 것이 마지막 원소의 다음번 주소로 아무 의미 없는 것을 가리키고 있다는 것이다.
for loop문을 돌 때 편하다는 장점과 오류 핸들링 등등의 장점이 있다고 한다.
(Node) List란?
이중 연결리스트의 확장.
연결리스트와 다른 점 : Node의 data에 해당하는 부분이 Position으로 되어있다. 특정 데이터의 주소가 연결된 것이 바로 List 이다.
Generic method:
size()
empty()
Iterators:
begin(): 시작 노드의 주소 리턴
end(): 마지막 노드 다음 노드의 주소 리턴
Update methods: (일반적인 삭제, 제거)
inserFront(e), insertBack(e)
removeFront(), removeBack()
Iterator-based update: (반복자로 받은 주소를 통한 삽입, 삭제)
insert(p,e)
remove(p)
Sequence란?
벡터와 리스트의 확장. index와 position을 통한 탐색이 모두 가능하다.
리스트와 벡터를 이어주는 Bridge metods가 존재한다.
요소에 접근하는 방식
- Rank: index
- Position: *p - 노드
Generic method:
size()
empty()
Sequence ADT
Vector-based methods:
elemAtRank(i): 인덱스 i에 있는 요소 리턴
replaceAtRank(i, o): 인덱스 i에 있는 값을 o로 바꿈
insertAtRank(i, o): 인덱스 i에 새로운 요소 o를 삽입
removeAtRank(i): 인덱스 i에 있던 값을 지움
List-based methods:
first(), last(), before(p), after(p)
replaceElem(p, o): position p에 있던 값을 o로 바꿈
swapElemts(p, q): position p와 q에 있던 값을 서로 바꿈
insertBefore(p, o): position p 앞에 새로운 요소 o를 삽입
insertAfter(p, o): pisution p 뒤에 새로운 요소 o를 삽입
insertFirst(o): 맨 앞 삽입
insertLast(o): 맨 뒤 삽입
remove(p): position p에 있던 값을 지움
Bridge metods:
atRank(r)=atIndex(i): 인덱스(랭크) r의 position(주소)을 리턴
rankOf(p)=Indexof(p): position p에 있는 요소의 인덱스를 리턴
