Sequence (based Doubly LinkedList) 실습

1. class Node

- int e : 데이터

- Node* prev : 이전노드 포인터

- Node* next : 다음노드 포인터

 

2. class Iterator : 노드에 접근하는 포인터 개념

- Node* v : Iterator가 가리키는 대상 노드 (초기화 : begin())

 

3. Iterator : int &operator*()

- Iterator가 가리키는 대상의 값을 반환

- * 연산자를 사용하기 위한 오버로딩 개념

- v->e를 반환한다

 

4. Iterator : bool operator==(const Iterator &p) const

- 받아온 p와 Iterator가 같은 Iterator인지 여부를 반환한다

- main에서 보내는 Iterator를 그대로 비교해야 하기에 Iterator의 주소인 Iterator &p로 주소를 받는다

- this->v == p.v 여부를 반환한다

 

5. Iterator : bool operator!=(const Iterator &p) const

- 받아온 p와 Iterator가 다른 Iterator 인지 여부를 반환한다

- main에서 보내는 Iterator를 그대로 비교해야 하기에 Iterator의 주소인 Iterator &p로 주소를 받는다

- this->v != p.v 여부를 반환한다

 

6. Itetator : Iterator &operator++()

- Iterator를 다음노드위치로 옮긴다

- ++ 연산자를 사용하기 위한 오버로딩 개념

- v = v->next로 이동한다

- *this를 반환한다 (Iterator 값을 반환한다)

 

7. Iterator : Iterator &operator--()

- Iterator를 이전노드위치로 옮긴다

- --연산자를 사용하기 위한 오버로딩 개념

- v = v->prev로 이동한다

- *this를 반환한다 (Iterator 값을 반환한다)

 

8. friend class Sequence

- Sequence 클래스에서 Iterator를 사용하기 위한 선언

 

 

 

9. class Sequence : Iterator가 가리키는 Node와 인덱스 개념의 조합

- int n : 개수

- Node* header : 맨앞 노드를 가리키는 포인터, list의 head와 다르게 노드자체이다 (값이 없는 노드)

- Node* tailer : 맨뒤 노드의 뒤를 가리키는 포인터, list의 tail과 다르게 노드자체이다 (값이 없는 노드)

 

10. Sequence : int size() const

- 개수인 n을 반환한다

 

11. Sequence : bool empty() const

- n==0 여부를 반환한다

 

12. Sequence : Iterator begin() const

- 값이 없는 header의 다음번째 노드를 가리킨다 (값이 있는 노드)

- Iterator 를 Sequence의 header->next 위치로 수정하여 반환한다

- return Iterator(header->next) 반환한다

 

13. Sequence : Iterator end() const

- 값이 없는 tailer 노드를 가리킨다

- Iterator를 Sequence의 tailer 위치로 수정하여 반환한다

- return Iterator(trailer)

 

14. Sequence : void insert(const Iterator &p, const int e)

- Iterator p가 가리키는 노드위치에 새로운 노드를 추가한다

- p가 가리키는 노드를 w로 저장한다

- w의 이전노드를 u로 저장한다

- 새로운 노드 v를 생성 후 값을 e로 넣는다

- v의 다음노드를 w로 설정한다 (v -> w)

- w의 이전노드를 v로 설정한다 (v <- w)

- v의 이전노드를 u로 설정한다 (u <- v)

- u의 다음노드를 v로 설정한다 (u -> v)

- 개수인 n을 증가시킨다

 

15. Sequence : void insert(const int e)

- 맨앞 위치에 새로운 노드를 추가한다

- insert 함수의 Iterator를 begin() 위치로 넣는다

- insert(begin(), e)를 실행한다

 

16. Sequence : void insertBack(const int e)

- 맨뒤 위치에 새로운 노드를 추가한다

- insert 함수의 Iterator를 end() 위치로 넣는다

- insert(end(), e)를 실행한다

 

17. Sequence : erase(const Iterator &p)

- Iteratpr p가 가리키는 노드를 삭제한다

- 만약 size()가 0인경우 empty 상태를 반환한다

- p가 가리키는 노드를 v로 저장한다

