벡터(Vectors) & 리스트(List) 자료구조

벡터 ADT

- 객체의 순차적인 저장으로 배열의 개념을 확장함.

- 삽입 / 삭제 연산으로 원소에 접근하기 위해선 Index가 반드시 필요함.

- 벡터의 연산

at(int i) - 제거하지 않고 index i번째의 원소를 리턴함.

set(int i , object o) - i번째의 원소를 o로 대체함.

insert(int i, object o) - i번째의 원소에 o를 삽입함.

erase(int i) - i번째의 원소를 삭제함.

size() - 벡터의 크기를 반환함.

empty() - 벡터가 비었는지 확인함.

 

배열에 기초한 실행

- N 크기의 배열 A를 사용함.

- 변수 n은 벡터의 크기를 추적함.(저장된 원소에 따라 크기 변화 -> 벡터를 사용하는 가장 큰 이유이자 장점)

- at 메소드의 시간복잡도는 O(1)

- set 메소드의 시간복잡도는 O(1)

- insert 메소드의 시간복잡도는 O(n)

- erase 메소드의 시간복잡도는 O(n)

- 그러나 만약 환형 배열을 통해 구현하면 , 0번째 index에 insert와 erase 메소드의 시간복잡도를 O(1)로 바꿀 수 있음.

 

리스트 ADT

- 리스트 ADT는 저장하는 임의의 객체의 순차적인 positions로 구성됨.

- 리스트의 연산

size() - 리스트의 크기를 리턴함.

empty() - 리스트가 비었는지 확인함.

begin() - Iterator(반복자)로 리스트의 시작 position

end() - Iterator(반복자)로 리스트의 끝 position

insertFront(e) , insertBack(e) - 앞/뒤에 객체 e를 삽입함.

eraseFront() , eraseBack() - 앞/뒤에 객체를 제거함.

insert(p,e) - position *p에 e를 삽입함.

erase(p) - position *p에 객체를 제거함.

 

더블 링크드 리스트(Doubly Linked List)

- Node는 Position과 Element를 저장한다.

element , previous node, next node

- trailer(맨 뒤)와 header(맨 앞)의 특별한 노드를 갖는다.

 

삽입 연산과 삭제 연산

Algorithm insert(p,e){
	create a new node V
    v->element = e
    u = p->prev
    v->next = p; p->prev = v
    v->prev = u; u->next = v;
}

Algorithm erase(p){
	u = p->prev
    w = p->next
    u->next = w
    w->prev = u
}