Sequence

○Sequence

 ▷Array List, Node List를 조합한 것.

 ▷index 또는 position으로 접근 가능

 ▷정렬된 자료들을 저장하는 기초적인 자료구조

 ▷stack, queue, vector, list를 대체 가능

 

 ▶메소드

  ▶Generic

   ▷size(): Sequence의 요소의 수 반환

   ▷empty(): Sequence가 비어있는가?

 

  ▶ArrayList-based

   ▷at(index): index에 있는 object 반환

   ▷set(index, object): index에 해당 object 할당.

   ▷insert(index): index에 해당 object 삽입

   ▷erase(index): index에 있는 object 제거.

 

  ▶List-based

   ▷begin(): 가장 앞의 position 반환.

   ▷end(): 가장 뒤의 position 뒤에 있는 가상의 position 반환.

   ▷insertFront(e): 가장 앞에 해당 element를 가진 position 추가

   ▷insertBack(e): 가장 뒤에 해당 element를 가진 position 추가

   ▷removeFront(): 가장 앞의 position 제거

   ▷removeBack(): 가장 뒤의 position 제거

   ▷insert(p, e): position p의 앞에 e를 가진 position 추가.

   ▷remove(p) : position p 제거.

 

  ▶Bridge

   ▷atIndex(i): index -> position

   ▷indexOf(p): position -> index

 

 ▶구현

  ▶Linked List Implementation

   ▷Doubly Link List로 만듬.

   ▷Node는 element, next node, previous node를 가지고 있음.

   ▷postion based -> O(1) / index vased -> O(n)

 

  ▶Array-based Implementation

   ▷Circular Array로 만듬.

   ▷Array는 position을 담고 있음.

   ▷position은 index와 element를 담고 있음.

   ▷중간 삽입, 삭제 -> O(n)

 

  ▶실행 시간 비교