[알고리즘] 연결리스트 class 로 구현한 양방향 링크드 리스트 (예제코드)

직접 테스트완료된 예제코드

• 예제코드

예제코드

#ifndef DLIST2_H 
#define DLIST2_H 

template class list 
{ 
////////////////////////////////////////////// 
private: 
    class node 
    { 
    public: 
        node* llink; 
        node* rlink; 
        T data; 
        node(node * a, node* b, T c) : llink(a), rlink(b), data(c) {} 
    }; 
    node* head; 
////////////////////////////////////////////// 
public: 
    typedef node* POSITION; 

    list() // 생성자 
    { 
        head= new node(0,0,0); // 헤드 노드를 생성한다 data에는 count를 저장한다 
        head->llink=head; // 처음에는 자기자신을 가르킨다 
        head->rlink=head; 
    } 
    ~list() // 소멸자 
    { 
        while(head->data) pop_front(); 
        delete head; // 헤드 노드도 삭제한다 
    } 
////////////////////////////////////////////// 
    void push_front(T data) // 앞에 넣기 
    { 
        POSITION t= new node(NULL,NULL,data); 

        t->llink=head; 
        t->rlink=head->rlink; 
        head->rlink->llink=t; 
        head->rlink=t; 

        head->data++; // 갯수 증가 
    } 

    void push_back(T data) // 맨 뒤에 넣기 
    { 
        node* t= new node(NULL,NULL,data); 

        t->llink=head->llink; // 앞과 반대로 넣는다 
        t->rlink=head; 
        head->llink->rlink=t; 
        head->llink=t; 

        head->data++; // 갯수 증가 
    } 
//////////////////////////////////////////////////////////////////////////////// 

    T pop_front() // 앞에 삭제 
    { 
        if(head->data==0) return 0; 
        else 
        { 
            T temp= head->rlink->data; // 삭제값 임시저장 
            erase(head->rlink); 
            return temp; 
        } 
    } 

    T pop_back() // 맨 뒤에 삭제 
    { 
        if(head->data==0) return 0; 
        else 
        { 
            T temp= head->llink->data; // 삭제값 임시저장 
            erase(head->llink); 
            return temp; 
        } 
    } 
//////////////////////////////////////////////////////////////////////////////// 
    POSITION get_first_position() const // 처음위치 알려줌 
    { 
        if(head->data!=0) 
        { 
            return head->rlink; 
        } 
        cout << "노드가 없습니다" << endl; 
        return NULL; 
    } 

    POSITION get_last_position() const // 마지막위치 알려줌 
    { 
        if(head->data!=0) 
        { 
            return head->llink; 
        } 
        cout << "노드가 없습니다" << endl; 
        return NULL; 
    } 

    POSITION get_next_position(POSITION p) const // 다음위치 알려줌 마지막은 0 
    { 
        if(p!=NULL) 
        { 
            assert(p); 
            return (p==head->llink ? NULL : p->rlink); 
            // 헤드노드의 llink는 마지막 노드를 가르킨다 따라서 p가 같으면 마지막이고 
            // 아니면 다음 노드를 반환 
        } 
        cout << "노드가 없습니다" << endl; 
        return NULL; 
    } 

    POSITION get_pre_position(POSITION p) const // 앞위치 알려줌 처음은 0 
    { 
        if(p!=NULL) 
        { 
            assert(p); 
            return (p==head->rlink ? 0 : p->llink); 
            // 헤드노드의 rlink는 처음 노드를 가르킨다 따라서 p가 같으면 
            // 처음이고 아니면 앞 노드를 반환 
        } 
        cout << "노드가 없습니다" << endl; 
        return NULL; 
    } 

    T get_data(POSITION p) const // 현재위치의 데이타 알려줌 
    { 
        if(p!=NULL) 
        { 
            assert(p); 
            return p->data; 
        } 
        cout << "노드가 없습니다" << endl; 
        return NULL; 
    } 
//////////////////////////////////////////////////////////////////////////////// 
    POSITION find(T value) const // value를 찾아서 위치를 알려줌 
    { 
        POSITION p=head->rlink; // 헤드값은 고정하고 처음부터 움직이는 포인터 생성 
        while(1) 
        { 
            if(p==NULL) // 끝까지 갔면 값이 없으므로 에러 출력후 반환 
            { 
                cout << "찾는 값이 없습니다" << endl; 
                return NULL; 
            } 
            else if(p->data==value) { return p; } 
            // 찾는 값이면 바로 반환 p가 널값일때 이 문장이 먼저 나오면 에러다 
            p=get_next_position(p); // 다음것 찾는다 
        } 
    } 

    POSITION erase(POSITION pos) // pos를 삭제하고 다음 요소의 위치를 알려줌 
    { 
        if(pos && pos->llink) 
        // pos가 널값이 아니고 제대로 된 주소일때 pos가 널값일때 조건문의 순서가 틀리면 에러다 
        { 
            POSITION ptemp; 
            if(pos==get_last_position()) ptemp=NULL; // 마지막일때는 널값 반환 or 순환? 
            else ptemp=pos->rlink; // 반환값을 임시저장 

            pos->llink->rlink=pos->rlink; // pop하는것처럼 한다 
            pos->rlink->llink=pos->llink; 

            delete pos; // 삭제 
            head->data--; // 갯수 감소 
            return ptemp; // 다음 주소 리턴 
        } 
        cout << "위치를 확인해 주세요" << endl; 
        return NULL; // 제대로 된 값이 아니면 NULL값을 리턴 
    } 
}; 

#endif