- v의 다음노드를 w로 저장한다

- v의 이전노드를 u로 저장한다

- u의 다음노드를 w로 설정한다 (u -> w)

- w의 이전노드를 u로 설정한다 (u <- w)

- 중간에 위치했던 v를 삭제한다

- 개수인 n을 감소시킨다

 

18. Sequence : void eraseFront()

- 맨앞 위치의 노드를 삭제한다

- erase 함수의 Iterator를 begin() 위치로 넣는다

- erase(begin())을 실행한다

 

19. Sequence : void eraseBack()

- 맨뒤 위치의 노드를 삭제한다

- erase 함수의 Iterator를 --end() 위치로 넣는다

- end()위치의 경우 값이 없는 노드이기 때문에 반드시 end()이전위치인 --end() 위치를 넣어야 한다

- erase(--end())를 실행한다

 

20. Sequence : Iterator atIndex(int i) const

- 인덱스 i 위치의 노드를 가리키는 Iterator를 반환한다

- 노드접근을 위한 Iterator p를 설정한다

- p를 begin()으로 설정한다

- for문을 j=0부터 j<i까지 증가시킨다

- ++p를 통해 Iterator가 가리키는 노드를 이동시킨다

- for문이 종료된 후 p를 반환한다

 

21. Sequence : int indexOf(const Iterator &p) const

- Iterator p가 가리키는 노드의 인덱스를 반환한다

- 반복문 증감을 위한 Iterator q, 인덱스 j를 설정한다

- q를 begin()으로, j=0으로 설정한다

- while q != p 동안 ++q, ++j 각각 증감을 해준다

- while이 종료되면 q는 p와 같아지므로 해당위치인 j를 반환해준다

 

22. Sequence : void print()

- Sequence에 있는 모든노드의 값을 출력한다

- 만약 empty() 인 경우 empty 상태를 반환한다

- 노드접근을 위한 Iterator를 p로 설정한다

- p를 begin()으로 설정한다

- 종료를 위한 Iterator를 q로 end() 값으로 설정한다

- while q != p 동안 반복하여 p->v->e 즉, Iterator가 가리키는 노드 안에있는 값을 출력한다

- ++p를 통해 Iterator가 다음노드를 가리킨다

class Sequence {
public:
    int n;
    Node* header;
    Node* trailer;

    Sequence() {
        this->n = 0;
        this->header = new Node;
        this->trailer = new Node;
        header->next = trailer;
        trailer->prev = header;
    }

    int size() const {
        return n;
    }

    bool empty() const {
        return (n==0);
    }

    Iterator begin() const {
        return Iterator(header->next);
    }

    Iterator end() const {
        return Iterator(trailer);
    }

    void insert(const Iterator &p,const int e) {
        Node* w = p.v;
        Node* u = w->prev;
        Node* v = new Node;
        
        v->e = e;

        v->next = w;
        w->prev = v;
        v->prev = u;
        u->next = v;
        
        this->n++;
    }

    void insertFront(const int e) {
        insert(begin(),e);
    }

    void insertBack(const int e) {
        insert(end(),e);
    }

    void erase(const Iterator &p) {
        if(size() == 0) {
            cout<<"Empty\n";
        }
        else {
            Node* v = p.v;
            Node* w = v->next;
            Node* u = v->prev;

            u->next = w;
            w->prev = u;

            delete v;
            this->n--;
        }
    }

    void eraseFront() {
        erase(begin());
    }

    void eraseBack() {
        erase(--end());
    }

    Iterator atIndex(int i) const {
        Iterator p = begin();
        for(int j=0; j<i; j++) {
            ++p;
        }
        return p;
    }

    int indexOf(const Iterator& p) const {
        Iterator q = begin();
        int j = 0;
        while(q != p) {
            ++q;
            ++j;
        }
        return j;
    }

    void print()
    {
        if(empty())
        {
            cout<<"Empty\n";
        }
        else
        {
            Iterator p = begin();
            Iterator q = end();
            while(p != q)
            {
                cout<<p.v->e<<" ";
                ++p;
            }
            cout<<"\n";
        }
    }
};