4. 시퀀스 [Sequence]

sequence

noun
a group of related events or things that have a particular order

연속적인 사건 및 행동들

수열 (수학)

• vector
• list

vector

aka. arrayList

• 배열의 확장 개념
• index를 통해 접근한다
• Circulary Array :
  0 -> 1 -> 2 -> ... -> n-1 -> 0

수행시간

i : index, o : object

• getSize(), isEmpty(), at(i), update(i,o)
  -> O(1)
• insert(i,o), erase(i)
  -> O(n)

꽉차면?

더 큰 배열을 만들고 대체한다.

• Incremetnal strategy : 특정 값을 정해놓고 그만큼씩 늘린다!
• Doubling strategy : 두배로 키운다!

List

singly linked list

doubly linked list

circularly linked list

circularly linked list

tail->next = head
head->prev = tail

수행시간

• getSize(), isEmpty(), remove(), insert() -> O(1)
  (※ 위치 정보를 알고 있을 때 )

Iterator

sequence의 내부를 순회(traversing)하는 객체

in vector : (index+1) % size
in list : curNode = curNode->next

Iterator 구현

class Iterator {
private:
    Node *node;

public:
    void set(Node *node) {
        this->node = node;
    }

    Node *get() {
        return node;
    }

    Iterator *operator++() {
        node = node->next;
        return this;
    }

    Iterator *operator--() {
        node = node->prev;
        return this;
    }

    friend class Sequence;
};

사용 방법

 void next() {
        if (iter->get() == trailer) {
            return;
        }
        iter++;
}
void prev() {
        if (iter->get() == header->next) {
            return;
        }
        iter--;
 }