[자료구조] 연결 리스트 2 (체인 반복자, 체인 조작 연산 2)

반복자(iterator)

반복자의 필요성

컨테이너 클래스의 종류에 따라 최대값을 찾는 구현 코드가 다름

- ex) 배열과 체인에 대해 최대값을 찾는 코드가 다르다

 

내부 구조의 이해 없이 컨테이너에 저장된 객체를 이용할 수 있는 반복자 필요

 

C++ 반복자

- 객체의 원소에 대한 포인터

- 객체의 원소를 하나씩 지나가도록 지원

 

C++ STL 반복자의 부류

• 입력
• 출력
• 전방
• 양방
• 임의접근

 

반복자 지원 연산

• 참조 연산자 *
• 동등 연산자 ==, !=
• 반복자 전진 ++, 감소 --
• 포인터 산술 연산, 임의의 양 점프 +=, -=

 

Chain에 대한 전방 반복자

Chain을 위한 전방 반복자 클래스

class ChainIterator
{
private:
    ChainNode<T> *current;

public:
    // C++ 데이터 타입의 전방 반복자

    // 생성자
    ChainIterator(ChainNode<T> *startNode = 0)
    {
        current = startNode;
    }

    T &operator*() const { return current->data; }
    T *operator->() const { return &current->data; }

    ChainIterator &operator++()
    {
        current = current->link;
        return *this;
    }
    ChainIterator operator++(int)
    {
        ChainIterator old = *this;
        current = current->link;
        return old;
    }

    bool operator!=(const ChainIterator right) const
    {
        return current != right.current;
    }
    bool operator==(const ChainIterator right) const
    {
        return current == right.current;
    }
};

- ChainIterator가 Chain의 공용 중첩 멤버 클래스

- Chain에 아래와 같은 공용 멤버 함수들이 정의

ChainIterator begin() { return ChainIterator(first); }
// 리스트의 첫 번째 노드로 초기화된 반복자를 반환

CharinIterator end() { return ChainIterator(0); }
// 리스트의 마지막 노드를 하나 지난 위치로 초기화된 반복자를 반환

 

- 반복자 객체 yi를 다음 명령문을 사용하여 정수 체인 y의 시작점으로 초기화

Chain<int>::ChainIter yi = y.begin()

 

- 반복자 덕분에 STL 알고리즘 accumulate를 사용해 원소들의 합 계산 가능

Sum = accumulate(y.begin(), y.end(), 0);

 

체인 연산

재사용 가능한 클래스에 포함될 연산

• 생성자
• 파괴자
• 지정 연산자(operator =)
• 동등 검사 연산자(operator ==)
• 클래스 객체 입출력 연산자(operator>>, operator<<)

 

체인 연산

• 삽입, 삭제 연산(체인의 앞, 체인의 끝, 체인의 i번째 위치)이 필요
• last: 리스트의 마지막 노드를 가리킴
• 리스트의 끝에 노드 삽입

 

template <class T>
void Chain<T>::InsertBack(const T &e)
{
    if (first)
    { // 비어있지 않은 체인
        last->link = new ChainNode<T>(e);
        last = last->link;
    }
    else
        first = last = new ChainNode<T>(e);
}

 

template <class T>
void Chain<T>::Concatenate(Chain<T> &b)
{ // b는 *this의 마지막에 연결
    if (first)
    {
        last->link = b.first;
        last = b.last;
    }
    else
    {
        first = b.first;
        last = b.last;
    }
    b.first = b.last = 0;
}

 

시간복잡도 - O(1)

 

template <class T>
void Chain<T>::Reverse()
{ // 체인의 순서를 뒤집는 함수
    ChainNode<T> *current = first,
                 *previous = 0;
    while (current) 
    {
        ChainNode<T> *r = previous; // 새 노드 포인터 r이 previous 노드를 가리키도록 함
        previous = current;
        current = current->link; // current는 다음 노드로 이동
        previous->link = r;      // previous를 이전 노드와 연결
    }
    first = previous;
}

 

시간복잡도 - O(n)